16 номер. Рекурсия
Рекурсивная процедура и вывод
Определите, сколько символов * выведет эта процедура при вызове F(40):
def F(n): print('*') if n>=1: print('*') F(n-1) F(n-3) print('*')Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Искомая величина: Определите, сколько символов * выведет эта процедура при вызове F(40):
Процедура печатает значения, поэтому её результат нужно описать отдельной функцией: C(n) — число напечатанных символов либо S(n) — сумма напечатанных чисел, в зависимости от вопроса. Возвращаемое значение самой процедуры для этого не используется.
Разберите один вызов по коду. Учитывайте печать до условия, внутри выполненной ветви и после неё. При невыполненном условии рекурсивных вызовов может не быть, но безусловная печать всё равно выполняется — это определяет базовый случай.
К собственному вкладу вызова прибавьте вклады всех рекурсивных вызовов с аргументами из программы. Одинаковый под-вызов учитывается столько раз, сколько он выполняется. Для числа символов или суммы порядок печати не меняет итог; при вопросе о порядке вывода его нужно сохранить.
Вычисляйте полученную вспомогательную функцию с сохранением уже найденных значений. Кэшируйте количество или сумму, а не саму печатающую процедуру: кэширование процедуры пропустит повторную печать и изменит ответ.
Ответ: 22947841.