Question

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

| Бейсик | Python |
| --- | --- |
| SUB F(n) IF n > 0 THEN PRINT "*" F(n - 1) F(n \ 3) END IF END SUB | def F(n): if n > 0: print("*") F(n - 1) F(n // 3) |
| Алгоритмический язык | Паскаль |
| алг F(цел n) нач если n > 0 то вывод "*" F(n - 1) F(div(n, 3)) все кон | procedure F(n: integer); begin if n > 0 then begin writeln('*'); F(n - 1); F(n div 3) end end |
| Си |
| void F(int n) { if (n > 0) { printf("*"); F(n - 1); F(n / 3); } } |

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(6)?

Accepted Answer

11

Answer

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

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

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

```
F(6)
├─ F(5)
│  ├─ F(4)
│  │  ├─ F(3)
│  │  │  ├─ F(2)
│  │  │  │  ├─ F(1)
│  │  │  │  │  ├─ F(0) [не выводит]
│  │  │  │  │  └─ F(0) [не выводит]
│  │  │  │  └─ F(0) [не выводит]
│  │  │  └─ F(1)
│  │  │     ├─ F(0) [не выводит]
│  │  │     └─ F(0) [не выводит]
│  │  └─ F(1)
│  │     ├─ F(0) [не выводит]
│  │     └─ F(0) [не выводит]
│  └─ F(1)
│     ├─ F(0) [не выводит]
│     └─ F(0) [не выводит]
└─ F(2)
   ├─ F(1)
   │  ├─ F(0) [не выводит]
   │  └─ F(0) [не выводит]
   └─ F(0) [не выводит]
```

Подсчитаем вызовы с n > 0 (каждый выводит одну звёздочку):
- F(6): 1
- F(5): 1
- F(4): 1
- F(3): 1
- F(2): 2 (из F(4) и из F(6))
- F(1): 5 (из F(5), F(4), F(3), F(2), F(2))

Итого: 1 + 1 + 1 + 1 + 2 + 5 = **11** звёздочек.

Бейсик	Python
SUB F(n) IF n > 0 THEN PRINT "*" F(n - 1) F(n \ 3) END IF END SUB	def F(n): if n > 0: print("*") F(n - 1) F(n // 3)
Алгоритмический язык	Паскаль
алг F(цел n) нач если n > 0 то вывод "*" F(n - 1) F(div(n, 3)) все кон	procedure F(n: integer); begin if n > 0 then begin writeln('*'); F(n - 1); F(n div 3) end end
Си
void F(int n) { if (n > 0) { printf("*"); F(n - 1); F(n / 3); } }

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