
У исполнителя Увеличитель две команды, которым присвоены номера.
1. Прибавь 2.
2. Умножь на 3.
Первая из них увеличивает число на экране
Программа для Увеличителя — это последовательность команд. Сколько есть программ, которые
Решение. Очевидно,
Верны следующие соотношения.
1. Если n не делится
2. Пусть n делится
При n = 3 R(n) = 2 (два способа: прибавлением двойки или однократным умножением
Имеем:
R(1)= 1;
R(3) = 2 = R(5)=R(7);
R(9) = R(3)+R(7) = 2+2 = 4 = R(11) = R(13);
R(15) = R(5)+R(13) = 2+4 = 6 = R(17) = R(19);
R(21) = R(7)+R(19) = 2+6 = 8 = R(23) = R(25);
R(27) = R(9)+R(25) = 4+8 =12 = R(29) = R(31).
Ответ: 12.
Другой способ решения.
Очевидно, из числа 1 нельзя получить четное число. Будем решать поставленную задачу последовательно для чисел
| 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 |
| 1 | 2 | 2 | 2 | 4 | 4 | 4 | 6 | 6 | 6 | 8 | 8 | 8 | 12 | 12 | 12 |
Приведём другое решение на языке Python.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 2, y) + f(x * 3, y)
print(f(1, 31))
PDF-версии: