СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




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

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

 

1. прибавь 1

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

 

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ – это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 27, причём траектория вычислений не содержит число 26? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 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 = 26 или (i-1)/2 = 26, то оно не учитывается. Можно заметить, что для числа 27 будет формула dp[27]=dp[26] + dp[13], а поскольку dp[26] не считается, то ответ совпадает с dp[13].

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

 

Ответ: 13.

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