Как решать задачи "с образцом" и без точки Б?

Два типа задач

Все задачи на разработку алгоритмов для "Стрелочки" можно разделить на два типа:


1) задачи, в которых требуется завершить перемещение "Стрелочки" в заданной точке Б,


2) и задачи, в которых нет точки Б, но есть "образец" – рисунок на поле, который нужно воспроизвести.

Что такое оптимальный алгоритм ? В задачах для самостоятельного решения требуется не просто переместить "Стрелочку" из точки А в точку Б либо повторить заданный рисунок. Требуется разработать оптимальный алгоритм перемещения. Чаще всего, это кратчайший по числу команд алгоритм.
Как получить оптимальный алгоритм?

В линейных задачах без использования процедур получить оптимальное решение можно, если

1) выбрать кратчайший путь – не делать лишних шагов или прыжков;

2) в задачах без точки Б правильно выбрать точку завершения движения "Стрелочки";

3) правильно выбрать направление движения, чтобы сократить количество поворотов на 90 градусов по часовой стрелке, так как каждый такой поворот выполняется серией команд "ПОВОРОТ ПОВОРОТ ПОВОРОТ".

Учебная задача

Постановка задачи. Постановка задачи: Разработайте алгоритм для выполнения рисунка по образцу.
Исходное положение "Стрелочки" на поле:

– точка А;
– направление движения: вправо.

Образец:

Решение задачи.

Рассмотрим три различных решения:

АЛГ ПУТЬ_1
   Дано
Исполнитель в т.А
   Надо
Воспроизвести образец
НАЧ
    ШАГ
    ПОВОРОТ
    ПОВОРОТ
    ПОВОРОТ
    ШАГ
    ШАГ
    ПОВОРОТ
    ПОВОРОТ
    ПОВОРОТ
    ШАГ
    ПОВОРОТ
    ПОВОРОТ
    ПОВОРОТ
    ШАГ
    ШАГ
КОН

Всего команд – 15. Этот алгоритм не является оптимальным, в нём слишком много поворотов, так как неудачно выбрано направление обхода – по часовой стрелке.

АЛГ ПУТЬ_2
   Дано
Исполнитель в т.А
   Надо
Воспроизвести образец
НАЧ
    ПОВОРОТ
    ПОВОРОТ
    ПОВОРОТ
    ШАГ
    ШАГ
    ПОВОРОТ
    ШАГ
    ПОВОРОТ
    ШАГ
    ШАГ
    ПОВОРОТ
    ШАГ
КОН

Всего команд – 12. Этот алгоритм  является оптимальным. В исходной точке – точке А выполняется  3 поворота, чтобы в дальнейшем обходить контур против часовой стрелки. Движение заканчивается в точке А.

 

АЛГ ПУТЬ_3
    Дано Исполнитель в т.А
    Надо Воспроизвести образец
НАЧ
    ШАГ
    ПОВОРОТ
    ПОВОРОТ
    ПРЫЖОК
    ПОВОРОТ
    ШАГ
    ШАГ
    ПОВОРОТ
    ШАГ
    ПОВОРОТ
    ШАГ
    ШАГ
КОН

Всего команд – 12. Этот алгоритм также  является оптимальным. Точкой завершения выбрана точка, отличная от точки А.

Таким образом, можно построить не единственный оптимальный алгоритм.