Question

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

| Бейсик | Python |
| --- | --- |
| SUB F(n) PRINT n IF n < 5 THEN F(n + 1) F(n + 3) END IF END SUB | def F(n): print(n) if n < 5: F(n + 1) F(n + 3) |
| Паскаль | Алгоритмический язык |
| procedure F(n: integer); begin writeln(n); if n < 5 then begin F(n + 1); F(n + 3) end end | алг F(цел n) нач вывод n, нс если n < 5 то F(n + 1) F(n + 3) все кон |
| С++ |
| void F(int n) { cout << n << endl; if (n < 5) { F(n + 1); F(n + 3); } } |

Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?

Accepted Answer

49

Answer

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

Функция выводит текущее значение n, а затем (если n < 5) рекурсивно вызывает себя с аргументами n + 1 и n + 3.

Проследим выполнение F(1):

1. F(1) выводит 1, затем вызывает F(2) и F(4).

2. F(2) выводит 2, затем вызывает F(3) и F(5).

3. F(3) выводит 3, затем вызывает F(4) и F(6).

4. F(4) выводит 4, затем вызывает F(5) и F(7).

5. F(5) выводит 5, условие n < 5 ложно, возврат.

6. F(7) выводит 7, условие n < 5 ложно, возврат.

7. Возврат в F(3), F(6) выводит 6, условие n < 5 ложно, возврат.

8. Возврат в F(2), F(5) выводит 5, условие n < 5 ложно, возврат.

9. Возврат в F(1), F(4) выводит 4, затем вызывает F(5) и F(7).

10. F(5) выводит 5, возврат.

11. F(7) выводит 7, возврат.

Последовательность выведённых чисел: 1, 2, 3, 4, 5, 7, 6, 5, 4, 5, 7.

Сумма: 1 + 2 + 3 + 4 + 5 + 7 + 6 + 5 + 4 + 5 + 7 = 49.

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

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