Приклад застосування рекурсивної процедури для створення фракталу

Питання для роздумів

Об'єкт Вікно списку, метод AddItem додавання елемента у Вікно списку, метод RemoveItem видалення елемента з Вікна списку.

1. Як Ви думаєте, чи можна за допомогою Вікна списку відсортувати цілі випадкові числа, що виходять за допомогою наступного оператора:
   Число(і) = Int (Rnd * 100)?
2. А чи можна тим же способом відсортувати випадкові числа, що виходять за допомогою оператора:
   Число(і) = Rnd?
3. Який «парадоксальний» результат Ви одержите, якщо спробуєте за допомогою Вікна списку відсортувати «за зростом» людей, серед яких виявиться карлик ростом 95 см?

Чи не здалася Вам назва цього розділу чимось лиховісним? Що це за звір такий — фрактал? Слово фрактал походить від лат. слова fractus — розбитий, роздроблений.

Але нічого лиховісного в цьому понятті немає. Виникло воно порівняно недавно, у 1975 р., і придумав його американський математик Бенуа Б. Мандельброт для позначення геометричних об'єктів, що мають дробову розмірність.

Ви звикли мати справу з геометричними об'єктами цілої розмірності: лінія, промінь, відрізок мають розмірність 1; трикутник, прямокутник, окружність — розмірність 2; куб, куля, циліндр — розмірність 3. А Мандельбротом були придумані такі геометричні об'єкти, розмірність яких не є цілим числом!

Геометричні об'єкти дробової розмірності називають фрактальними множинами чи просто фракталами.

Ці об'єкти (множини) не можна намалювати чи виліпити з пластиліну — вони є результатом роботи деяких рекурсивних алгоритмів, якщо ті працюють нескінченно довго. Практично навіть за допомогою Вашого персонального комп'ютера можна створити щось, що б віддалено нагадувало фрактали.

У комп'ютерній графіці поняття фрактала експлуатується досить інтенсивно: у журналах і книгах часто можна побачити красиві картинки «інопланетних пейзажів» і фантастичних орнаментів. Ці зображення, створені комп'ютером, не змогла б створити навіть сама бурхлива людська фантазія.

Для побудови геометричного образа, що наближається до фракталу, використовується наступний алгоритм.

Береться яке-небудь звичайне вхідне зображення. Це може бути квадрат, трикутник, навіть яке-небудь слово, зображене великим шрифтом. За визначеним законом створюються зменшені (копії можуть ще й деформуватися за визначеним законом) копії вхідного зображення, що також за певним законом розміщаються на площині майбутнього малюнка. Вхідне зображення стирається.

Tе ж саме, рекурсивно, робиться з кожною копією.

Якби процес продовжувався нескінченно, то результатом його був би дійсний фрактал.

Однак на комп'ютері будь-який алгоритм може працювати тільки до визначеної межі. Ця межа встановлюється головним чином вирішальною здатністю екрана Вашого монітора. Тому на визначеному кроці процес послідовного дроблення вихідного зображення припиняється, а ми одержуємо можливість помилуватися результатом, що тільки умовно можна назвати фракталом.

Вражаючим у цьому результаті є те, що він не залежить від того, що було взято як вхідне зображення! Кінцева картинка залежить тільки від тих законів, за якими будувалися і розміщувалися копії!

Приклад 3.5. Розглянемо фрактал, що називається трикутником Серпиньского (на честь польського математика, що вперше описав цей об'єкт у 1916 р.).

Будується цей трикутник у такий спосіб.

Беруться 3 квадрати, у які вписуються 3 однакових вхідних зображення (припустимо, звичайні трикутники — див. мал. 3.2, а).

а)

б)

с)

Мал. 3.2. Перші 2 кроки побудови фрактального трикутника

Потім кожен з трьох квадратів заміняється трьома квадратами, розміри яких у два рази менші від розмірів вхідних квадратів. У них також вписуються трикутники (мал. 3.2, б).

Кожний з нових дев'яти квадратів, у свою чергу, заміняється трьома меншими квадратами, у які знову вписуються трикутники (мал. 3.2, с), і т.д. Процес продовжується доти, поки розміри трикутників (чи квадратів) не досягнуть встановленого заздалегідь мінімального значення.

Істинний трикутник Серпиньского, що мав би вийти, якби процес продовжувався до нескінченності, розміри квадратів (трикутників) дорівнювали б нулю. Проте як геометричний об'єкт із дробовою розмірністю він все ж існує! А ми навіть через невелике число кроків можемо бачити образ, що до якогось ступеня наближає нас до розуміння змісту таких об'єктів.

Для побудови зображень, що подібні до описаних вище, зручно використовувати рекурсивні процедури.

У даному випадку такою рекурсивною процедурою є процедура НамалюватиТрикутник.

Це процедура з п'ятьма вхідними параметрами: d, xl, yl, x2, y2, де d — мінімально припустимий розмір сторони квадрата, у який вписується трикутник, (xl, yl) і (x2, y2) — координати лівої верхньої і правої нижньої вершин квадрата.

Для малювання квадрата і трикутників використовується метод Line мови Visual Basic. Він застосовується до об'єкта Графічне вікно з ім'ям Picture l. Оператори, що малюють лінії, розміщені у визначенні процедури до рекурсивних викликів. Це означає, що малювання буде відбуватися на рекурсивному спуску і користувач матиме можливість стежити за ходом побудови результату.

Визначення процедури НамалюватиТрикутник наступне:

Код 3.13

Процедура запуску представлена наступним кодом:

Код 3.14

Відразу після натискання командної кнопки робиться масштабування вікна зображення і встановлюється значення вирішальної здатності екрана - мінімальної довжини сторони трикутника.

Слідом за цим робиться виклик рекурсивної процедури НамалюватиТрикутник.

На мал. 3.3 показаний результат роботи програми — зображення фракталу на екранній формі робочого додатка. Роздільна здатність екрана d встановлена рівною 1, а розміри вікна зображення (у пікселях) - 256 x 256.

Мал. 3.3. Результат роботи додатка «Фрактальна множина — трикутник Серпиньского»

Hові поняття:

Дата добавления: 2014-12-23