分行算法與程序設(shè)計(jì)課件

參考書：《分形演算法與程式設(shè)計(jì)》1

分形圖的遞歸演算法2.1Cantor三分集的遞歸演算法2.2Koch曲線的遞歸演算法

2.3Sierpinski墊片的遞歸演算法2.4Hilbert-Peano曲線的演算法2.5分支結(jié)構(gòu)分形遞歸演算法2.6分形樹遞歸演算法參考書：《分形演算法與程式設(shè)計(jì)》2遞歸演算法u

直接遞歸調(diào)用的例子如下：voidRecur(n){

……Recur(m);……}過程Recur的內(nèi)部又調(diào)用了自身——Recur過程。

參考書：《分形演算法與程式設(shè)計(jì)》3遞歸演算法u

間接遞歸調(diào)用的例子如下：voidRecur_A(n){……Recur_B(m);

……}voidRecur_B(n){……Recur_A(m);

……}

參考書：《分形演算法與程式設(shè)計(jì)》42.1Cantor三分集的遞歸演算法演算法：Cantor(ax,ay,bx,by)標(biāo)題：Cantor三分集的遞歸演算法參數(shù)：c（終止遞歸的小量）

d（不同層次線之間的距離）變數(shù)：ax,ay（曲線端點(diǎn)座標(biāo)）

bx,by（曲線端點(diǎn)座標(biāo)）

cx,xy（曲線端點(diǎn)座標(biāo)）

dx,dy（曲線端點(diǎn)座標(biāo)）函數(shù)：plot(x1,y1)–(x2,y2)

（畫直線函數(shù)）BEGINIF((bx-ax)<c)THENBEGIN

plot(ax,ay)-(bx,by)ENDELSEBEGIN

plot(ax,ay)-(bx,by)

cx=ax+(bx-ax)/3cy=ay+ddx=bx-(bx-ax)/3dy=by+day=ay+dby=by+dcantor(ax,ay,cx,cy)cantor(dx,dy,bx,by)ENDEND參考書：《分形演算法與程式設(shè)計(jì)》52.2Koch曲線的遞歸演算法演算法：Koch(ax,ay,bx,by,c)標(biāo)題：Koch曲線的遞歸演算法參數(shù)：c（終止遞歸的小量）

PI（π值）變數(shù)：ax,ay（線段端點(diǎn)座標(biāo)）

bx,by（線段端點(diǎn)座標(biāo)）

cx,xy（線段端點(diǎn)座標(biāo)）

dx,dy（線段端點(diǎn)座標(biāo)）

ex,ey（線段端點(diǎn)座標(biāo)）

L

（線段長(zhǎng)度）

alpha（基線與水平線正方向夾角）函數(shù)：plot(x1,y1)–(x2,y2)

（畫直線函數(shù)）

sin()

（正弦函數(shù)）

cos()

（余弦函數(shù)）

ArcTan()

（反正切函數(shù)）

sqrt()

（開平方函數(shù)）參考書：《分形演算法與程式設(shè)計(jì)》62.2Koch曲線的遞歸演算法BEGIN

IF((bx-ax)*(bx-ax)+(by-ay)*(by-ay))<cTHEN

BEGINplot(ax,ay)-(bx,by)

END

ELSEBEGINcx=ax+(bx-ax)/3cy=ay+(by-ay)/3ex=bx-(bx-ax)/3ey=by-(by-ay)/3L=sqrt((ex-cx)*(ex-cx)+(ey-cy)*(ey-cy))alpha=ArcTan((ey-cy)/(ex-cx))

IF((ex-cx)<0)THEN參考書：《分形演算法與程式設(shè)計(jì)》72.2Koch曲線的遞歸演算法

BEGINalpha=alpha+PI

ENDdy=cy+sin(alpha+PI/3)*Ldx=cx+cos(alpha+PI/3)*LKoch(ax,ay,cx,cy,c)Koch(ex,ey,bx,by,c)Koch(cx,cy,dx,dy,c)Koch(dx,dy,ex,ey,c)ENDEND參考書：《分形演算法與程式設(shè)計(jì)》82.3Sierpinski墊片的遞歸演算法演算法：Sierpinski(x,y,L,n)標(biāo)題：Sierpinski墊片遞歸演算法參數(shù)：n（遞歸深度）變數(shù)：x,y（三角形中心點(diǎn)座標(biāo)）

x1,y1

（三角形頂點(diǎn)座標(biāo)）

x2,y2（三角形頂點(diǎn)座標(biāo)）

x3,y3

（三角形頂點(diǎn)座標(biāo)）

x01,y01（小三角形中心點(diǎn)座標(biāo)）

x02,y02（小三角形中心點(diǎn)座標(biāo)）

x03,y03（小三角形中心點(diǎn)座標(biāo)）

L

（三角形的邊長(zhǎng)）函數(shù)：plot(x1,y1)–(x2,y2)

（畫直線函數(shù)）

sin()

（正弦函數(shù)）

cos()

（余弦函數(shù)）

sqrt()

（開平方函數(shù)）參考書：《分形演算法與程式設(shè)計(jì)》92.3Sierpinski墊片的遞歸演算法BEGINIF(n=1)THENBEGIN

x1=x-L/2y1=y+L*(sin(PI/6)/cos(PI/6))/2x2=x+L/2y2=y+L*(sin(PI/6)/cos(PI/6))/2x3=xy3=y-L*(sin(PI/6)/cos(PI/6))

