Как решать задачи "с образцом" и без точки Б? |
||
Два типа задач |
Все задачи на разработку алгоритмов для "Стрелочки" можно разделить на два типа: |
|
|
|
|
Что такое оптимальный алгоритм ? | В задачах для самостоятельного решения требуется не просто переместить "Стрелочку" из точки А в точку Б либо повторить заданный рисунок. Требуется разработать оптимальный алгоритм перемещения. Чаще всего, это кратчайший по числу команд алгоритм. | |
Как получить оптимальный алгоритм? |
В линейных задачах без использования процедур получить оптимальное решение можно, если 1) выбрать кратчайший путь – не делать лишних шагов или прыжков; 2) в задачах без точки Б правильно выбрать точку завершения движения "Стрелочки"; 3) правильно выбрать направление движения, чтобы сократить количество поворотов на 90 градусов по часовой стрелке, так как каждый такой поворот выполняется серией команд "ПОВОРОТ ПОВОРОТ ПОВОРОТ". |
Учебная задача |
||
Постановка задачи. | Постановка задачи: Разработайте алгоритм для выполнения рисунка по образцу. | |
Исходное положение "Стрелочки" на поле:
– точка А; |
Образец:
|
Решение задачи. | Рассмотрим три различных решения: |
||
|
|
|
|
АЛГ ПУТЬ_1 Дано Исполнитель в т.А Надо Воспроизвести образец НАЧ ШАГ ПОВОРОТ ПОВОРОТ ПОВОРОТ ШАГ ШАГ ПОВОРОТ ПОВОРОТ ПОВОРОТ ШАГ ПОВОРОТ ПОВОРОТ ПОВОРОТ ШАГ ШАГ КОН Всего команд – 15. Этот алгоритм не является оптимальным, в нём слишком много поворотов, так как неудачно выбрано направление обхода – по часовой стрелке. |
АЛГ ПУТЬ_2 Дано Исполнитель в т.А Надо Воспроизвести образец НАЧ ПОВОРОТ ПОВОРОТ ПОВОРОТ ШАГ ШАГ ПОВОРОТ ШАГ ПОВОРОТ ШАГ ШАГ ПОВОРОТ ШАГ КОН Всего команд – 12. Этот алгоритм является оптимальным. В исходной точке – точке А выполняется 3 поворота, чтобы в дальнейшем обходить контур против часовой стрелки. Движение заканчивается в точке А.
|
АЛГ ПУТЬ_3 Дано Исполнитель в т.А Надо Воспроизвести образец НАЧ ШАГ ПОВОРОТ ПОВОРОТ ПРЫЖОК ПОВОРОТ ШАГ ШАГ ПОВОРОТ ШАГ ПОВОРОТ ШАГ ШАГ КОН Всего команд – 12. Этот алгоритм также является оптимальным. Точкой завершения выбрана точка, отличная от точки А. Таким образом, можно построить не единственный оптимальный алгоритм. |