СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 11 № 11112

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

 

БейсикPython

SUB F(n)

  IF n > 0 THEN

    PRINT "*"

    F(n - 1)

    F(n \ 3)

  END IF

END SUB

def F(n):

    if n > 0:

        print("*")

        F(n - 1)

        F(n // 3)

Алгоритмический языкПаскаль

алг F(цел n)

нач

  если n > 0 то

    вывод "*"

    F(n - 1)

    F(div(n, 3))

  все

кон

procedure F(n: integer);

begin

  if n > 0 then

  begin

    writeln('*');

    F(n - 1);

    F(n div 3)

  end

end

Си

void F(int n)

{

  if (n > 0)

  {

    printf("*");

    F(n - 1);

    F(n / 3);

  }

}

 

 

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(6)?

Решение.

Рассмотрим структуру вызова функций.

 

 F(6)

 {

    F(5)

    F(2)

    {

       F(4)

       F(1)

       F(1)

       F(0)

       {

          F(3)

          F(1)

          F(0)

          F(0)

          F(0)

          F(0)

            {

            F(2)

            F(1)

            F(0)

            {

              F(1)

              F(0)

                {

                F(0)

                }

              }

            }

       }

    }

 }

 

Число напечатанных «звёздочек» равно числу вызовов функции F(n) с аргументом не равным нулю, то есть равно 11.

 

Ответ: 11.

Источник: ЕГЭ по ин­фор­ма­ти­ке 23.03.2016. До­сроч­ная волна
Спрятать решение · ·
Vlad Boltenkov 08.06.2016 16:34

F(6)

{

F(5)

F(2)

{

F(4)

F(1)

F(1) - откуда эта единица

F(0)

{

F(3)

F(1)

F(0)

F(0)

F(0)

F(0)

{

F(2)

F(1)

F(0)

{

F(1)

F(0)

{

F(0)

Сергей Никифоров

Поясняем: F(5) вызывает F(4) и F(1), а F(2) вызывает F(1) и F(0).