plot(x1,y1)-(x1,y1)plot(x2,y2)-(x2,y2)plot(x3,y3)-(x3,y3)

ENDELSEBEGIN

x01=x-L/4y01=y+L*(sin(PI/6)/cos(PI/6))/4x02=x-L/4y02=y+L*(sin(PI/6)/cos(PI/6))/4x03=xy03=y-L*(sin(PI/6)/cos(PI/6))/2Sierpinski(x01,y01,L/2,n-1)Sierpinski(x02,y02,L/2,n-1)Sierpinski(x03,y03,L/2,n-1)ENDEND參考書：《分形演算法與程式設(shè)計(jì)》102.4Hilbert-Peano曲線的演算法演算法：Peano(n)標(biāo)題：Hilbert-Peano曲線遞歸演算法變數(shù)：n（遞歸深度）

len（線的長(zhǎng)度）

x,y（端點(diǎn)座標(biāo)）函數(shù)：lineto(x,y)（畫直線函數(shù)）過程：a(n)（基本元素構(gòu)型）

b(n)（基本元素構(gòu)型）

c(n)（基本元素構(gòu)型）

d(n)（基本元素構(gòu)型）參考書：《分形演算法與程式設(shè)計(jì)》112.4Hilbert-Peano曲線的演算法BEGINa(n)

BEGIN

IFn>0THEN

BEGINd(n-1)x=x-lenlineto(x,y)a(n-1)y=y+lenlineto(x,y)a(n-1)x=x+lenlineto(x,y)b(n-1)

END

ENDb(n)

BEGIN

IFn>0THEN

BEGINc(n-1)y=y-lenlineto(x,y)b(n-1)x=x+lenlineto(x,y)b(n-1)y=y+lenlineto(x,y)a(n-1)

END

ENDc(n)

BEGIN

IFn>0THEN

BEGINb(n-1)x=x-lenlineto(x,y)c(n-1)y=y+lenlineto(x,y)c(n-1)x=x+lenlineto(x,y)d(n-1)

END

ENDd(n)

BEGIN

IFn>0THEN

BEGINa(n-1)y=y-lenlineto(x,y)d(n-1)x=x+lenlineto(x,y)d(n-1)y=y+lenlineto(x,y)c(n-1)

END

ENDEND參考書：《分形演算法與程式設(shè)計(jì)》122.5分支結(jié)構(gòu)分形遞歸演算法演算法：Ramus

(x,y,alpha,L,n)標(biāo)題：分支結(jié)構(gòu)遞歸演算法參數(shù)：PI（π值）變數(shù)：n（遞歸深度）

L（線段長(zhǎng)度）

x,y（線段起點(diǎn)座標(biāo)）

x1,y1（線段終點(diǎn)座標(biāo)）

alpha

（主幹生成角度）

alpha_L（左支幹生成角度）

alpha_R（右支幹生成角度）函數(shù)：plot(x1,y1)-(x2,y2)

（畫直線函數(shù)）

sin()（正弦函數(shù)）

cos()（余弦函數(shù)）參考書：《分形演算法與程式設(shè)計(jì)》132.5分支結(jié)構(gòu)分形遞歸演算法BEGIN

IF(n>0)THEN

BEGINx1=x+cos(alpha)*Ly1=y-sin(alpha)*Lplot(x,y)-(x1,y1)alpha_L=alpha+PI/8alpha_R=alpha-PI/8L=2*L/3Ramus(x2,y2,alpha_L,L,n-1)Ramus(x2,y2,alpha_R,L,n-1)

ENDEND參考書：《分形演算法與程式設(shè)計(jì)》142.6分形樹遞歸演算法演算法：tree

(x,y,L,alpha)標(biāo)題：分形樹遞歸演算法參數(shù)：PI（π值）

A（主幹生長(zhǎng)方向）

B（側(cè)幹與主幹的夾角）

C（主幹偏轉(zhuǎn)角度）

s1（長(zhǎng)度小量，控制遞歸深度）

s2（主幹與側(cè)幹之比）

s3（上一級(jí)主幹與下一級(jí)主幹之比）變數(shù)：L

（主幹的長(zhǎng)度）

x,y（主幹起點(diǎn)座標(biāo)）

x1,y1（中間分叉點(diǎn)座標(biāo)）

x2,y2（主幹終點(diǎn)座標(biāo)）

x1L,y1L（第一左分支終點(diǎn)座標(biāo)）

x1R,y1R（第一右分支終點(diǎn)座標(biāo)）

x2L,y2L（第二左分支終點(diǎn)座標(biāo)）

x2R,y2R（第二右分支終點(diǎn)座標(biāo)）函數(shù)：plot(x1,y1)-(x2,y2)

（畫直線函數(shù)）

sin()（正弦函數(shù)）

cos()（余弦函數(shù)）參考書：《分形演算法與程式設(shè)計(jì)》152.6分形樹遞歸演算法BEGIN

IF(L>s1)THEN

