Решение задач типа 14 ГИА по информатике

Продолжаем подготовку к ГИА по информатике и сегодня мы рассмотрим решение задачи 14. В качестве примера такой задачи возьмем задачу ГИА по информатике 2014 года по материалам ФИПИ.

У исполнителя Делитель две команды, которым присвоены номера:

1. раздели на 2
2. вычти 1

Первая  из  них  уменьшает  число  на  экране  в 2 раза,  вторая  уменьшает  его на 1. Исполнитель работает только с натуральными числами. Составьте алгоритм получения из числа 65 числа 4, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 12112 – это алгоритм:
раздели на 2
вычти 1
раздели на 2
раздели на 2
вычти 1,
который преобразует число 42 в число 4).

Если таких алгоритмов более одного, то запишите любой из них.

Первое, что приходит на ум воспользоваться методом перебора всех вариантов. Но в этом случае есть вероятность запутаться, так как количество вариантов довольно большое. Поэтому, предлагаю графический метод решения.

Итак, запишем исходное число 65 по центру листа:

Решение задач типа 14 ГИА по информатике

По условию у исполнителя всего 2 команды — раздели на 2 и вычти 1. В итоге после выполнения первой команды (из максимально возможных пяти) мы можем получить два числа:

65 /2 = 32,5

65 — 1 = 64

Но так как в условии указано, что Исполнитель работает только с натуральными числами, то число 32,5 мы сразу отбросим — оно не натуральное. Значит у нас получается такая картина:

задача 14 ГИА по информатике — шаг 1

Здесь над стрелочками указаны номера команд. Левая ветвь зачеркнута — число 32,5 натуральным не является. Это существенно облегчает нам дальнейшее решение. Значит рассмотрим только правую ветвь.

На втором шаге мы будем выполнять команды уже над числом 64. Получим такую картину:

задача 14 ГИА по информатике — шаг 2

Продолжаем. На третьем шаге команды необходимо произвести уже с двумя полученными числами — 32 и 63:

задача 14 ГИА по информатике — шаг 3

Здесь мы видим, что число 31,5 опять не удовлетворяет требованию натуральности. Продолжаем. Осталось немного :) Итак, четвертый шаг:

задача 14 ГИА по информатике — шаг 4

Число 15,5 мы сразу отбрасываем. Остался последний шаг! Можно опять отразить его графически:

задача 14 ГИА по информатике — шаг 5

А можно просто посчитать в уме. Мы видим, что нужное число 4 получено. В ответе нам нужно указать последовательность команд. Ее мы легко найдем, пройдя по стрелочкам от исходного числа 65 к полученному 4:

2 1 1 1 1

задача 14 ГИА по информатике — решение

Это и есть правильный ответ.

Не расслабляемся :) Время пролетит незаметно и наступит пора экзаменов. Готовимся и еще раз готовимся! Успехов!