Question

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

Бейсик	Python
SUB F (n) IF n > 0 THEN F(n − 1) PRINT n F(n \ 4) END IF END SUB	def F(n): if n > 0: F(n − 1) print(n) F(n // 4)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin if n > 0 then begin F(n − 1); write(n); F(n div 4); end end;	алг F(цел n) нач если n > 0 то F(n − 1) вывод n F(div(n, 4)) все кон
C++
void F(int n){ if (n > 0){ F(n − 1); std::cout << n; F(n / 4); } }

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(5). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Accepted Answer

1234151

Answer

Идея решения: проследить порядок выполнения рекурсивных вызовов, учитывая, что вывод происходит между двумя рекурсивными обращениями.

Структура функции: перед выводом числа n вызывается F(n − 1), а после вывода — F(n // 4).

Проследим вызовы F(5):

**F(5):** n > 0
- Вызов F(4)
  - **F(4):** n > 0
    - Вызов F(3)
      - **F(3):** n > 0
        - Вызов F(2)
          - **F(2):** n > 0
            - Вызов F(1)
              - **F(1):** n > 0
                - Вызов F(0)
                  - **F(0):** n = 0, выход
                - Вывод: **1**
                - Вызов F(0)
                  - **F(0):** n = 0, выход
            - Вывод: **2**
            - Вызов F(0)
              - **F(0):** n = 0, выход
        - Вывод: **3**
        - Вызов F(0)
          - **F(0):** n = 0, выход
    - Вывод: **4**
    - Вызов F(1)
      - **F(1):** n > 0
        - Вызов F(0)
          - **F(0):** n = 0, выход
        - Вывод: **1**
        - Вызов F(0)
          - **F(0):** n = 0, выход
  - Вывод: **5**
  - Вызов F(1)
    - **F(1):** n > 0
      - Вызов F(0)
        - **F(0):** n = 0, выход
      - Вывод: **1**
      - Вызов F(0)
        - **F(0):** n = 0, выход

Последовательность выводов: 1, 2, 3, 4, 1, 5, 1.

Задание №16Алгоритмы и исполнителиЕГЭ по информатике