Кривая Гильберта
Пространственно-заполняющая кривая --- непрерывная линия, которая проходит через все точки квадрата. Применяется в картографии, обработке изображений и базах данных для пространственной индексации.
Разбор
Перемещаем черепаху в левый верхний угол поля и запускаем построение с глубиной 5 и шагом 14:
использовать Черепаха
алг
нач
поднять хвост
назад(140)
влево(90)
вперед(140)
вправо(90)
опустить хвост
hilbert_A(5, 14.0)
кон
Кривая строится двумя взаимно рекурсивными алгоритмами --- hilbert_A и hilbert_B. Они рисуют зеркальные фрагменты кривой. Базовый случай ($n = 0$) --- ничего не делаем.
Алгоритм hilbert_A поворачивает влево, вызывает hilbert_B, затем соединяет три фрагмента прямыми шагами, чередуя вызовы hilbert_A и hilbert_B:
алг hilbert_A(цел n, вещ step)
нач
если n = 0 то
| ничего
иначе
влево(90)
hilbert_B(n - 1, step)
вперед(step)
вправо(90)
hilbert_A(n - 1, step)
вперед(step)
hilbert_A(n - 1, step)
вправо(90)
вперед(step)
hilbert_B(n - 1, step)
влево(90)
все
кон
Алгоритм hilbert_B --- зеркальная копия hilbert_A. Все повороты направо заменены на повороты налево и наоборот:
алг hilbert_B(цел n, вещ step)
нач
если n = 0 то
| ничего
иначе
вправо(90)
hilbert_A(n - 1, step)
вперед(step)
влево(90)
hilbert_B(n - 1, step)
вперед(step)
hilbert_B(n - 1, step)
влево(90)
вперед(step)
hilbert_A(n - 1, step)
вправо(90)
все
кон
На каждом уровне рекурсии количество отрезков увеличивается в 4 раза. На уровне 5 кривая проходит через $4^5 = 1024$ точки, заполняя квадрат равномерной змейкой.
Полная программа
использовать Черепаха
алг
нач
поднять хвост
назад(140)
влево(90)
вперед(140)
вправо(90)
опустить хвост
hilbert_A(5, 14.0)
кон
алг hilbert_A(цел n, вещ step)
нач
если n = 0 то
| ничего
иначе
влево(90)
hilbert_B(n - 1, step)
вперед(step)
вправо(90)
hilbert_A(n - 1, step)
вперед(step)
hilbert_A(n - 1, step)
вправо(90)
вперед(step)
hilbert_B(n - 1, step)
влево(90)
все
кон
алг hilbert_B(цел n, вещ step)
нач
если n = 0 то
| ничего
иначе
вправо(90)
hilbert_A(n - 1, step)
вперед(step)
влево(90)
hilbert_B(n - 1, step)
вперед(step)
hilbert_B(n - 1, step)
влево(90)
вперед(step)
hilbert_A(n - 1, step)
вправо(90)
все
кон