Отправляет email-рассылки с помощью сервиса Sendsay

Программирование в Delphi

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Delphi - проблемы и решения" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Май 2006   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Сергей

Статистика

11.187 подписчиков
-91 за неделю
←   Все выпуски   →

Рекурсия и фракталы


Выпуск No 7
Рекурсия и фракталы
Меню сайта рассылки
 

Здравствуйте!

Сначала хочу сделать небольшое объявление. По адресу http://glyclabs.narod.tu

начал работу сайт рассылки. Не судите строго, это мой первый сайт. Пожалуйста, ответьте на анкету для подписчиков, размещённую на сайте! Учту все ваши предложения и замечания.

Сегодня я хочу показать вам удивительный мир фракталов. Фрактал это геометрическая фигура обладающая свойствами самоподобия. То есть каждый минимальный элемент фрактала похож на весь фрактал в целом. Фрактал можно бесконечно увеличивать, и при каждом новом увеличении будут появляться  новые элементы. Вы думаете, вы никогда не видели фрактал? На самом деле вы очень часто с ними встречаетесь! Фракталы окружают нас. Многие объекты в живой природе - фрактальной природы. Самый яркий пример - листок папоротника. Вспомните, от главного стебля папоротника отходят боковые стебли поменьше, на ктоторых ов таком же порядке располагаются ещё меньшие стебли. И если сравнить часть листа папоротника со всем листом, окажется, что они удивительно похожи. Многие эффекты визуализации в Winamp и Windows Media Player сделаны с использованием фрактальных методов. В игровой индустрии фрактальная графика встречается ещё чаще. Горы, деревья, трава, камни и многие другие объекты - фракталы.

Наиболее известны 3 типа фракталов: геометрические, алгебраические и стохастические. Геометрические фракталы - самый распространённый тип фракталов. Именно на основе алгебраических фракталов в играх создаются горы, деревья и т.д. А ещё ими преподаватели информатики в ВУЗах очень любят мучить нерадивых студентов. Алгебраические фракталы названы так потому, что они строят графики некоторых алгебраических функций, необъяснимых с точки зрения стандартной, евклидовой геометрии. Алгебраические фракталы представляют собой очень красивое, необычное зрелище. На первый взгляд кажется, что все эти кривые, завихрения, ломаные хаотичны, но на самом деле там присутствует чёткая закономерность.

Стохастические фракталы на самом деле являются разновидностью первых двух типов фракталов. Но в формулы стохастических фракталов введён элемент случайности. И каждый новый стох. Фрактал будет немного непохож на предыдущий. Именно благодаря стохастическим фракталам в современных играх каждое облачко, каждый  кустик, каждая травинка неповторимы и непохожи на другие.

Здесь вы можете найти картинки некоторых фракталов.

Наверное, я утомил вас этой лекцией, но фракталы настолько интересное,  восхитительное явление, что я могу рассказывать о них часами. Если вы заинтересовались этой темой отсылаю вас к сайту http://www.ghcube.com/fractals/, который целиком посвящён фракталам.

 

Теперь поговорим о рекурсии. Рекурсивная подпрограмма-подпрограмма, которая из своего тела вызывает сама себя.

Вот пример простейшей рекурсивной функции - нахождение факториала числа.

 

procedure TForm1.Button1Click(Sender: TObject);

begin

Label1.caption:=FloatToStr(Fract(StrToInt(Edit1.text)));

end;

function fract(n: real):real;

begin

If n<=0 then result:=1 else result:=n*fract(n-1);

end;

 

По событию Button1Click мы вызываем нашу рекурсивную функцию. Её входным параметром будет число, факториал которого мы ищем.

В рекурсивном алгоритме всегда существуют 2 вещи:

1. База рекурсии - то место, где рекурсия должна остановиться. (Обычно самая мелкая операция). В нашем случае это первая строчка функции fract. Если в рекурсивном алгоритме отсутствует база, то он будет вызывать себя бесконечно, тем самым завесив машину ;)).

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

 

Работает это так: сначала функция вызывает сама себя до тех пор пока не приблизится к базе. Это называется рекурсивный спуск. Когда функция наконец получит своё первое значение (в нашем случае - 1), начинается вычисление функции - рекурсивный подьём.

Пример для числа 3:

Fract(3)

Fract(2)

Fract(1) // Спуск

Fract(0)

 

Fract(0)=1

Fract(1)=1*Fract(0)=1

Fract(2)=2*Fract(1)=2*1=2 // Подъём

Fract(3)=3*Fract(2)=3*2=6

 

Именно с помощью рекурсивного алгоритма строятся фракталы.

Теперь наконец перейдём от теории к практике. Сделаем геометрический фрактал «Треугольник Серпинского». Вот как он выглядит:

Поместите на форму компонент Image, компонент SpinEdit со вкладки Samples и кнопку.  У SpinEdit’а в свойстве MinValue напишите 1, а в свойстве MaxValue - 20.

 

По событию Button1Click пропишите:

 

procedure TForm1.Button1Click(Sender: TObject);

var x1, y1, x2, y2, x3, y3: integer;

begin

Image1.Canvas.FillRect(clientrect);