BEGINx2=x+L*cos(A*PI/180)y2=y-L*sin(A*PI/180)x2L=x2+L/s2*cos((A+B)*PI/180)y2L=y2-L/s2*sin((A+B)*PI/180)x2R=x2+L/s2*cos((A-B)*PI/180)y2R=y2-L/s2*sin((A-B)*PI/180)x1=x+L/s2*cos(A*PI/180)y1=y-L/s2*sin(A*PI/180)x1L=x1+L/s2*cos((A+B)*PI/180)y1L=y1-L/s2*sin((A+B)*PI/180)x1R=x1+L/s2*cos((A-B)*PI/180)y1R=y1+L/s2*sin((A-B)*PI/180)plot(x,y)-(x2,y2)plot(x2,y2)-(x2L,y2L)plot(x2,y2)-(x2R,y2R)plot(x1,y1)-(x1R,y1R)plot(x1,y1)-(x1L,y1L)tree(x2,y2,L/s3,A-C)tree(x2L,y2L,L/s2,A+B)tree(x2R,y2R,L/s2,A-B)tree(x1R,y1R,L/s2,A-B)tree(x1L,y1L,L/s2,A-B)

ENDEND參考書：《分形演算法與程式設(shè)計(jì)》16第3

章文法構(gòu)圖演算法3.1LS文法3.2單一規(guī)則的LS文法生成

3.3多規(guī)則的LS文法生成3.4隨機(jī)LS文法參考書：《分形演算法與程式設(shè)計(jì)》17文法構(gòu)圖演算法字母表：L，R生成規(guī)則：L→R，R→LR初始字母：R則有：R→LR→RLR→LRRLR→RLRLRRLR→LRRLRRLRLRRLR→……

