ГДЗ по информатике, 11 класс, Босова, номер p131.8

План решения:

Задача относится к классу задач на подсчёт количества путей в графе состояний. Исполнитель «Калькулятор» имеет две команды: +1 и ×2. Нам нужно найти количество различных последовательностей команд (программ), которые переводят начальное число 1 в конечное число 20. Для этого удобно использовать метод динамического программирования или рекурсивный подсчёт с запоминанием результатов для каждого числа от 1 до 20. Обозначим N(x) — количество программ, переводящих число 1 в число x.

Вычисление пункта 1:

Чтобы попасть в число x, мы могли прийти из числа x-1 (команда +1) или из числа x/2 (команда ×2, если x чётное). Следовательно, справедлива рекуррентная формула: N(x)=N(x-1)+{N(x/2),если x чётное0,если x нечётное Начальное условие: N(1)=1 (пустая программа или старт). Посчитаем значения по порядку:

• N(1)=1
• N(2)=N(1)+N(1)=1+1=2 (пути: 1→2 через ×2; 1→1→2? Нет, команда +1 из 1 даёт 2. Путь 1+12 и 1×22. Всего 2.)
• N(3)=N(2)=2 (только из 2 через +1)
• N(4)=N(3)+N(2)=2+2=4
• N(5)=N(4)=4
• N(6)=N(5)+N(3)=4+2=6
• N(7)=N(6)=6
• N(8)=N(7)+N(4)=6+4=10
• N(9)=N(8)=10
• N(10)=N(9)+N(5)=10+4=14
• N(11)=N(10)=14
• N(12)=N(11)+N(6)=14+6=20
• N(13)=N(12)=20
• N(14)=N(13)+N(7)=20+6=26
• N(15)=N(14)=26
• N(16)=N(15)+N(8)=26+10=36
• N(17)=N(16)=36
• N(18)=N(17)+N(9)=36+10=46
• N(19)=N(18)=46
• N(20)=N(19)+N(10)=46+14=60

Вычисление пункта 2:

Нам нужно найти количество программ, где промежуточным результатом обязательно является число 15. Это означает, что путь разбивается на два независимых участка: 1→15 и 15→20. Количество таких программ равно произведению количества способов добраться до 15 и количества способов добраться от 15 до 20. Количество способов 1→15 уже найдено: N(15)=26. Теперь найдём количество способов 15→20. Пусть M(y) — количество программ, переводящих 15 в y. Аналогично предыдущему пункту, но стартуем с 15 (M(15)=1):

• M(15)=1
• M(16)=M(15)=1 (только +1, так как 16/2=8<15, а мы идём только вверх)
• M(17)=M(16)=1
• M(18)=M(17)+M(9)? Нет, правило перехода назад: чтобы попасть в y, можно прийти из y-1 или y/2. Но мы считаем пути от 15. Проще считать обратным ходом от 20 до 15 или прямым перебором малых чисел. Давайте посчитаем K(a,b) — число путей от a до b. Здесь a=15,b=20. Пути от 15: 1. 15+116+117+118+119+120 (1 путь) 2. 15+116+117+118×236 (перебор, не подходит) 3. 15+116×232 (перебор) 4. 15×230 (перебор) Похоже, я усложнил. Вернёмся к формуле N(x), но с ограничением, что мы должны пройти через 15. Число путей 1→20 через 15 равно N(15)×P(15→20), где P(15→20) — число путей от 15 до 20. Рассмотрим все возможные пути от 15 до 20. Максимальное число команд мало. Из 15 можно сделать +1 (получим 16) или ×2 (получим 30, что больше 20, значит этот ход запрещён, если мы хотим попасть точно в 20 без выхода за пределы? В задаче обычно подразумевается, что промежуточные результаты могут быть любыми, но финальный должен быть 20. Однако, если мы умножим 15 на 2, получим 30. Из 30 нельзя вернуться в 20 командами +1 или ×2. Значит, из 15 единственный возможный первый шаг — это +1. Итак, обязательный шаг: 15→16. Теперь задача сводится к количеству путей от 16 до 20. От 16 можно пойти +1→17 или ×2→32 (тупик). Значит, обязательный шаг: 16→17. От 17 можно пойти +1→18 или ×2→34 (тупик). Значит, обязательный шаг: 17→18. От 18 можно пойти +1→19 или ×2→36 (тупик). Значит, обязательный шаг: 18→19. От 19 можно пойти +1→20 или ×2→38 (тупик). Значит, обязательный шаг: 19→20. Таким образом, существует ровно 1 путь от 15 до 20: 15→16→17→18→19→20. Общее количество программ для пункта 2: 26×1=26.

  Вычисление пункта 3:

  Нужно найти количество программ, где промежуточным результатом никогда не получается число 12. Это эквивалентно общему количеству всех программ минус количество программ, которые проходят через число 12. Количество программ, проходящих через 12, равно произведению N(12)×P(12→20). Мы знаем N(12)=20. Найдём P(12→20) — количество путей от 12 до 20. Составим таблицу путей от 12 (Q(x) — число путей от 12 до x): Q(12)=1 Q(13)=Q(12)=1 (из 12 только +1, т.к. ×2→24>20) Q(14)=Q(13)+Q(7)? Нет, считаем прямо. Давайте проще: какие ходы возможны из чисел ≥12? Если текущее число x≥11, то x×2≥22>20. Значит, начиная с числа 11, команда ×2 ведёт в тупик (нельзя вернуться к 20). Следовательно, все пути от 12 до 20 должны состоять исключительно из команд +1. Единственный путь: 12→13→14→15→16→17→18→19→20. Значит, P(12→20)=1. Количество «плохих» программ (проходящих через 12): 20×1=20. Количество «хороших» программ (не проходящих через 12): N(20)-20=60-20=40.

  Проверка:

  Пересчитаем N(20) аккуратно, чтобы убедиться в отсутствии ошибок. N(1)=1 N(2)=2 N(3)=2 N(4)=4 N(5)=4 N(6)=6 N(7)=6 N(8)=10 N(9)=10 N(10)=14 N(11)=14 N(12)=20 N(13)=20 N(14)=26 N(15)=26 N(16)=36 N(17)=36 N(18)=46 N(19)=46 N(20)=60 Расчёты верны. Для пункта 2: путь 15→20 уникален, так как любое умножение на 2 после 10 (кроме случаев, когда результат ≤20) приводит к числу >20 или требует возврата, которого нет. От 15 до 20 только сложения. 26×1=26. Верно. Для пункта 3: исключаем пути через 12. Пути через 12: N(12)×1=20. 60-20=40. Верно.