Question

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

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

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

Accepted Answer

3334567

Answer

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

Функция F(n) выполняет следующие действия при n > 2:
1. Вызывает F(n // 2)
2. Вызывает F(n − 1)
3. Выводит число n

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

**F(7):** n > 2, поэтому
- Вызов F(7 // 2) = F(3)
  - F(3): n > 2, поэтому
    - Вызов F(3 // 2) = F(1) — условие не выполнено, выход
    - Вызов F(2) — условие не выполнено, выход
    - Вывод: **3**
- Вызов F(6)
  - F(6): n > 2, поэтому
    - Вызов F(3)
      - F(3): n > 2, поэтому
        - Вызов F(1) — выход
        - Вызов F(2) — выход
        - Вывод: **3**
    - Вызов F(5)
      - F(5): n > 2, поэтому
        - Вызов F(2) — выход
        - Вызов F(4)
          - F(4): n > 2, поэтому
            - Вызов F(2) — выход
            - Вызов F(3)
              - F(3): n > 2, поэтому
                - Вызов F(1) — выход
                - Вызов F(2) — выход
                - Вывод: **3**
            - Вывод: **4**
        - Вывод: **5**
    - Вывод: **6**
- Вывод: **7**

Порядок выводов: 3, 3, 3, 4, 5, 6, 7.

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