參考書：《分形演算法與程式設(shè)計(jì)》183.1LS文法二維LS是字母表的繪圖規(guī)則如下：F：以當(dāng)前方向前進(jìn)一步，並畫線；f：以當(dāng)前方向前進(jìn)一步，不畫線；＋：逆時(shí)針旋轉(zhuǎn)角；－：順時(shí)針旋轉(zhuǎn)角；[：將海龜當(dāng)前資訊壓棧；]：將“[”時(shí)刻的海龜資訊出棧。參考書：《分形演算法與程式設(shè)計(jì)》193.2單一規(guī)則的LS文法生成Koch曲線的LS文法如下：

w：Fa：60oP：F→F＋F－－F＋F

步驟0：F

步驟1：F＋

F－－F＋F

步驟2：F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋

F－－F＋

F＋

F＋

F－－F＋

F

步驟3：F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋

F－－F＋

F＋

F＋

F－－F＋

F＋

F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋F－－F＋F＋

F＋

F－－F＋

F－－F＋

F－－F＋

F＋

F＋

F－－F＋

F＋

F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋

F－－F＋F＋

F＋

F－－F＋

F

步驟4：……參考書：《分形演算法與程式設(shè)計(jì)》203.3單一規(guī)則的LS演算法實(shí)現(xiàn)演算法：LS標(biāo)題：L_System生成演算法參數(shù)：Axiom（公理）

n（字串替換次數(shù)）變數(shù)：a[]（被替換字元）

x[]，y[]（替換字串）

len（線段長(zhǎng)度）

Aipha（基線與水平線夾角）

Dalta（生成角度）

ox,oy（起始座標(biāo)點(diǎn)）

n（遞歸深度）

bef（前一節(jié)點(diǎn)）

aft（後一節(jié)點(diǎn)）函數(shù)：lineto(x,y)（畫直線函數(shù)）

GetLength(x)（字串長(zhǎng)度）BEGIN//初始化

x[0]=“F”a[1]=“F”x[1]=“F+F--F+F”len=10Aipha=0Delta=60ox=100oy=400n=4參考書：《分形演算法與程式設(shè)計(jì)》213.3單一規(guī)則的LS演算法實(shí)現(xiàn)y[]=x[0]

FORi=1TOnyL=GetLength(y)j=0

WHILE(j<yL)

IFy[j]==a[1]THENtree[]=tree[]+x[1]j=j+1

ELSEtree[]=tree[]+y[j]j=j+1

ENDIFENDWHILE

y[]=tree[]tree.Empty()//清空

ENDFOR

tree[]=y[]//按字元繪圖

WHILE(i<xL)

SWITCH(tree[i])

CASE“F”aft.x=bef.x+len*cos(Aipha*PI/180)aft.y=bef.y-len*sin(Aipha*PI/180)aft.d=bef.d//方向

LineTO(aft.x,aft.y)bef=aft

BREAK

CASE“[”stack[k]=befk=k+1

BREAK

CASE“]”bef=stack[k-1]參考書：《分形演算法與程式設(shè)計(jì)》223.3單一規(guī)則的LS演算法實(shí)現(xiàn)k=k-1LineTO(bef.x,bef.y)

BREAK

CASE“+”bef=bef+DeltaBREAK

CASE“-”bef=bef-Delta

BREAK

ENDSWITCHi=i+1

ENDWHILEEND參考書：《分形演算法與程式設(shè)計(jì)》233.3多規(guī)則的LS文法生成為了生成更複雜的圖形，可將字母表增加字母元素Sierpinski墊片的LS文法如下：

w：La：600P1：L→＋R－L－R＋

P2：R→－L＋R＋L－相應(yīng)的改造1：x[0]=“L”a[1]=“L”x[1]=“+R-L-R+”a[2]=“R”x[2]=“-L+R+L-”Delta=60參考書：《分形演算法與程式設(shè)計(jì)》243.3多規(guī)則的LS文法生成相應(yīng)的改造2：WHILE(j<xL)

IFy[j]==a[1]THENtree[]=tree[]+x[1]j=j+1ELSEIFy[j]==a[2]THEN

tree[]=tree[]+x[2]j=j+1

ELSEtree[]=tree[]+y[i]j=j+1

ENDIFy[]=tree[]

ENDWHILE

參考書：《分形演算法與程式設(shè)計(jì)》253.3多規(guī)則的LS文法生成相應(yīng)的改造3：

CASE“L”aft.x=bef.x+len*cos(Aipha*PI/180)aft.y=bef.y-len*sin(Aipha*PI/180)aft.d=bef.d//方向

LineTO(aft.x,aft.y)bef=aft

BREAK

CASE“R”aft.x=bef.x+len*cos(Aipha*PI/180)aft.y=bef.y-len*sin(Aipha*PI/180)aft.d=bef.d//方向

LineTO(aft.x,aft.y)bef=aft

BREAK參考書：《分形演算法與程式設(shè)計(jì)》263.4隨機(jī)LS文法w:Fa:25P1：F————→F[＋F]F[－F]FP2：F————→F[＋F]F[－F[＋F]]P3：F————→FF[－F＋F＋F]＋[＋F－F－F]為了更好的模擬自然景物，需要隨機(jī)使用多個(gè)變換規(guī)則。p1p2p3相應(yīng)的改造1：x[0]=“F[+F]F[-F]F”x[1]=“F[+F]F[-F[+F]]”x[2]=“FF-[-F+F+F]+[+F-F-F]”相應(yīng)的改造2：WHILE(j<xL)

IFy[j]==“F”THEN

r=Rand()%3tree[]=tree[]+x[r]j=j+1

ELSEtree[]=tree[]+y[r]j=j+1

ENDIFENDWHILE參考書：《分形演算法與程式設(shè)計(jì)》273.4隨機(jī)LS文法參考書：《分形演算法與程式設(shè)計(jì)》28第4

章迭代函數(shù)系統(tǒng)演算法4.1混沌遊戲4.2迭代函數(shù)系統(tǒng)4.3相似變換與仿射變換4.4IFS碼4.5Sierpinski墊片的IFS生成4.6拼貼與IFS碼的確定

4.7IFS植物形態(tài)實(shí)例4.8複平面上的IFS演算法參考書：《分形演算法與程式設(shè)計(jì)》29混沌遊戲4.1給定平面上三點(diǎn)A,B,C。再任意給定初始點(diǎn)Z0,做下列迭代。???íì+++=+,2/)(,2/)(,2/)(1CZBZAZZnnnn當(dāng)擲出的硬幣呈正面當(dāng)擲出的硬幣呈反面當(dāng)擲出的硬幣呈側(cè)面參考書：《分形演算法與程式設(shè)計(jì)》30迭代函數(shù)系統(tǒng)4.2迭代函數(shù)系統(tǒng)（IteratedFunctionSystem，IFS）是分形理論的重要分支。它將待生成的圖像看成是由許多與整體相似的（自相似）或經(jīng)過一定變換與整體相似的（自仿射）小塊拼貼而成。參考書：《分形演算法與程式設(shè)計(jì)》31相似變換與仿射變換直觀上看：相似變換是指在各個(gè)方向上變換的比率必須相同的一種比例變換，仿射變換是指在不同的方向上變化的比率可以不同的一種比例變換。

4.3相似變換：如果對(duì)於任意兩點(diǎn)A、B，以及對(duì)應(yīng)點(diǎn)A’、B’，總有A’B’=k·AB（k為正實(shí)數(shù)），那麼，這個(gè)變換叫做相似變換，實(shí)數(shù)k叫做相似比。仿射變換：x’=ax+by+ey’=cx+dy+f其中a,b,c,d,e,f為仿射變換係數(shù)。參考書：《分形演算法與程式設(shè)計(jì)》324.4IFS碼用多個(gè)仿射變換式表達(dá)一個(gè)圖象w1,w2,w3,……，使用每一個(gè)仿射變換式的概率p可以不同，一般面積越大，p值越大。於是，只要獲得a,b,c,d,e,f,p（IFS碼）的值便可以得到要表達(dá)的圖形。x’=a1·x+b1·y+e1y’=c1·x+d1·y+f1w1x’=a2·x+b2·y+e2y’=c2·x+d2·y+f2w2x’=a3·x+b3·y+e3y’=c3·x+d3·y+f3w3p1p2p3p1+p2+p3=1參考書：《分形演算法與程式設(shè)計(jì)》334.5Sierpinski墊片的IFS生成

由於生成的三個(gè)小三角形的面積相等，所以我們可以讓w1、w2、w3出現(xiàn)的概率相同或相近。

x’=0.5xy’=0.5yx’=0.5x+0.5y’=0.5yx’=0.5x+0.25y’=0.5y-0.5x’=0.5·x+0·y+0y’=0·x+0.5·y+0x’=0.5·x+0·y+0.5y’=0·x+0.5·y+0x’=0.5·x+0·y+0.25y’=0·x+0.5·y-0.5w1w2w3參考書：《分形演算法與程式設(shè)計(jì)》344.5Sierpinski墊片的IFS生成

演算法：IFS標(biāo)題：IFS生成演算法參數(shù)：

n（迭代次數(shù)）

m[]（存儲(chǔ)IFS碼值）變數(shù)：a,b,c,d,e,f,p（IFS碼變數(shù)）函數(shù)：Pset(x,y)（畫點(diǎn)函數(shù)）

Rand（隨機(jī)函數(shù)）BEGIN//IFS碼賦值

m[0,0]=0.5;m[0,1]=0;m[0,2]=0m[0,3]=0;m[0,4]=0;m[0,5]=0m[0,6]=0.333m[1,0]=0.5;m[1,1]=0;m[1,2]=0m[1,3]=0.5;m[1,4]=0.5;m[1,5]=0m[1,6]=0.333m[2,0]=0.5;m[2,1]=0;m[2,2]=0m[2,3]=0.5;m[2,4]=0.25;m[2,5]=0.5m[2,6]=0.334n=6000

WHILEn>0p=Rand

SWITCH(P)

CASEIS<=m[0,6]a=m[0,0];b=m[0,1];c=m[0,2]d=m[0,3];e=m[0,4];f=m[0,5]

BREAK

CASEIS<=(m[0,6]+m[1,6])a=m[1,0];b=m[1,1];c=m[1,2]d=m[1,3];e=m[1,4];f=m[1,5]

BREAK參考書：《分形演算法與程式設(shè)計(jì)》354.5Sierpinski墊片的IFS生成

CASEIS<=(m[0,6]+m[1,6]+m[2,6])a=m[2,0];b=m[2,1];c=m[2,2]d=m[2,3];e=m[2,4];f=m[2,5]BREAKCASEIS<=(m[0,6]+m[1,6]+m[2,6]+m[3,6])a=m[3,0];b=m[3,1];c=m[3,2]d=m[3,3];e=m[3,4];f=m[3,5]

ENDSWITCH

x=a*x+b*y+ex=c*x+d*y+fPset(100+600*x,500-600*y)n=n-1

ENDWHILEEND（源代碼：書中程序4.1）參考書：《分形演算法與程式設(shè)計(jì)》364.6拼貼與IFS碼的確定

此時(shí)四個(gè)子圖分別是目標(biāo)圖的1/4、1/5、1/4、1/2大小的複製品。然後按順序互動(dòng)式地在螢?zāi)簧险{(diào)節(jié)每一個(gè)子圖的仿射變換參數(shù)ai、bi、ci、di、ei，使得平移、旋轉(zhuǎn)後基本覆蓋住目標(biāo)圖。

參考書：《分形演算法與程式設(shè)計(jì)》374.7IFS植物形態(tài)實(shí)例

IFS碼在書中表4.18IFS碼在書中表4.20IFS碼在書中表4.19參考書：《分形演算法與程式設(shè)計(jì)》384.8複平面上的IFS演算法

參考書：《分形演算法與程式設(shè)計(jì)》394.8複平面上的IFS演算法

演算法：Julia_IFS標(biāo)題：Julia集的IFS演算法參數(shù)：z（迭代次數(shù)）

PI（π值）

RAND_MAX（隨機(jī)最大值）變數(shù)：k（概率變數(shù)）

x,y（z的實(shí)部和虛部）

cx,cy（c的實(shí)部和虛部）

r（極距）

a,b,e,f,m,n,wx,wy,theta

函數(shù)：Pset(x,y)（畫點(diǎn)函數(shù)）

Rand（隨機(jī)函數(shù)）

sin（正弦函數(shù)）

cos（余弦函數(shù)）

atan（反正切函數(shù)）BEGINFORi=1TOzm=a*x+en=b*y+fIFi>10THENPset(m,n)ENDIFwx=x-cxwy=y-cyIFwx>0THENtheta=atan(wy/wx)ENDIFIFwx<0THENtheta=PI+atan(wy/wx)ENDIFIFwx=0THENtheta=PI/2ENDIF參考書：《分形演算法與程式設(shè)計(jì)》404.8複平面上的IFS演算法

theta=theta/2r=sqit(wx*wx+wy*wy)k=randrnd=k/RAND_MAXIFrnd<0.5THENr=sqrt(r)ELSEr=-sqrt(r)ENDIFx=r*cos(theta)y=r*sin(theta)ENDFOREND參考書：《分形演算法與程式設(shè)計(jì)》41第5

章逃逸時(shí)間演算法5.1基本思想

5.2Julia集的逃逸時(shí)間演算法

5.3Mandelbrot集的逃逸時(shí)間演算法5.4基於牛頓迭代的Julia集的逃逸時(shí)間演算法參考書：《分形演算法與程式設(shè)計(jì)》42逃逸時(shí)間演算法的基本思想F(z)=z2+c當(dāng)c=0時(shí)，由於z是複數(shù)，即z=x+yi，則有z2=z×z=(x+yi)×(x+yi)=x2+y2i2+2xyi=(x2-y2)+(2xy)i設(shè)複數(shù)z=x+yi的絕對(duì)值，即

|z|=SQR(x2+y2)|F(z0)|=|x02-y02+2x0y0i|=SQR((x02-y02)2+(2x0y0)2)=SQR(x04+y04-2x02y02+4x02y02)=SQR((x02+y02)2)=|z0|2若0<|z0|<1,|F(z0)|<|z0|，對(duì)於每一次迭代z趨向0，即z向0收斂。若|z0|>1,經(jīng)過迭代z會(huì)趨向無窮，z向無窮逃逸。若|z0|>1,

z是平面上的單位圓。5.1參考書：《分形演算法與程式設(shè)計(jì)》43逃逸時(shí)間演算法的基本思想

當(dāng)c≠0時(shí)，其吸引子不再是0，而是一個(gè)區(qū)域，稱混沌區(qū)。如圖，假設(shè)有一個(gè)充分大的整數(shù)N，當(dāng)未逃逸區(qū)域M中的初始點(diǎn)a經(jīng)過小於N次迭代就達(dá)到未逃逸區(qū)域M的邊界，甚至超出了邊界，我們就認(rèn)為點(diǎn)a逃逸出去了；而如果經(jīng)過N次迭代後a的軌跡仍未到達(dá)M的邊界，我們就認(rèn)為，a是A上的點(diǎn)。用這樣的方法，描繪出A的邊界圖形，這便是逃逸時(shí)間演算法的基本思想。

5.1參考書：《分形演算法與程式設(shè)計(jì)》445.2Julia集的逃逸時(shí)間演算法

參考書：《分形演算法與程式設(shè)計(jì)》455.2Julia集的逃逸時(shí)間演算法

演算法：Julia標(biāo)題：Julia集的逃逸時(shí)間演算法參數(shù)：K（逃逸時(shí)間）

m（逃逸半徑）

Mx,My（繪圖範(fàn)圍）

xs,xl,ys,yl（窗口範(fàn)圍）

p,q（複平面上C的座標(biāo)）變數(shù)：x0,y0（座標(biāo)變數(shù)）

r（膜變數(shù)）函數(shù)：SetP(x,y,color)（畫點(diǎn)函數(shù)）

BEGIN//初始化

K=100m=500Mx=800My=600xs=-1.5xl=1.5ys=-1.5yl=1.5p=0.23q=0.043xb=(xl-xs)/Mxyb=(yl-ys)/My參考書：《分形演算法與程式設(shè)計(jì)》465.2Julia集的逃逸時(shí)間演算法

FORnx=0TOMx

FORny=0TOMyx0=xs+nx*xby0=ys+ny*ybk=0Loop1:xk=x0*x0-y0*y0+pyk=2*x0*y0+qk=k+1r=xk*xk+yk*ykx0=xky0=yk

IFr>mTHENH=k;gotoLoop2

ENDIF

IFk==KTHENH=r

GOTOLoop2

ENDIF

IFr<=m&&k<KTHEN

GOTOLoop1

ENDIF

Loop2:SetP(nx,ny,H)

ENDFOR

ENDFOREND參考書：《分形演算法與程式設(shè)計(jì)》47參考書：《分形演算法與程式設(shè)計(jì)》485.3Mandelbrot集的逃逸時(shí)間演算法

演算法：Mandelbrot標(biāo)題：Mandelbrot集的逃逸時(shí)間演算法參數(shù)：K（逃逸時(shí)間）

m（逃逸半徑）

Mx,My（繪圖範(fàn)圍）

xs,xl,ys,yl（窗口範(fàn)圍）

p,q（複平面上C的座標(biāo)）變數(shù)：x0,y0（座標(biāo)變數(shù)）

r（膜變數(shù)）函數(shù)：SetP(x,y,color)（畫點(diǎn)函數(shù)）

BEGINpl=0.9ps=2.3ql=1.2qs=-1.2K=100m=500Mx=800My=600p=(pl-ps)/Mxq=(ql-qs)/My

FORnp=0TOMx

FORnq=0TOMyp0=ps+np*pq0=qs+nq*qk=0參考書：《分形演算法與程式設(shè)計(jì)》495.3Mandelbrot集的逃逸時(shí)間演算法

x0=0y0=0Loop1:xk=x0*x0-y0*y0+p0yk=2*x0*y0+q0k=k+1r=xk*xk+yk*ykx0=xky0=yk

IFr>mTHENH=kGOTOLoop2

ENDIF

IFr<=mANDk<KTHEN

GOTOLoop1

ENDIFLoop2:SetP(np,nq,H)

ENDFOR

ENDFOREND參考書：《分形演算法與程式設(shè)計(jì)》50參考書：《分形演算法與程式設(shè)計(jì)》515.4基於牛頓迭代的Julia集的逃逸時(shí)間演算法

牛頓迭代法求根公式：zn+1=zn-f(zn)/f’(zn)

其中，f’(zn)是f(zn)的導(dǎo)數(shù)?？紤]f(z)=z3-1=0的情況,那麼相應(yīng)的牛頓變換是f(z)=(2z3+1)/3z2則z的三個(gè)根分別是w1=1,w2=ei2π/3,w3=ei4π/3，三個(gè)根的吸引域A(w1)，A(w2)，A(w3)的交界便是牛頓函數(shù)的Julia集。經(jīng)過迭代，在A(wi)上的點(diǎn)都會(huì)被吸引到點(diǎn)wi上。設(shè)一個(gè)較大的迭代次數(shù)N，以及一個(gè)距離小量r，當(dāng)?shù)螖?shù)達(dá)到N，其與根點(diǎn)的距離小於r的被認(rèn)為是收斂到某根上了，否則被認(rèn)為是逃逸了。參考書：《分形演算法與程式設(shè)計(jì)》525.4基於牛頓迭代的Julia集的逃逸時(shí)間演算法