x1:=Image1.Width div 2;

y1:=10;

x2:=Image1.Width-10;

y2:=Image1.Height-10;

x3:=10;

y3:=Image1.Height-10;

Image1.Canvas.MoveTo(x1, y1);

Image1.Canvas.LineTo(x2, y2);

Image1.Canvas.MoveTo(x2, y2);

Image1.Canvas.LineTo(x3, y3);

Image1.Canvas.MoveTo(x3, y3);

Image1.Canvas.LineTo(x1, y1);

Serpinsky(x1, y1, x2, y2, x3, y3, StrToInt(SpinEdit1.Text))

end;

 

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

Далее мы вызываем рекурсивную процедуру.

 

procedure TForm1.Serpinsky(x1, y1, x2, y2, x3, y3, n: integer);

var

x12, y12, x22, y22,x32, y32: integer;

begin

If n>0 then

begin

//jj

x12:=(x1+x3) div 2;

y12:= (y3+y1) div 2;

x22:= (x1+x2) div 2;

y22:= (y1+y2) div 2;

x32:= (x3+x2) div 2;

y32:= (y3+y2) div 2;

Image1.Canvas.MoveTo(x12, y12);

Image1.Canvas.LineTo(x22, y22);

Image1.Canvas.MoveTo(x22, y22);

Image1.Canvas.LineTo(x32, y32);

Image1.Canvas.MoveTo(x32, y32);

Image1.Canvas.LineTo(x12, y12);

Serpinsky(x1, y1, x22, y22, x12, y12, n-1);

Serpinsky(x12, y12, x32, y32, x3, y3, n-1);

Serpinsky(x22, y22, x2, y2, x32, y32, n-1);

end;

end;

 

Процедура Serpinsky находит середины сторон каждого треугольника и соединяет их линиями, которые собой образуют новый треугольник.

Ну и напоследок давайте сделаем алгебраический фрактал, который называется «множество Мандельброта».

Наверное, это самый знаменитый фрактал. Он назван в честь математика Бенуа Мандельброта. Фракталы были известны ещё до нашей эры, но именно Мандельброт научно обосновал закономерности фракталов, и создал собственный вид геометрии - фрактальную геометрию. Обратите внимание на рисунок:  точки внутри фигуры стремятся к 0, а точки за пределами фигуры - к бесконечности. Самое интересное - границы фигуры - они-то как раз и фрактальны! Если мы будем увеличивать фигуру, то при каждом новом приближении будем замечать новые элементы, кажущиеся хаотичными, но на самом деле строго упорядоченными.

На форме разместите компонент Image и кнопку. Прорпишите следующий код:

procedure TForm1.Button1Click(Sender: TObject);

var

  R: TRect;

  au, ao: Integer;

  dX, dY, bo, bu: Double;

begin

Image1.canvas.FillRect(clientrect);

Button1.Enabled:=false;

Button1.caption:='Wait!';

  R.Left := 0;

  R.Right := Image1.width;

  R.Top := 0;

  R.Bottom := Image1.height;

  ao := 1;

  au := -2;

  bo := 1.5;

  bu := -1.5;

  dX := (ao - au) / (R.Right - R.Left);

  dY := (bo - bu) / (R.Bottom - R.Top);

  DrawMandelbrot(Image1.Canvas, dX, dY, au, bu, R.Right, R.Bottom);

  Button1.Enabled:=true;

Button1.caption:='Draw Mandelbort!';

beep;

end;

procedure TForm1.DrawMandelbrot(ACanvas: TCanvas; X, Y, au, bu: Double; X2, Y2:

  Integer);

var

  c1, c2, z1, z2, tmp: Double;

  i, j, Count: Integer;

begin

  c2 := bu;

  for i := 10 to X2 do

  begin

    c1 := au;

    for j := 0 to Y2 do

    begin

      z1 := 0;

      z2 := 0;

      Count := 0;

      {count is deep of iteration of the mandelbrot set

       if |z| >=2 then z is not a member of a mandelset}

      while (((z1 * z1 + z2 * z2 < 4) and (Count <= 90))) do

      begin

        tmp := z1;

        z1 := z1 * z1 - z2 * z2 + c1;

        z2 := 2 * tmp * z2 + c2;

        Inc(Count);

      end;

      //the color-palette depends on TColor(n*count mod t)

      ACanvas.Pixels[j, i] := (16 * Count mod 255);

      c1 := c1 + X;

    end;

    c2 := c2 + Y;

  end;

 

end;

 

Здесь вы можете скачать exe-шник, в котором можно увеличивать фрактал, дабы рассмотреть его в мельчайших подробностях. Предупреждаю сразу: прорисовка идёт очень долго. Так что если ваша машина не подаёт признаков жизни - она не зависла, она думает ;))!!

Ну вот и всё на сегодня.

 

Скриншоты фракталов - скачать

Исходники - скачать

EXE-шники - скачать

Exe-шник множества Мандельброта - скачать


Все отзывы, пожелания, предложения присылайте на glyclabs@mail.ru
От вас зависит содержание рассылки, пишите!
C уважением, Valar

Количество подписчиков: 832
В избранное