Дан рекурсивный алгоритм: : integer); ('*'); then begin (n-2); (n-2); (n div 2); ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова ?

Добавлена: 03.05.2026
Обновлена: 03.05.2026
Предмет: Информационные технологии
Автор: Кэмп

#Математическая логика и теория алгоритмов
#Алгоритмы и структуры данных

Дан рекурсивный алгоритм: : integer); ('*'); then begin (n-2); (n-2); (n div 2); ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова ?

Условие:

Дан рекурсивный алгоритм:\nprocedure $\mathbf{F}(\mathbf{n}$ : integer);\nbegin\nwriteln('*');\nif $\mathrm{n}>0$ then begin\nF(n-2);\nF(n-2);\nF(n div 2);\nend\nend; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова $F(6)$ ?

Решение:

Обозначим T(n) – количество напечатанных звездочек при вызове F(n).

Анализ алгоритма:

При вызове F(n) всегда печатается одна звездочка. Если n > 0, то выполняются три рекурсивных вызова: F(n‑2), F(n‑2) и F(n div 2).

Таким образом, можно записать рекуррентное соотношение:
T(n) = 1, если n ≤ 0 (так как при n ≤ 0 условие n > 0 ложно, и дальнейших вызовов нет);
T(n) = 1 + 2·T(n‑2) + T(n div 2), если n >
0.

Теперь пошагово вычислим T(6).