演算法：Julia_Newton標(biāo)題：Julia集的牛頓迭代逃逸時(shí)間演算法參數(shù)：N（迭代次數(shù)）

r（距離小量）

Mx,My（繪圖範(fàn)圍）

xs,xl,ys,yl（窗口範(fàn)圍）

p,q（複平面上C的座標(biāo)）變數(shù)：x0,y0（座標(biāo)變數(shù)）

r（膜變數(shù)）函數(shù)：SetP(x,y,color)（畫點(diǎn)函數(shù)）

BEGINfnm(x,y)=x*x+y*y

FORi=-150TO150

FORj=-150TO150x=i/75y=i/75

FORk=1TOn

IFi=0ANDj=0THEN

GOTOLoop

ENDIF

IFfnm(x-1,y)<rTHENSetP(i,j)

GOTOLoop

ENDIFfm=3*fnm(x,y)*fnm(x,y)參考書：《分形演算法與程式設(shè)計(jì)》535.4基於牛頓迭代的Julia集的逃逸時(shí)間演算法

nx=2*x/3+(x*x-y*y)/fmny=2*y/3-2*x*y/fmx=nxy=ny

ENDFORLoop

ENDFOR

ENDFOREND參考書：《分形演算法與程式設(shè)計(jì)》54第6

