@Doublench

Программы исполнителя:
1. умножить число на 5;
2. прибавить к числу 1.
Программа для исполнителя записывается как строка из цифр 1 и 2.
Найдите количество различных программ, которые позволяют из числа 1 получить число 101.

Как такое решить ? Ведь получается уйма различных вариантов ? Как подсчитать ? Или я чего не понял ...

0

@кот Бегемот

Эта задача решается с помощью динамического программирования. Легче всего это понять с помощью таблицы.
Нарисуем таблицу, в которой будет 2 строки и 101 столбец. В принципе, можно обойтись и меньшим количеством столбцов, это станет ясно позднее. Отметим для себя несколько постулатов:
1. Число 1 нам дано, следовательно мы получили его единственным способом.
2. Число, не делящееся на 5 можно получить только из предыдущего числа прибавлением единицы.
3. Число, делящееся на 5 можно получить из предыдущего числа и из числа, которое в 5 раз меньше.

А теперь начнём рисовать таблицу, в которой вверху будут числа от 1 до 101, а в нижней строке - количество способов их получения. Итак, число 1 получено единственным способом (постулат 1):
--------------------------
1|2|3|4|5|6|7|8|9|10|
--------------------------
1|_|_|_|_|_|_|_|_|__|
--------------------------
Число 2 может быть получено только из числа 1, а 1 получен единственным способом, значит, число 2 тоже получено единственным способом.
Аналогично, число 3 можно получить только из числа 2, которое получено единственным способом, значит, число 3 тоже получено единственным способом.
Ну, и 4, разумеется, тоже. Итак:
--------------------------
1|2|3|4|5|6|7|8|9|10|
--------------------------
1|1|1|1|_|_|_|_|_|__|
--------------------------

А вот число 5 можно получить и из числа 4, и из числа 1 (умножением на 5), складываем способы 1+1=2
Согласно постулату 2, числа 6,7, 8,9 также получены двумя способами, а вот 10 получаем одним способом из числа 2 и двумя способами из числа 9 (поскольку оно само получено двумя способами), значит, всего 3 способа.
--------------------------
1|2|3|4|5|6|7|8|9|10|
--------------------------
1|1|1|1|2|2|2|2|2|3_|
--------------------------

Очевидно, что дальше таблица будет заполняться аналогично, изменение будет только для чисел, кратных 5, поэтому сокращённая таблица будет иметь вид:
----------------------------------------------------------------------------------------
1|5|10|15|20|25|30|35|40|45|50|55|60|65|70|75|80|85|90|95|100|101|
----------------------------------------------------------------------------------------
1|2|3_|4_|5_|7_|9_|11|13|15|18|21|24|27|30|34|38|42|46|50|55_|55_|
----------------------------------------------------------------------------------------
Чтобы стало яснее, приведу пример для числа 75: 75 можно получить из 15, умножением на 5 (4 способа) и из 74 прибавлением единицы, но 74,73,72,71 получаются из 70 тридцатью способами, значит, 75 получаем 4+30=34 способа

1

@Doublench

спасибо. гениально.

0