Сборник заданий ЕГЭ по теме "Поиск алгоритма минимальной длины"

Поиск алгоритма минимальной длины

Что нужно знать: каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом исполнитель - это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды.

Алгоритм — это последовательность команд исполнителю, в результате выполнения которой он должен решить поставленную задачу. 

Исполнитель — это человек, компьютер, автоматическое устройство и т.д. Исполнитель должен уметь выполнять все команды, которые записаны в алгоритме. 

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

1. Прибавь 3 

2. Умножь на 4 

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

(Например, программа 21211 это программа, которая преобразует число 2 в 50).

·     Умножь на 4 

·     Прибавь 3 

·     Умножь на 4 

·     Прибавь 3 

·     Прибавь 3 

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

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

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

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

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

                                             1            2

                                                                         1                  2                     1             2

    4              5         8

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

7. Нужно выбрать такой план дальнейшего перебора вариантов,

который может быстрее всего привести к цели (числу 57).

 

                                                                1               8   

 

                                                 1            1

 

                                   1           4

                         7

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

9. Ветка дерева, начиная от числа 48, построена на рисунке.

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

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

Возможные ловушки и проблемы:

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

2.       Не всегда можно сразу угадать нужную ветку «дерева», то есть, ту, которая быстрее всего приведет к успеху.

Решение (вариант 2, «обратный ход»):

1. Нам нужно увеличить число (с 3 до 57), для этого в большинстве случаев умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях

2. Попробуем решить задачу «обратным ходом», начав с числа 57.

3. Очевидно, что последней командой не может быть умножение на 4 (57 на 4 не делится), поэтому последняя команда – сложение (прибавь 3), над стрелкой записан номер команды:

        1

…54         57

4.Число 54 также не делится на 4, поэтому предыдущая команда – тоже сложение:

              1            1

 … 51         54        57

5.   Аналогично для числа 51:

    1             1            1

 …48          51         54        57

6.   Число 48 делится на 4, поэтому используем умножение:
                              2             1            1             1

 …12          48        51         54        57

7.   Наконец, добавив в начало программы еще одно умножение, получаем полную цепочку:

      2               2            1            1             1

3       12          48        51         54        57

8.   таким образом, правильный ответ – 22111, эта программа состоит из 5 команд.

