Поиск алгоритма минимальной длины для исполнителя B2 (базовый уровень, время – 4 мин) - презентация

1 Поиск алгоритма минимальной длины для исполнителя B2 (базовый уровень, время – 4 мин)

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

3 Решение «обратный ход» нам нужно увеличить число (с 3 до 57), для этого в большинстве случаев умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях попробуем решить задачу «обратным ходом», начав с числа 57; очевидно, что последней командой не может быть умножение на 4 (57 на 4 не делится), поэтому последняя команда – сложение (прибавь 3), над стрелкой записан номер команды: число 54 также не делится на 4, поэтому предыдущая команда – тоже сложение: аналогично для числа 51: число 48 делится на 4, поэтому используем умножение: наконец, добавив в начало программы еще одно умножение, получаем полную цепочку: таким образом, правильный ответ – 22111, эта программа состоит из 5 команд.

4 Самостоятельное решение Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера: Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера: Вычти 1 Умножь на 2 Выполняя команду номер 1, КАЛЬКУЛЯТОР вычитает из числа на экране 1, а выполняя команду номер 2, умножает число на экране на 2. Напишите программу, содержащую не более 4 команд, которая из числа 13 получает число 100. Укажите лишь номера команд. Выполняя команду номер 1, КАЛЬКУЛЯТОР вычитает из числа на экране 1, а выполняя команду номер 2, умножает число на экране на 2. Напишите программу, содержащую не более 4 команд, которая из числа 13 получает число 100. Укажите лишь номера команд. Например, программа – это программа: Например, программа – это программа: Умножь на 2 Вычти 1 Умножь на 2 Вычти 1 которая преобразует число 2 в число 4. которая преобразует число 2 в число 4. Ответ 2122

5 Задание 2 У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера: У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера: 1. сдвинь влево 2. вычти 1 Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд Запишите результат в десятичной системе. Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд Запишите результат в десятичной системе.

6 Решение Фактически команда сдвинь влево означает умножь на 2 Фактически команда сдвинь влево означает умножь на 2 При умножении на 2, если число больше 256, то должен быть переход в высший разряд, для этого мы от произведения отнимем 256. При умножении на 2, если число больше 256, то должен быть переход в высший разряд, для этого мы от произведения отнимем 256. Рассмотрим последовательность команд в таблице: Рассмотрим последовательность команд в таблице: Код команды ДействиеРезультатПримечание умножь на Умножь на 2, вычте вычти Умножь на 2, вычте умножь на 2 60

7 Самостоятельное решение У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера: У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера: 1. сдвинь влево 2. вычти 1 Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд Запишите результат в десятичной системе. Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд Запишите результат в десятичной системе. Ответ: 171

8 Задание 3 Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды: Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды: 1 (вверх), 2 (вниз), 3 (вправо) 4 (влево), 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле? Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?

9 Решение чтобы не разрушиться на обратном пути, Робот должен идти точно по тому же пути в обратном направлении чтобы не разрушиться на обратном пути, Робот должен идти точно по тому же пути в обратном направлении нарисуем путь Робота, который выполнил программу : нарисуем путь Робота, который выполнил программу : Робот начал движение из клетки, отмеченной красной точкой, и закончил в клетке, где стоит синяя точка чтобы вернуться в исходную клетку (с красной точкой) по пройденному пути, Роботу нужно сделать шаг влево (команда 4), затем шаг вверх (команда 1) и еще один шаг влево (команда 4) ответ – 414

10 Самостоятельное решение Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле? Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле? Ответ 142

11 Задание 4 Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу: Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:вправовверхвлевовлевовнизвнизвправовправовправовнизвлево Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную. Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.

12 Решение отметим, что в условии ничего не говорится о стенках, то есть, молчаливо предполагаем, что их нет отметим, что в условии ничего не говорится о стенках, то есть, молчаливо предполагаем, что их нет можно повторить все движения Робота на бумажке и посмотреть, куда он уйдет; на схеме исходная точка обозначена красной точкой, а конечная – синей, синяя линия показывает путь Робота: можно повторить все движения Робота на бумажке и посмотреть, куда он уйдет; на схеме исходная точка обозначена красной точкой, а конечная – синей, синяя линия показывает путь Робота: поскольку Робот не может ходить по диагонали, для перехода из начальной точки в конечную кратчайшим путем ему нужно выполнить, например, такую программу (см. штриховые линии на рисунке): поскольку Робот не может ходить по диагонали, для перехода из начальной точки в конечную кратчайшим путем ему нужно выполнить, например, такую программу (см. штриховые линии на рисунке): Вниз, вниз, вправо, есть и другие варианты (попробуйте их найти!), но все они содержат 3 команды: одну команду вправо и две команды вниз Вниз, вниз, вправо, есть и другие варианты (попробуйте их найти!), но все они содержат 3 команды: одну команду вправо и две команды вниз ответ – 3

