≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 22 № 13471

Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:

1. прибавь 1

2. сделай нечётное

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Пояснение.

Используем метод динамического программирования. Заведем массив dp, где dp[i] — количество способов получить число i с помощью таких команд.

База динамики:

dp[1]=1;

Формула перехода:

dp[i]=dp[i-1] - если i - четное.

dp[i]=dp[i-1] + dp[(i-1)/2] - если i нечетное;

Но при этом если i-1 = 24 или (i-1)/2 = 24, то его не учитываем. Можно заметить, что для числа 25 будет формула

dp[25]=dp[24] + dp[12], а т.к. dp[24] не считаем, то ответ совпадает с dp[12].

Посчитаем dp[13] (далее будет приведены значения в ячейках dp от 1 до 12): 1 1 2 2 3 3 5 5 7 7 10 10.

 

 

Ответ: 10.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304