Возможные ловушки и проблемы: Иногда может потребоваться «откат» назад, например, если исходное число – 6, то применив деление на 4 для 12 мы «проскакиваем» его (получаем 12/4=3<6), поэтому нужно возвращаться обратно к 12 и дважды применять сложение; в этом случае ответ будет такой:     1         1         2          1            1          1 6      9     12      48      51      54      57 Возможные ловушки и проблемы: Обратим внимание, что когда мы «шли» в обратном направлении, от конечного числа к начальному, часто очередную операцию удавалось определить однозначно (когда число не делилось на 4). Это связано с тем, что среди допустимых команд есть «не всегда обратимая» операция – умножение: умножить целое число на 4 можно всегда, а разделить нацело – нет; в подобных случаях результат быстрее получается именно «обратным ходом», во время которого сразу отбрасываются невозможные варианты. Пример 2: У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:  1. Сдвинь влево  2. Вычти 1  Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд 11221. Запишите результат в десятичной системе.  Решение: 1. Важно, что числа однобайтовые – на число отводится 1 байт или 8 бит.  2.  Главная проблема в этой задаче – разобраться, что такое «сдвиг влево»; так называется операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса: 7 6 5 4 3 2 1 0 ? 0 0 1 0 1 1 0 1 = 45 0 0 0 1 0 1 1 0 1 0 = 90 Можно доказать, что в большинстве случаев результат этой операции – умножение числа на 2, однако есть исключение: если в старшем (7-ом) бите исходного числа x была 1, она будет «выдавлена» в бит переноса, то есть потеряна 1, поэтому мы получим остаток от деления числа 2x на 28=256 3.   Попутно заметим, что при сдвиге вправо 2 в старший бит записывается 0, а младший «уходит» в бит переноса; это равносильно делению на 2 и отбрасыванию остатка 4.   Таким образом, фактически команда сдвинь влево означает умножь на 2. 5.   Поэтому последовательность команд 11221 выполняется следующим образом. Код команды Действие Результат Примечание 104 1 умножь на 2 208 1 умножь на 2 160 остаток от деления 208*2 на 256 2 вычти 1 159 2 вычти 1 158 1 умножь на 2 60 остаток от деления 158*2 на 256 Ответ:  60. Пример 3: Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика: Вперед 4 – Кузнечик прыгает вперед на 4 единицы, Назад 3 – Кузнечик прыгает назад на 3 единицы. Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 27?  Решение (составление уравнения, подбор решения): 1.    Обозначим через  х - количество команд «Вперед 4» в программе, а через  y– количество команд «Назад 3» 2.    Для того, чтобы КУЗНЕЧИК попал в точку 27 из точки 0, должно выполняться условие 3.    Это уравнение называется диофантовым; поскольку числа 4 и 3 – взамнопростые (их наибольший общий делитель равен 1), оно имеет бесконечно много решений 4.    Из всех решений нас интересует такое, при котором y – наименьшее возможное неотрицательное (!) число 5.    Представим уравнение в виде 6.    Дальше используем метод подбора (или перебора), начиная от 1; получаем 7.     Видим, что первое y, при котором 27+3y  делится на 4, это y=3. Ответ : 3. Задание 1: У исполнителя Утроитель две команды, которым присвоены номера: 1. Вычти 2 2. Умножь на три Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд.  Ответ: 11121 Задание 2: Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика: Вперед 5 – Кузнечик прыгает вперёд на 5 единиц, Назад 3 – Кузнечик прыгает назад на 3 единицы. Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 21? Решение: Обозначим через х количество команд «Вперед 5» в программе, а через у – количество команд «Назад 3», причём  у и х могут быть только неотрицательными целыми числами. Для того, чтобы КУЗНЕЧИК попал в точку 21 из точки 0, должно выполняться условие: 5х-3у=21 5х=21+3у Представим его в виде: Из последнего уравнения видно, что правая часть должна делиться на 5. Из всех решений нас интересует такое, при котором у – наименьшее возможное число. Используя метод подбора находим: у=3. Ответ: 3 Задание 3: Автомат по­лу­ча­ет на вход трёхзначное число. По этому числу стро­ит­ся новое число по сле­ду­ю­щим правилам. 1. Скла­ды­ва­ют­ся пер­вая и вторая, а также вто­рая и тре­тья цифры ис­ход­но­го числа. 2. По­лу­чен­ные два числа за­пи­сы­ва­ют­ся друг за дру­гом в по­ряд­ке убы­ва­ния (без разделителей). Пример. Ис­ход­ное число: 348. Суммы: 3 + 4 = 7; 4 + 8 = 12. Результат: 127. Ука­жи­те наи­мень­шее число, в ре­зуль­та­те об­ра­бот­ки ко­то­ро­го ав­то­мат вы­даст число 1412. Решение: Пусть 12 = 3 + 9, тогда 14 вы­год­но раз­бить на сумму чисел 9 и 5. Наи­мень­шее ис­ход­ное число, удо­вле­тво­ря­ю­щее условиям задачи: 395. Ответ: 395. Задание 4: Исполнитель Робот действует на клетчатой доске, между соседними клетками  которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается.  Робот успешно выполнил программу  2324142 Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?   Ответ: 132

Краткое описание документа:

В сборнике подобраны различные типы заданий из ЕГЭ по теме "Поиск алгоритма минимальной длины".

Что нужно знать: каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом исполнитель - это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды.

Алгоритм — это последовательность команд исполнителю, в результате выполнения которой он должен решить поставленную задачу.

Исполнитель — это человек, компьютер, автоматическое устройство и т.д. Исполнитель должен уметь выполнять все команды, которые записаны в алгоритме.