Question

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

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

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

Accepted Answer

1231412

Answer

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

Алгоритм F(n) работает следующим образом:
- если n ≤ 0, ничего не происходит;
- если n > 0, то сначала вызывается F(n − 1), затем выводится n, затем вызывается F(n − 2).

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

```
F(4)
├─ F(3)
│  ├─ F(2)
│  │  ├─ F(1)
│  │  │  ├─ F(0) → ничего
│  │  │  └─ вывод: 1
│  │  │  └─ F(-1) → ничего
│  │  └─ вывод: 2
│  │  └─ F(0) → ничего
│  └─ вывод: 3
│  └─ F(1)
│     ├─ F(0) → ничего
│     └─ вывод: 1
│     └─ F(-1) → ничего
└─ вывод: 4
└─ F(2)
   ├─ F(1)
   │  ├─ F(0) → ничего
   │  └─ вывод: 1
   │  └─ F(-1) → ничего
   └─ вывод: 2
   └─ F(0) → ничего
```

Порядок выводов: 1, 2, 3, 1, 4, 1, 2.

Проверим с помощью кода:

```python
def F(n):
    if n > 0:
        F(n - 1)
        print(n, end='')
        F(n - 2)

F(4)
```

Вывод: `1231412`

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