3) нарисуем путь Робота, который выполнил программу 323341:
? | ? | ? | ? | ? | ? |
? |
| ? | ? | ? | |
? | ? | ? | |||
? | ? | ? | ? | ||
? | ? | ? | ? | ? | ? |
Робот начал движение из клетки, отмеченной красной точкой, и закончил в клетке, где стоит синяя точка
4) чтобы вернуться в исходную клетку (с красной точкой) по пройденному пути, Роботу нужно сделать шаг влево (команда 4), затем шаг вверх (команда 1) и еще один шаг влево (команда 4)
5) таким образом, ответ – 414.
Еще пример задания:
Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:
вправо
вверх
влево
влево
вниз
вниз
вправо
вправо
вправо
вниз
влево
Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.
Решение (способ 1, моделирование движения Робота):
1) отметим, что в условии ничего не говорится о стенках, то есть, молчаливо предполагаем, что их нет
2) можно повторить все движения Робота на бумажке и посмотреть, куда он уйдет; на схеме исходная точка обозначена красной точкой, а конечная – синей, синяя линия показывает путь Робота:
| ||||
| ||||
3) поскольку Робот не может ходить по диагонали, для перехода из начальной точки в конечную кратчайшим путем ему нужно выполнить, например, такую программу (см. штриховые линии на рисунке):
вниз вниз вправо |
4) есть и другие варианты (попробуйте их найти!), но все они содержат 3 команды: одну команду вправо и две команды вниз
5) таким образом, ответ – 3.
Решение (способ 2, анализ программы):
1) можно решить задачу без повторения движений Робота
2) обратим внимание, что пары команд «вперед-назад» и «влево-вправо» дают нулевой эффект, то есть, не перемещают Робота, поэтому все такие пары можно выкинуть из программы
3) поскольку стенок нет, все равно где стоят парные команды в программе, вычеркиваем их:
вправо
вверх
влево
влево
вниз
вниз
вправо
вправо
вправо
вниз
влево
4) смотрим, какие команды остались (они отмечены желтым маркером), их всего 3
5) таким образом, ответ – 3.
Еще пример задания:
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 4 – Кузнечик прыгает вперед на 4 единицы,
Назад 3 – Кузнечик прыгает назад на 3 единицы.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 27?
Решение (составление уравнения, подбор решения):
1) обозначим через 
количество команд «Вперед 4» в программе, а через 
– количество команд «Назад 3»
2) для того, чтобы КУЗНЕЧИК попал в точку 27 из точки 0, должно выполняться условие
3) это уравнение называется диофантовым; поскольку числа 4 и 3 – взамнопростые (их наибольший общий делитель равен 1), оно имеет бесконечно много решений
4) из всех решений нас интересует такое, при котором 
– наименьшее возможное неотрицательное (!) число
5) представим уравнение в виде
нужно подобрать минимальное неотрицательное , при котором правая часть делится на 4
6) дальше используем метод подбора (или перебора), начиная от 1; получаем
7) видим, что первое , при котором 
делится на 4, это 
(при этом 
).
8) таким образом, ответ – 3.
Задачи для тренировки[3]:
1) У исполнителя Утроитель две команды, которым присвоены номера:
1. вычти 2
2. умножь на три
Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 – это программа:
умножь на три
вычти 2
умножь на три
вычти 2
вычти 2,
которая преобразует число 2 в 8). (Если таких программ более одной, то запишите любую из них.)
2) У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2
2. умножь на 3
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа 21211 – это программа:
умножь на 3
прибавь 2
умножь на 3
прибавь 2
прибавь 2,
которая преобразует число 1 в 19).
3) У исполнителя УТРОИТЕЛЬ две команды, которым присвоены номера:
1. вычти 1
2. умножь на 3
Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза.
Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.
(Например, программа 21211 это программа
умножь на 3
вычти 1
умножь на 3
вычти 1
вычти 1
которая преобразует число 1 в 4.)
4) Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:
Вперед N (Кузнечик прыгает вперед на N единиц);
Назад M (Кузнечик прыгает назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?
5) Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:
1. Умножь на 2
2. Вычти 2
Выполняя команду номер 1, КАЛЬКУЛЯТОР умножает число на экране на 2, а выполняя
команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не
более 5 команд, которая из числа 7 получает число 44. Укажите лишь номера команд.
Например, программа 11221 – это программа:
Умножь на 2;
Умножь на 2;
Вычти 2;
Вычти 2;
Умножь на 2,
которая преобразует число 5 в число 32.
6) Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:
1. умножь на 3
2. вычти 2
Выполняя команду номер 1, КАЛЬКУЛЯТОР умножает число на экране на 3, а выполняя
команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не
более 5 команд, которая из числа 1 получает число 23. Укажите лишь номера команд.
Например, программа 11221 – это программа:
умножь на 3
умножь на 3
вычти 2
вычти 2
умножь на 3,
которая преобразует число 1 в число 15.
7) Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:
1. Вычти 3
2. Умножь на 2
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
