Задание 4 Параграф 1.6 ГДЗ Босова 9 класс Углубленный уровень (Информатика)
Рассмотрим вариант решения задания из учебника
Босова, Аквилянов 9 класс, Просвещение:
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2
2. умножь на 2
Сколько есть программ, которые число 1 преобразуют в число 24?
Решите эту задачу двумя способами:
1) выполнив необходимые вычисления вручную;
2) написав программу и выполнив её на компьютере.
K(n) = K(n-2) + K(n/2)
n 1 2 3 4 5 6 7 8 9 10 11 12 13
K 1 1 1 2 1 3 1 5 1 6 1 9 1
n 14 15 16 17 18 19 20 21 22 23 24
K 10 1 15 1 16 1 22 1 23 1 32
Программа:
def trek(n):
if n < =2: return 1
elif F[n]!=0: return F[n]
elif n%2==0: F[n]=trek(n-2)+trek(n//2)
else:F[n]=trek(n-2)
return F[n]
n=int(input('N > > '))
F=[0]*1000
print(trek(n))
Окно вывода:
N > > 24
32