章分形顯微鏡6.1逃逸時(shí)間演算法的放縮原理6.2Mandelbrot集的局部放大6.3Julia集的局部放大

6.4牛頓迭代法的局部放大6.5作為Julia集字典的Mandelbrot集參考書：《分形演算法與程式設(shè)計(jì)》55逃逸時(shí)間演算法的放縮原理6.1參考書：《分形演算法與程式設(shè)計(jì)》566.2Mandelbrot集的局部放大

BEGINdp=(pmax-pmin)/(w_right-w_left)dq=(qmax-qmin)/(w_bottom-w_top)FORi=w_leftTOw_rightp=pmin+dp*i;FORj=w_topTOw_bottomx0=0y0=0q=qmin+dq*jFORk=0TOm_times x=x0*x0-y0*y0+py=2*x0*y0+qr=x*x+y*yx0=xy0=y演算法：Mandelbrot_zoom標(biāo)題：Mandelbrot集的局部放大參數(shù)：m_times（逃逸時(shí)間）

m_deep（逃逸半徑）變數(shù)：pmin，qmin

（參數(shù)窗口左上角座標(biāo)）

pmax，qmax

（參數(shù)窗口右下角座標(biāo)）

w_left，w_top

（繪圖窗口左上角座標(biāo)）

w_right，w_bottom

