Демонстрация задачи

Вот метод towers, который вы только что видели.

Я добавил здесь переменную step, чтобы подсчитать количество шагов для решения задачи. Так, что здесь отображаются шаги.

Там также есть метод demo с параметром num для установки различного количества дисков.

Скомпилируем и запустим программу.

Вызовем метод demo, и давайте сначала попробуем с 2 дисками, и задача выполнена в 3 хода.

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

Давайте попробуем еще раз, используя 3 диска.

И решение выполняется в 7 шагов.

Давайте попробуем большее число, скажем, 8 дисков.

Были сделаны 255 или 2 в 8-й степени -1 ходов.

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

Здесь также есть анимированная версия программы Башни Ханоя, так что вы можете на самом деле визуализировать все движение.

Программа в основном такая же, как и раньше, и как вы можете видеть, здесь есть вывод для 1 диска.

И здесь есть первый рекурсивный вызов для перемещения num-1 дисков.

Не рекурсивный шаг для перемещения одного диска. И второй рекурсивный вызов для перемещения num-1 дисков снова.

Остальной код для обработки некоторого наглядного представления дисков и для создания дисков разных цветов.

Скомпилируем программу и давайте запустим программу с n равным 6.

Здесь вы можете увидеть, что программа, во-первых, переместит 5 маленьких диска в середину, и теперь, большой диск может перемещаться к месту назначения и так далее, пока задача не будет завершена.

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

Фракталы

Я хотел бы кратко рассказать о фракталах. Некоторые из вас, возможно, видели фрактальные изображения.

Фракталом является математическое множество, которое отображает самоподобные узоры, то есть, фракталы отображаются одинаково или почти одинаково, в различных масштабах или ориентациях.

Рекурсивные функции также описывают процессы, которые самоподобны.

Вы увидите, что многие фрактальные узоры могут быть получены с использованием рекурсивных функций.

Термин «фрактал» был впервые введен Мандельбротом, математиком в 1975 году.

Множество комплексных чисел, которое называется множеством Мандельброта, можно визуализировать с помощью набора фрактальных изображений.

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

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

То, что я хочу показать, это простой фрактал, который называется ковром Серпинского.

Ковер Серпинского создается путем создания квадрата, а затем делением его на девять меньших квадратов одинакового размера, то есть с помощью матрицы 3х3, удалив центральный квадрат, поочередно, вы можете покрасить его другим цветом.

Процесс затем будет повторяться для восьми окружающих квадратов.

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

Вот реализация рекурсивного метода генерации ковра Серпинского.

Метод называется drawSierpinskiCarpet с 6 параметрами.

Во-первых, это изображение на котором ковер Серпинского должен быть изображен.

Параметры left и top дают расположение квадрата, с которым в настоящее время идет работа.

Параметры width и height дают размер текущего квадрата, и iterations дает глубину рекурсивных вызовов, которые должны быть сделаны.

Выражение if для проверки того, что изображение на самом деле существует, ширина не равна высоте означает, что квадрат не является квадратом, ширина <3 означает, что квадрат не может быть разделен на 3х3, и итерации меньше 1 означает, что все рекурсивные вызовы были завершены.

Ничего не будет сделано, если какое-либо из этих условий верно.

Размер меньших квадратов получается путем деления ширины на 3, то есть генерацией матрицы 3х3.

Метод drawRectangle для класса СolorImage рисует прямоугольник на изображении, в месте, указанном первыми двумя параметрами.

И третий, и четвёртый параметры определяют размер прямоугольника, который рисуется.

В этом случае, это квадрат с размером в количество пикселей.

Вложенные циклы здесь для рисования 8 мини ковров Серпинского, делая рекурсивные вызовы метода drawSierpinskiCarpet.

Обратите внимание, что if выражение, чтобы пропустить средний квадрат, который индексируется как 1,1.

Откроем IDEA, чтобы посмотреть демонстрацию программы.

Это тот же метод drawSierpinskiCarpet, который мы только что видели.

Я добавил метод demo здесь, чтобы настроить холст, ColorImage и параметры для метода drawSierpinskiCarpet.

Ширина и высота устанавливаются в 729, что является 3 в степени 6.

Число итераций установлено на 6, так что в 6 итераций, размер площади будет снижен до единицы.

Давайте скомпилируем программу и создадим экземпляр SierpinskiCarpet, и запустим метод demo.

Здесь создается ковер Серпинского. Это выглядит захватывающим.

Здесь метод drawRectangle для ColorImage вызывается таким образом, что квадраты рисуются различными цветами.

Три дополнительные параметры здесь указывают цвет прямоугольника, который рисуется.

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

Здесь также замедляется выполнение программы, используя паузу, так что вы можете увидеть программу в действии.

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