Question

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

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

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

Accepted Answer

33

Answer

Идея решения: проследить рекурсивные вызовы функции и собрать все выведённые значения, отбросив вызовы с аргументом ≤ 2 (они ничего не печатают).

Функция выводит число n только если n > 2, затем рекурсивно вызывает себя с аргументами n − 3 и n − 4.

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

```
F(10)
├─ выводит 10
├─ F(7)
│  ├─ выводит 7
│  ├─ F(4)
│  │  ├─ выводит 4
│  │  ├─ F(1) — не выводит
│  │  └─ F(0) — не выводит
│  └─ F(3)
│     ├─ выводит 3
│     ├─ F(0) — не выводит
│     └─ F(-1) — не выводит
└─ F(6)
   ├─ выводит 6
   ├─ F(3)
   │  ├─ выводит 3
   │  ├─ F(0) — не выводит
   │  └─ F(-1) — не выводит
   └─ F(2) — не выводит
```

Выведённые числа: 10, 7, 4, 3, 6, 3.

Сумма: 10 + 7 + 4 + 3 + 6 + 3 = 33.

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