（繪圖窗口右下角座標(biāo)）

p,q（參數(shù)座標(biāo)）

x,y（繪圖座標(biāo)）

x0,y0（繪圖座標(biāo)）

r（極距）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）參考書：《分形演算法與程式設(shè)計(jì)》576.2Mandelbrot集的局部放大

IF(r>m_deep)THENbreakIF(k>=m_times)THENk=rSPost(i,j,k);ENDFORENDFORENDFOREND 參考書：《分形演算法與程式設(shè)計(jì)》586.3Julia集的局部放大BEGINdp=(pmax-pmin)/(w_right-w_left)dq=(qmax-qmin)/(w_bottom-w_top)FORi=w_leftTOw_rightp=pmin+dp*i;FORj=w_topTOw_bottomx0=pmin+dp*i;y0=qmin+dq*j;q=qmin+dq*jFORk=0TOm_times x=x0*x0-y0*y0+py=2*x0*y0+qr=x*x+y*yx0=xy0=y演算法：Julia_zoom標(biāo)題：Julia集的局部放大參數(shù)：m_times（逃逸時(shí)間）

m_deep（逃逸半徑）變數(shù)：pmin，qmin

（參數(shù)窗口左上角座標(biāo)）

pmax，qmax

（參數(shù)窗口右下角座標(biāo)）

w_left，w_top

（繪圖窗口左上角座標(biāo)）

w_right，w_bottom

（繪圖窗口右下角座標(biāo)）

p,q（參數(shù)座標(biāo)）

x,y（繪圖座標(biāo)）

x0,y0（繪圖座標(biāo)）

r（極距）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）參考書：《分形演算法與程式設(shè)計(jì)》596.3Julia集的局部放大IF(r>m_deep)THENbreakIF(k>=m_times)THENk=rSPost(i,j,k);ENDFORENDFORENDFOREND 參考書：《分形演算法與程式設(shè)計(jì)》606.4牛頓迭代法的局部放大BEGINdp=(pmax-pmin)/(w_right-w_left)dq=(qmax-qmin)/(w_bottom-w_top)FORi=w_leftTOw_rightFORj=w_topTOw_bottomx=pmin+dp*i;y=qmin+dq*j;count=0;WHILE(count<N)xx=x*x yy=y*y d=3*((xx-yy)*(xx-yy)+4*xx*yy) tmp=x; x=(2/3)*x+(xx-yy)/dy=(2/3)*y-2*tmp*y/d count=count+1; ENDWHILE演算法：Newton_zoom標(biāo)題：Newton法的局部放大參數(shù)：m_times（逃逸時(shí)間）

m_deep（逃逸半徑）變數(shù)：pmin，qmin

（參數(shù)窗口左上角座標(biāo)）

pmax，qmax

（參數(shù)窗口右下角座標(biāo)）

w_left，w_top

（繪圖窗口左上角座標(biāo)）

w_right，w_bottom

（繪圖窗口右下角座標(biāo)）

p,q（參數(shù)座標(biāo)）

x,y（繪圖座標(biāo)）

xx,yy（繪圖座標(biāo)）

d（極距）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）參考書：《分形演算法與程式設(shè)計(jì)》616.4牛頓迭代法的局部放大IF(x>0)THENcolor=countELSEIF(x<-0.3)AND(y>0.0)THENcolor=count+100ELSEcolor=count+200ENDIFENDFORENDFOREND 參考書：《分形演算法與程式設(shè)計(jì)》626.5作為Julia集字典的Mandelbrot集