13 Самостоятельное решение Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу: Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу: влево вверх вверх влево вниз вправо вправо вправо Укажите наименьшее возможное число команд в программе, Робота из той же начальной клетки в ту же конечную. Укажите наименьшее возможное число команд в программе, Робота из той же начальной клетки в ту же конечную. Ответ: 2

14 Задание 5 Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика: Вперед 4 – Кузнечик прыгает вперед на 4 единицы, Вперед 4 – Кузнечик прыгает вперед на 4 единицы, Назад 3 – Кузнечик прыгает назад на 3 единицы. Назад 3 – Кузнечик прыгает назад на 3 единицы. Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 27?

15 Решение (составление уравнения, подбор решения): обозначим через Х количество команд «Вперед 4» в программе, а через У – количество команд «Назад 3». обозначим через Х количество команд «Вперед 4» в программе, а через У – количество команд «Назад 3». для того, чтобы КУЗНЕЧИК попал в точку 27 из точки 0, должно выполняться условие для того, чтобы КУЗНЕЧИК попал в точку 27 из точки 0, должно выполняться условие это уравнение называется диофантовым; поскольку числа 4 и 3 – взамнопростые (их наибольший общий делитель равен 1), оно имеет бесконечно много решений. это уравнение называется диофантовым; поскольку числа 4 и 3 – взамнопростые (их наибольший общий делитель равен 1), оно имеет бесконечно много решений. из всех решений нас интересует такое, при котором – наименьшее возможное неотрицательное (!) число из всех решений нас интересует такое, при котором – наименьшее возможное неотрицательное (!) число представим уравнение в виде представим уравнение в виде нужно подобрать минимальное неотрицательное, при котором правая часть делится на 4 нужно подобрать минимальное неотрицательное, при котором правая часть делится на 4 дальше используем метод подбора (или перебора), начиная от 1; получаем дальше используем метод подбора (или перебора), начиная от 1; получаем видим, что первое, при котором делится на 4, это видим, что первое, при котором делится на 4, это (при этом ). (при этом ). ответ – 3.

16 Самостоятельное решение Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика: Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика: Вперед 5 – Кузнечик прыгает вперёд на 5 единиц, Назад 3 – Кузнечик прыгает назад на 3 единицы. Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 21? Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 21? Ответ 3

17 Самостоятельное решение Исполнитель КВАДРАТОР имеет только две команды, которым присвоены номера: Исполнитель КВАДРАТОР имеет только две команды, которым присвоены номера: Возведи в квадрат Прибавь 1 Выполняя команду номер 1, КВАДРАТОР возводит число на экране в квадрат, а выполняя Выполняя команду номер 1, КВАДРАТОР возводит число на экране в квадрат, а выполняя команду номер 2, прибавляет к этому числу 1. Напишите программу, содержащую не команду номер 2, прибавляет к этому числу 1. Напишите программу, содержащую не более 4 команд, которая из числа 2 получает число 36. Укажите лишь номера команд. более 4 команд, которая из числа 2 получает число 36. Укажите лишь номера команд. Например, программа – это программа: Например, программа – это программа: Возведи в квадрат Прибавь 1 Возведи в квадрат Прибавь 1 которая преобразует число 1 в число 6. которая преобразует число 1 в число 6. Ответ: 1221

18 Самостоятельное решение Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды: Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды: Сместиться на вектор (а, Ь) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали. Сместиться на вектор (а, Ь) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали. Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз. Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз. Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм: Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм: Сместиться на вектор (5,2) Сместиться на вектор (-3, 3) Повторить 3 [Сместиться на вектор (1,0)] Сместиться на вектор (3, 1) На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма? На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма? Ответ: 10