分形的字符串替换算法 字符串替换法是一种很简单明快地用计算机绘制分形图的方法，但它却能绘制出相当复杂优美的分形，这种方法的理论根据也是相当简单的，主要是利用分形可以由简单的图（生成元）迭代产生这一基本原理，因此可以用字符串表示生成元的构成（如组成的线段数、转动的角度等），再把字符串反迭代就能生成我们希望得到的分形图.所以这种方法主要能用在生成元比较明确的那些分形上。可分为两大类：一类是象例1的von Koch曲线这样“比较规则”的曲线，这一类分形还包含Peano曲线和Hilbert曲线等；另一类是象植物枝一样的比较复杂的树状分形。
（1）“规则”曲线的绘制
例1 先以绘制von Koch曲线为例，说明如何应用字符串替换算法：
von Koch曲线的构造是：迭代初始把单位线段去掉中间的三分之一，代之以底边在被除去线段上的等边三角形的另外两边，以后每上步迭代都是把上次图形中的每折线段去掉中间三分之一，代之以类似等边三角形的另二边。可以很清楚地了解到，这些曲线的生成元是“_/\_”，曲线由把每一折线段反复迭代成缩小比例为1/3的生成元而成。
于是，只要约定好记号，把生成元的构造用字符串表示出来，并且反复迭代，就可以直接得到我们需要的曲线。由于此例中生成元及迭代都比较“规则”，因此做法还是比较简单的。
首先做记号的约定：
A：沿逆时针方向转一角度δ；
B：沿顺时针方向转一角度δ；
C：从当前点开始沿当前方向画一长度L的线段。
有了这些记号之后就可以用一个字符串表示一个图形。为了叙述方便，有时把字符串说成图形（该字符串所代表的图形），有时把字符串或字符说成一动作（绘制该字符串所代表的图形所需的动作）。规定初始点在原点，初始角度为0，δ=π/3。则字符串“C”代表一条起点在(0,0)终点在(1,0)的线段。而“CACBBCAC”代表图1最下边的那条曲线。其中第一个C表示向前画一线段，长度L=1/3，（已规定初始点在原点，初始方向-角度为0），这样当前点（上一个动作完成之后“画笔”停留的位置）变为(1/3,0)；下一字符为A,故应沿逆时针方向转一角度π/3，在第二个字符A"操作"之后，当前点为(1/3,0)，沿当前方向π/3画一线段，L=1/3；当第三个字符C“操作”之后，当前点变成(1/2,√3/2)当前角度不变（还是π/3）；接下去二个字符BB，代表沿顺时针方向转二次，每次转π/3，这两个字符“操作”之后，当前点(1/2,√3/2)不变，而当前方向为-π/3；接下去第六个字符为C，“操作”之后，当前点为（2/3，0）当前方向为-π/3；再接下去——第七个字符A。“操作”之后，当前点为（2/3，0），而当前方向为0；最后，完成最后一“操作”，字符C——画出（2/3，0）到（1，0）之间的线段。
从von Koch曲线的作法可知：其下一步是把“CACBBCAC”中的C这一“操作”用复合“操作”C$=“CACBBCAC”来替代，故知道下一步的图形是：
C$+“A”+C$+“BB”+C$+“A”+C$
注意这时画线段的长度应为上次长度（1/3）的1/3即1/9。
综上所述，von Koch曲线可描述如下：
第一步图形为“C”，画线长度L(1)=1，若第k步图形为V(k)$，画线长度为L(k)，则第k+1步的图形V(k+1)$中的所有“C”用C$=“CACBBCAC“来代替，其它字符不变，而得到的新的字符串；画线长度L(k+1)=L(k)/3。（见图1）
根据这一算法，编写的BASIC源程序如下：
源程序1 von Koch曲线
（图1）
10 ''''''''von Koch curve
20 KEY OFF:SCREEN 2:WINDOW(0,0)-(4/3,1)
30 N=7:PI=3.141593:L=4:ANGLE=PI/3
40 P$="CD":C$="CACBBCAC":DFF SEG=&8000:ADR1=0
50 FOR i=1 TO LEN(P$)
60 POKE ADR1,ASC(MID$,i,1)):ADR1=ADR1+1:NEXT i
70 FOR i=1 TO N:CLS:A=0:L=L/3:PSET(0,1/3),4:ADR1=0
80 ON PEEK(ADR10-64 GOTO 90,100,110,130
90 A=A+1:GOTO 120
100 A=A-1:GOTO 120
110 LINE -STEP(L*COS(A*ANGLE),L*SIN(A*ANGLE))
120 ADR1=ADR1+1:GOTO 80
130 LOCATE 23,30:PRINT"von koch crver step";i
140 ADR2=&HFFFF:IF i=N THEN END
150 WHILE ADR1+1
160 ON PEEK(ADR1)-64 GOTO 170,170,180,170
170 POKE ADR2,PEEK(ADR1);GOTO 190
180 GOSUB 250
190 ADR1=ADR1-1:ADR2=ADR2-1
200 WEND
210 WHILE ADR2:ADR1=ADR1+1:ADR2=ADR2+1
220 POKE ADR1,PEEK(ADR2):WEND
230 IF i<N AND INKEY$="" THEN 230
240 NEXT i:END
250 FOR j=1 TO LEN(C$)
260 POKE ADR2,ASC(MID$(C$,LEN(C$)-j+1,1))
270 ADR2=ADR2-1:NEXT j:ADR2=ADR2+1:RETURN
对源程序的几点说明：
1.本程序用GWBASIC3.22版本，在AST 386/25机下调试通过。
2.第20语句中WINDOW的定义应使得窗口的长宽比为4:3，因为这一比例是微机显示器的标准比例。另外，为了获得较高的分辨率，以使得图象清晰，可以把SCREEN 2改为SCREEN 12，程序其它部分不变，就可以在Quick BASIC 4.5版本下运行。这样你可以得到640×480高分辨率图象。不过这时你的显示器应是VGA。
3.第40语句定义P$=“CD”，字符D是作为图象数据结束的标志，别无它意。
4.程序中40语句定义“图形数据”（字符串）存放在内存段地址8000H处，这一地址可以改变为其它处，但应该保证该段不被系统或其它程序占用。
5.迭代步数N的计算：首先，程序中用存放“图形数据”的空间为内存的一个段，即64k。而“图形数据”的增长速度是指数型的。所以迭代步数N不能取的太大。k步需要1/3（7×4^(k-1)-4）个字节，故迭代步数N应满足：
1/3（7×4^(k-1)-4）≤2^10×64
解得N≤8。
其次，取太大的N意义不大。因为显示器的分辨率是有限的。更何况BASIC语言，在图形方式下，其最高的分辨率（SCREEN 2），也只不过是640×200。事实上取N=7就已经足够了。