Номер 8, страница 130 - гдз по информатике 11 класс учебник Босова, Босова

Параграф 9. Структурное программирование. Глава 2. Алгоритмы и элементы программирования - номер 8, страница 130.

Условие.

8. Исполнитель Калькулятор имеет следующую систему команд:

1) прибавь 1;
2) умножь на 2.

С помощью первой из них исполнитель увеличивает число на экране на 1, с помощью второй — в 2 раза.

1) Выясните, сколько разных программ, преобразующих число 1 в число 20, можно составить для этого исполнителя.

2) Сколько среди них таких программ, у которых в качестве промежуточного результата обязательно получается число 15?

3) Сколько среди них таких программ, у которых в качестве промежуточного результата никогда не получается число 12?

Решение.

1) 60.
На языке Python:
def F(x, y):
if x == y: return 1
if x > y: return 0
if x ‹ y: return F(x + 1, y) + F(x * 2, y)
print (F(1, 20))

2) 26.
На языке Python:
def F(x, y):
if x == y: return 1
if x > y: return 0
if x ‹ y: return F(x + 1, y) + F(x * 2, y)
print (F(1, 15))

3) 40 для исходного числа 1 преобразующего в число 20 и при этом не содержит число 12.
На языке Python:
def F(x, y):
if x == y: return 1
if x > y or x==12: return 0
if x ‹ y: return F(x + 1, y) + F(x * 2, y)
print (F(1, 20))