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




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

Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

 

1. прибавь 1

2. умножь на 2

 

Выполняя команду номер 1, КАЛЬКУЛЯТОР прибавляет к числу на экране 1, а выполняя

команду номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 19 число 629.

Решение.

Умножение на число обратимо не для любого числа, поэтому, если мы пойдём от числа 629 к числу 19, тогда однозначно восстановим программу с минимальным числом команд. Полученные команды будут записываться справа налево.

 

1) Число 629 не делится на 2, значит, оно получено прибавлением единицы к числу 628: 629 = 628 + 1 (команда 1).

 

2) Т. к. мы хотим получить минимальное число команд, то для получения числа 628 нужно использовать умножение: 628 = 314 * 2 (команда 2).

 

Далее, если число чётное, применяем рассуждение 2), если нечётное — рассуждение 1), поэтому:

 

314 = 157 * 2 (команда 2);

157 = 156 + 1 (команда 1);

156 = 78 * 2 (команда 2);

78 = 39 * 2 (команда 2);

39 = 38 + 1 (команда 1);

38 = 19 * 2 (команда 2).

 

Считаем количество команд и получаем ответ: 8.