Программирование Python Напишите программы по примеру:
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?
Решение (теоретическое):
запишем рекуррентную формулу для вычисления – количества возможных программ для получения числа N из некоторого начального числа:
, если N не делится на 2
, если N делится на 2
все допустимые программы можно разбить на 2 части:
– переход от 1 до 10
– переход от 10 до 20
обозначим через количеств возможных программ получения числа b из числа a
очевидно, что если траектория проходит через c, то для любого c, такого что a < c < b
поэтому
вычисляем эти значения отдельно стандартным по рекуррентным формулам и перемножаем: 14 ⋅ 2 = 28
ответ: 28.
Решение (рекурсивная программа, Python):
главная проблема при решении этого задания – высокая вероятность арифметической ошибки, поэтому для проверки (если есть время) можно написать программу, реализующую тот же алгоритм
вычисления по рекуррентным формулам можно организовать с рекурсии
рекурсивная функция, которая возвращает количество программ для преобразования числа start в число x, может быть написана так:
def numProg( start, x ):
if x < start: return 0 # (1)
if x == start: return 1 # (2)
K = numProg( start, x-1 ) # (3)
if x % 2 == 0:
K += numProg( start, x//2 ) # (4)
return K
если число x меньше, чем начальное значение, количество программ равно 0 (строка (1))
если число x равно начальному значению, количество программ равно 1 (строка (2))
в остальных случаях всегда учитываем количество программ предыдущего числа (если последняя команда программы будет +1), см. строку (3)
если число 0078 чётное, нужно добавить ещё и количество программ для числа x//2 (строка (4))
в основной программе вычисляем количество программ от 1 до 10 и умножаем на количество программ от 10 до 20:
print( numProg(1,10)*numProg(10,20) )
ответ: 28.
188
233
Ответы на вопрос:
Популярно: Другие предметы
-
КатюшаМелихова14.06.2021 18:03
-
Олиф129.09.2021 17:41
-
Pikaduwert11.01.2020 05:06
-
ArtemD9816.09.2022 01:09
-
Borkborkk19.06.2022 00:40
-
alobatsevi425.04.2020 20:35
-
Podoplel24.01.2023 12:07
-
Михаил194625.04.2021 00:55
-
MariaRosengard06.03.2022 10:24
-
KristinaPanpi413.08.2020 01:07