Julia集是一個(gè)固定的值的圖形展現(xiàn)，而Mandelbrot集卻要走遍所有的值，顯然，每一個(gè)值都對(duì)應(yīng)一個(gè)Julia集，所以我們說Mandelbrot集是Julia集微縮字典。我們可以在Mandelbrot集的繪圖空間中任意取一點(diǎn)，並將其還原成相應(yīng)的值，再將此值作為Julia集程式中選定的值，來繪製Julia集的圖形。dp=(pl-ps)/Mxdq=(ql-qs)/MyDrawJulia(ps+dp*point.x,qs+dq*point.y)參考書：《分形演算法與程式設(shè)計(jì)》63第7

章分形演化演算法7.1從邏輯運(yùn)算談起7.2一維元胞自動(dòng)機(jī)7.3二維元胞自動(dòng)機(jī)7.4分形演化的DLA模型7.5用DLA模型模擬植物的生長(zhǎng)7.6不同初始條件的DLA形態(tài)參考書：《分形演算法與程式設(shè)計(jì)》64參考書：《分形演算法與程式設(shè)計(jì)》65從邏輯運(yùn)算談起7.1邏輯異或

本行：00011011下一行：0110

參考書：《分形演算法與程式設(shè)計(jì)》667.2一維元胞自動(dòng)機(jī)元胞按等間隔方式分佈在一條向兩側(cè)無限延伸的直線中，稱為一維元胞自動(dòng)機(jī)。

本行：001100其他下一行：110參考書：《分形演算法與程式設(shè)計(jì)》677.2一維元胞自動(dòng)機(jī)演算法：cell_one標(biāo)題：一維元胞自動(dòng)機(jī)參數(shù)：n（水準(zhǔn)方向最大值）

m（垂直方向最大值）變數(shù)：i，j（迴圈變數(shù)）

y1[]（本行元胞數(shù)組）

y2[]（下一行元胞數(shù)組）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）BEGIN

FORi=1TOm

FORj=1TOn

IFy1[j-1]=0ANDy1[j]=0ANDy1[j+1]=1THENy2[j]=1

ELSEIFy1[j-1]=1ANDy1[j]=0ANDy1[j+1]=0THENy2[j]=1

ELSEy2[j]=0

ENDIF

IFy2[j]=1THENSPost(x,y,color)

ENDIFENDFORENDFOREND參考書：《分形演算法與程式設(shè)計(jì)》687.3二維元胞自動(dòng)機(jī)在一個(gè)二維網(wǎng)格中，如果拋下一粒種子（元胞著色），然後考察一下種子身邊的格子中的元胞狀態(tài)會(huì)發(fā)生什麼事情。給一個(gè)規(guī)則，即每一個(gè)格子的狀態(tài)，由其周圍的八個(gè)格子的狀態(tài)（0或1）來決定，如果它周圍八個(gè)格子中的狀態(tài)值相加為奇數(shù)時(shí)，則此格子下一個(gè)狀態(tài)為1；如果它周圍八個(gè)格子中的狀態(tài)值相加為偶數(shù)時(shí)，則此格子下一個(gè)狀態(tài)為0。就這樣一步一步演化下去，會(huì)看到圖案。參考書：《分形演算法與程式設(shè)計(jì)》697.3二維元胞自動(dòng)機(jī)演算法：cell_two標(biāo)題：二維元胞自動(dòng)機(jī)參數(shù)：n（元胞的範(fàn)圍）變數(shù)：i，j（迴圈變數(shù)）

a[][]（本步元胞數(shù)組）

b[][]（下一步元胞數(shù)組）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）BEGIN

FORi=1TOn

FORj=1TOn

k=a[i-1][j-1]+a[i-1][j]+a[i-1][j+1] +a[i][j-1]+a[i][j+1]+a[i+1][j1]

+a[i+1][j]+a[i+1][j+1]

IFkmod2=1THENb[i][j]=1

ELSEb[i][j]=0

ENDIFENDFORENDFOREND參考書：《分形演算法與程式設(shè)計(jì)》707.4分形演化的DLA模型

自然界中有很多種這樣的生長(zhǎng)集團(tuán)參考書：《分形演算法與程式設(shè)計(jì)》717.4分形演化的DLA模型

演算法：DLA標(biāo)題：DLA模型參數(shù)：BAX，BAY（基點(diǎn)座標(biāo)）

m（垂直方向最大值）變數(shù)：r0（凝聚半徑）

r（釋放粒子的半徑）

rmax（粒子逃逸半徑）

cyt,cyb,cyl,cyr

（遊走粒子周圍4點(diǎn)）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）

getpixel(x,y)（獲取點(diǎn)）

read()（隨機(jī)函數(shù)）

sgn()

（符號(hào)函數(shù)）BEGINr0=5

WHILE(n<1000)r=r0+5rmax=r0+5rx=(2*r+1)*read()-rrv=r-abs(rx)ry=rv*sgn(read()-0.5)x=rxy=ry

FOR(;;)xb=xyb=ydist=abs(x)+abs(y)cyt=getpixel(x+BAX,y+BAY+1)cyb=getpixel(x+BAX,y+BAY-1)cyl=getpixel(x+BAX-1,y+BAY)cyr=getpixel(x+BAX+1,y+BAY)參考書：《分形演算法與程式設(shè)計(jì)》727.4分形演化的DLA模型

twd[1]=0twd[2]=0twd[(2*read())+1]=sgn(read()-0.5)x=x+twd[1]y=y+twd[2]SPost(x+BAX,y+BAY,white)SPost(x+BAX,y+BAY,red)ENDFORENDWH