uzluga.ru
добавить свой файл
1

АЛГОРИТМИКА. Часть 1.


ЗАДАЧА 1. "Волк, коза и капуста".


Крестьянин стоит на левом берегу реки с волком, козой и капустой.

Ему нужно перевезти все это ни правый берег,


Но его лодка слишком мала: он может взять только одного пассажира
— либо волка, либо козу, либо капусту. И еще — если на одном берегу
оставить волка и козу, то волк съест козу, а если оставить козу и
капусту, то коза съест капусту. Только в присутствии крестьянина
они не безобразничают, Как тут поступить?


Одно из важнейших понятий алгоритмики — Исполнитель. Исполнитель— это человек или механическое
устройство или, скажем, компьютер со строго определённым набором возможных операций. Эти операции называются командами. Исполнитель может исполнять команды из набора, и ничего более. В пашей задаче крестьянин был Исполнителем, а его набор команд состоял из четырех операций.

Решение:

перевези козу

переправься

перевези волка

перевези козу

перевези капусту

переправься

перевези козу

Упражнение

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


Алгоритмы "ВОДОЛЕЕВ"

Задача "Водолей 1": имеет две банки А – 2 литра, В – 3 литра.

Задача – отмерить литр.

Решение:

наполни В
перелей из В в А
.

Выпишем все команды Водолея с двумя ведрами (банками, ёмкостями):

наполни А

наполни В

вылей из А

вылей из В

перелей из А в В

перелей из В в А

Обычно в начале каждой задачи все ведра пусты. Наша цель получить (отмерить) требуемое количество воды в одной из емкостей, причем неважно, в какой именно и сколько воды будет при этом в остальных ведрах,

Задача для "Водолея 2": А – 3 литра, В – 5 литра

Отмерьте 1 литр воды с помощью одной 3-литровой и одной 5-литровой банки.

Задача для "Водолея 3": Имеетпся 5-литровая емкость А и 8-литровая емкостпь В. а) Отмерьте 1 литр воды.

б) Отпмерьте 4 литра воды

Алгоритмы "УДВОИТЕЛЬ"

Если, например, на экране было число 7 и мы нажали клавишу прибавь 1, то число 7 пропадает, а вместо него появляется число 8. Если же нажать клавишу умножь на 2, то вместо числа 7 появится число 14.

В нашем представлении Удвоитель является исполнителем с двумя командами:

прибавь 1

умножь на 2

Задача 1 для Удвоителя.. Давайте получим на экране число 17. (Начнем с О.) Вот две возможные программы, выполняющие это задание:

прибавь 1

умножь на 2

умножь на 2

умножь на 2

умножь на 2

умножь на 2

прибавь 1

прибавь 1

прибавь 1

прибавь 1

…………… 17 раз!

прибавь 1

прибавь 1

прибавь 1

прибавь Ф

прибавь 1

Какая из этих программ вам больше нравится? Почему? Упражнение

Задача 2 для Удвоителя

Как вы думаете, можно ли получить на экране любое положительное целое число? Объясните свой ответ.

Устройте такое соревнование: кто-нибудь называет число, и все пытаются его получить. Выигрывает тот, кто напишет программу с наименьшим числом шагов.


Задачи:

а) Получи число 15 меньше чем за 8 шагов

б)Получи число 1024

в) На экране написано число 4. Получи из него число 15 меньше чем за 6 шагов.

^ Алгоритмы исполнителя "КУЗНЕЧИК"

Нарисуем горизонтальную прямую и нанесем на нее квадратные метки на равном расстоянии друг от друга (рис. 1.1). Метки отмечают точки на прямой. Одну из точек обозначим числом О. Точки справа от нее обозначим числами 1, 2, 3, 4 и так далее, а точки слева — числами — 1, — 2, — 3, — 4... Такую прямую будем называть числовой осью, На числовой оси живет Исполнитель Кузнечик. На рисунке 1.1 (и далее) он обозначен буквой К.




В начальный момент Кузнечик находится в точке О числовой оси. Он может прыгать на 3 единицы вперед (рис. 1.2) и на 2 единицы назад (рис. 1.3), Таким образом, список его команд содержит только две строчки:




а рисунке 1.4 показано, как прыгал Кузнечик, выполняя такую программу:

вперед 3

вперед 3

назад 2

назад 2

назад 2




Упражнение

1) Переведитпе Кузнечика из точки О в точку 7.

2) Переведитпе Кузнечиха из точки О в точку 2.


Задача 1. У Кости есть только монеты достоинством 3 копа, а у Димы — только 2-хкоповые. Костя должен Диме 7 копов. Как ему расплатиться?

Связана ли эта задача как-нибудь с Кузнечиком?

Задача 2 Заставьте Кузнечика побывать по одному разу в каждой из точек 1, 2, 3, 4, 5, не выходя 'за пределы отрезка от 0 до 5.

Задача 3 Кузнечик начал выполнение программы в точке 0 и закончил в точке 2. Затем та же программа была выполнена еще раз. Где теперь оказался Кузнечик?

Задача 4 Может ли Кузнечик добраться до любой точки на прямой? Как? (Разумеется, мы спрашиваем только про точки, соответствующие целым числам, а не про дроби.)

Задача 5 Поменяем немножко список команд Кузнечика. Конечно, изменение списка команд, даже самое маленькое, означает, что мы получили другого Исполнителя. Но мы все равно будем называть его Кузнечиком. Новый список для этого Кузнечика состоит также из двух команд:


вперед 7

назад 5

Может ли новый Кузнечик добраться до любой точки прямой, например до точки 1?

Как вы уже заметили, у нас было много разных Водолеев, отличающихся числом емкостей и их объемами. Точно так же нам придется иметь дело с различными Кузнечиками: они будут совершать разные прыжки вперед и назад.


6. ОТКАЗ

Не всякую команду можно исполнить в любой ситуации. Для того чтобы команда была выполнима, нужны особые условия. Представим себе, что наша программа для Крестьянина начинается со строчек

перевези козу

перевези волка

Но на правом берегу еще нет волка, поэтому перевезти его через реку невозможно. В таком случае выполнение программы останавливается. Эту невозможность выполнить команду мы называем ОТКАЗ.

Та же ситуация возникает и при игре в шахматы, когда мы указываем какой-нибудь фигуре перейти с одного поля на другое, а на первом поле этой фигуры нет.

Нарушение другого рода происходит, когда волк остаётся с козой без Крестьянина: такое положение противоречит условиям игры.

В шахматах то же самое случается, если, например, король не уходит из-под шаха,