§ 6. Достижимые цели

Обычно никто не составляет алгоритмы просто так: как правило, алгоритмы служат для решения какой-либо задачи, для достижения какой-либо цели. Допустим, вы выбрали исполнителя для решения некоторого класса задач. Но тогда сразу встает вопрос, может ли имеющийся в вашем распоряжении исполнитель решить поставленную задачу. Чтобы уметь отвечать на такой вопрос, надо знать, какие цели достижимы тем или иным исполнителем, то есть какие результаты он может получить с помощью своих допустимых действий.

Алгоритм не роскошь, а средство достижения цели

Как правило, задача определения всех достижимых целей исполнителя весьма сложна. Поэтому давайте рассмотрим простого исполнителя, который может передвигаться по бумаге, рисуя линии. Назовем его ЧЕРТЕЖНИК. Будем изображать направление движения ЧЕРТЕЖНИКА стрелкой. Пишущий узел находится в начале стрелки. Для ЧЕРТЕЖНИКА допустимы всего два действия:

1) пройти 1 см в направлении стрелки, рисуя линию (рис. 8, а);

2) повернуться на 90° влево вокруг начала стрелки (рис. 8,б).

Рис. 8. Чертежик

Будем считать, что первое действие ЧЕРТЕЖНИК выполняет по команде "Сделать шаг", а второе действие - по команде "Повернуть налево".

Давайте с помощью ЧЕРТЕЖНИКА нарисуем линию, изображенную на рисунке 9. Длина каждого отрезка равна 1 см. Начальное положение ЧЕРТЕЖНИКА указано стрелкой. Приведем алгоритм, с помощью которого решается эта задача:

 Повернуть налево. 
 Сделать шаг. 
 Повернуть налево. 
 Сделать шаг. 
 Повернуть налево. 
 Сделать шаг.

А рисунок 10 он начертить не сможет.

Рис. 9. Чертежик

Рис. 10. Чертежик

Ясно, что ЧЕРТЕЖНИК вообще не может изображать разрывные линии. А какие рисунки он может изобразить? Другими словами, какие цели достижимы для ЧЕРТЕЖНИКА? Ответ несложен: ЧЕРТЕЖНИК может рисовать только непрерывные ломаные, у которых длины звеньев целочисленны и все углы прямые.

Что надо сделать, чтобы ЧЕРТЕЖНИК смог рисовать разрывные линии? Ясно, что для этого надо увеличить набор допустимых Действий. Например, добавить в список команд ЧЕРТЕЖНИКА команду "Прыгнуть", по которой он делает шаг длины 1 см, не рисуя линии. Теперь можно составить алгоритм рисования, например, фигуры, изображенной на рисунке 10.

 Повернуть налево. 
 Сделать шаг. 
 Повернуть налево. 
 Сделать шаг. 
 Повернуть налево. 
 Сделать шаг. 
 Повернуть налево. 
 Повернуть налево. 
 Повернуть налево. 
 Прыгнуть. 
 Повернуть налево. 
 Повернуть налево. 
 Повернуть налево. 
 Сделать шаг. 
 Повернуть налево. 
 Сделать шаг. 
 Повернуть налево. 
 Сделать шаг.

В дальнейшем мы будем считать, что ЧЕРТЕЖНИК умеет выполнять команду "Прыгнуть".

Вопросы

1. Что называется достижимыми целями исполнителя?

2. Каковы допустимые действия ЧЕРТЕЖНИКА?

Задания для самостоятельного выполнения

1. Какие из этих линий (рис. 11) может нарисовать ЧЕРТЕЖНИК?

Рис. 11. Чертежик

2. Напишите для ЧЕРТЕЖНИКА алгоритмы, выполнив которые он нарисует заданные фигуры (рис. 12):

Рис. 12. Чертежик

3. Какие цели достижимы для ЧЕРТЕЖНИКА, умеющего выполнять лишь следующие действия:

а) "Сделать шаг" и "Прыгнуть";

б) "Прыгнуть" и "Повернуть налево";

в) "Повернуть налево".

4. ЧЕРТЕЖНИК - 30 и ЧЕРТЕЖНИК - 45 очень похожи на обычного ЧЕРТЕЖНИКА. Единственное отличие состоит в том, как они понимают команду ПОВЕРНУТЬ НАЛЕВО. По этой команде ЧЕРТЕЖНИК - 30 поворачивается на 30°, а ЧЕРТЕЖНИК - 45 - на 45° против часовой стрелки. Какого из этих двух ЧЕРТЕЖНИКОВ вы предпочтете для рисования следующих фигур:

а) квадрат со стороной 1 см;

б) правильный шестиугольник со стороной 1 см;

в) правильный восьмиугольник со стороной 1 см;

г) отрезок длины 5 см.

5. Для каждого натурального N создан ЧЕРТЕЖНИК - N, который по команде ПОВЕРНУТЬ НАЛЕВО поворачивается на угол № против часовой стрелки. Найти такое N, что для ЧЕРТЕЖНИКА - N достижима каждая из двух целей: "нарисовать правильный десятиугольник" и "нарисовать квадрат". Для какого N суммарное число действий в алгоритмах рисования этих фигур наименьшее?

6. Предположим, что в условии задачи 10 из § 4 вместо трехлитрового кувшина дан двухлитровый. Можно ли теперь набрать 7 литров?

7. Даны три листа бумаги. Исполнитель берет лист, разрезает его на четыре части и кладет их обратно. Какое количество листов может получиться в результате его работы?

8*. На доске написаны числа 1, 2, 3, ..., n. Исполнитель может стереть два числа и записать вместо них абсолютную величину их разности. Через n - 1 шаг на доске останется одно число. Цель - получить число 0. Для каких п эта цель достижима?

9. Какими допустимыми действиями вы снабдили бы автомат, заменяющий:

а) кассира в магазине;

б) дворника;

в) вахтера;

г) директора школы?

10. Можно ли создать исполнителя, который все может?