Подготовка к ОГЭ: Задание 14

Тема: Составление линейного алгоритма для исполнителя

Что нужно знать:

• исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

• для нахождения оптимального (самого короткого) алгоритма, преобразующего одно число в другое с помощью заданного набора команд, можно строить дерево возможных вариантов, выясняя, какие результаты в принципе можно получить после одного шага, после двух шагов и т.д.

• иногда построение дерева вариантов лучше вести в обратном порядке, двигаясь от конечного числа к начальному; при этом ответ (последовательность команд алгоритма) выписывается от начального числа к конечному

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

1. прибавь 2

2. умножь на 3

Первая из них увеличивает число на экране на 2, вторая – утраивает его. Запишите порядок команд в алгоритме получения из числа 0 числа 28, содержащем не более 6 команд, указывая лишь номера команд.

(например, 21211 - это алгоритм

умножь на 3

прибавь 2

умножь на 3

прибавь 2

прибавь 2

который преобразует число 1 в число 19.)

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

1. прибавь 3

2. умножь на 2

Первая из них увеличивает число на экране на 3, вторая – удваивает его. Запишите порядок команд в алгоритме получения из числа 1 числа 47, содержащем не более 6 команд, указывая лишь номера команд.

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

1. прибавь 3

2. умножь на 4

Первая из них увеличивает число на экране на 3, вторая – умножает его на 4. Запишите порядок команд в алгоритме получения из числа 3 числа 57, содержащем не более 5 команд, указывая только номера команд.

1. У исполнителя Квадратор две команды, которым присвоены номера:

1. возведи в квадрат

2. прибавь 1

Первая из них возводит число на экране в квадрат, вторая – увеличивает его на 1. Запишите порядок команд в алгоритме получения из числа 1 числа 10, содержащем не более 4 команд, указывая лишь номера команд.

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

1. вычти 1

2. умножь на 3

Первая из них уменьшает число на экране на 1, вторая – утраивает его. Запишите порядок команд в алгоритме получения из числа 5 числа 26, содержащем не более 5 команд, указывая лишь номера команд.

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

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

1. вычти 2

2. умножь на 3

Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в алгоритме получения из числа 11 числа 13, содержащем не более 5 команд, указывая лишь номера команд.

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

1. У исполнителя Конструктор две команды, которым присвоены номера:

1. приписать 2

2. разделить на 2

Первая из них приписывает к числу на экране справа цифру 2, вторая – делит его на 2. Запишите порядок команд в алгоритме получения из числа 1 числа 16, содержащем не более 5 команд, указывая только номера команд

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

1. У исполнителя Арифметик две команды, которым присвоены номера:

1. прибавь 2,

2. умножь на 3.

Первая из них увеличивает число на экране на 2, вторая - утраивает его. Запишите порядок команд в алгоритме преобразования числа 3 в число 69, содержащем не более 5 команд, указывая лишь номера команд.

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

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

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

Исполнитель работает только с натуральными числами. Составьте алгоритм получения из числа 17 числа 5 содержащий не более 5 команд. В ответе запишите только номера команд.

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

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

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

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

№3

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

1. прибавь 3

2. умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.

Решение (вариант 1, «прямой ход»):

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

2. начнем решать задачу, «отталкиваясь» от начального числа

3. на первом шаге с помощью имеющихся команд из числа 3 можно получить 6 или 12;

4. на втором шаге из 6 можно получить 9 и 24, а из 12 – 15 и 48, и т.д., получается такая схема (структура «дерево»), цифры около стрелок показывает номер выполненной команды:

1. уже чувствуется, что дерево сильно разрастается, на следующем уровне будет уже 8 вариантов, потом – 16 и т.д. (на каждом следующем уровне – в 2 раза большем, чем на предыдущем)

2. нужно выбрать такой план дальнейшего перебора вариантов, который может быстрее всего привести к цели (числу 57)

3. видим, что после второй операции ближе всего к результату оказалось число 48, попробуем начать анализ с этой ветки; если не получится – возьмем число 24 и т.д.

4. ветка дерева, начиная от числа 48, построена на рисунке справа; красный крестик показывает, что полученное значение превышает 57

5. итак, мы вышли на число 57 в результате такой последовательности команд: 22111, ее длина равна 5, что удовлетворяет условию задачи.

6. таким образом, правильный ответ – 22111.