Science 版 (精华区)

发信人: qpcwth (独翅鸟), 信区: Science
标  题: 《分形艺术》37
发信站: 哈工大紫丁香 (2001年11月03日18:12:43 星期六), 站内信件

第四章传统分形：从反例到主角
4.5谢尔宾斯基地毯
　
    波兰著名数学家谢尔宾斯基在1915-1916年期间，为实变函数理论构造了几个典型的
例子，这些怪物常称作“谢氏地毯”、“谢氏三角”、“谢氏海绵”、“谢氏墓垛”。
如今，几乎任何一本讲分形的书都要提到这些例子。它们不但有趣，而且有助于形象地
理解分形。
    我们首先看谢氏三角形。取一个大的正三角形，即等边三角形。连接各边的中点，
得到4个完全相同的小正三角形，挖掉中间的一个，这是第一步。
    然后将剩下的三个小正三角形按照上述办法各自取中点、各自分出4个小正三角形，
去掉中间的一个小正三角形，这是第二步。
    依次类推，不断划分出小的正三角形，同时去掉中间的一个小正三角形。这就是谢
氏三角形的生成过程。数学家很关心当步数趋于无穷大时最后剩下了什么。的确，最后
仍然剩下一些 东西。
    直观上可以想像，最后得到的极限图形面积为零。设初始三角形面积为S，则第一步
完成后去掉的面积为1/4S。第二步完成后去掉的面积为1/4S+3×(1/4)^2 S。第三步完成
后总共去掉的面积为1/4S+3×(1/4)^2S+3^2× (1/4)^3S。第n步后去掉的总面积为：
S_n(去掉)=S/4×［1+3/4+…+(3/4)^n-1］=S× ［1-(3/4)^n］
显然，当n→∞时，S_n(去掉)→S，即剩下的面积为零。读者朋友最 好拿一张纸，亲自
试一试挖取三角形的过程，挖掉的部分涂黑，用不了几步，就会发现差不 多一片黑了。
重要的是，在挖取操作中能够体会分形的生成过程：生成分形一点也不难，小 孩子也会
做!
    我们大多不是数学家，所以不必真的关心极限图形，观察前8步就足够了。实际上，
无限精度只是个理想，作为物理学工作者(大家都是广义的物理学工作者!)，接触的永远
是有限世界，更感兴趣的是有限到无限的过程。当步数n比较大时，我们就可以近似认为
达到了无穷。在几乎所有规则分形的生成过程中，n取20便足可以认为是∞了!
    在挖取三角形的过程中，我们发现，每一步骤构造出的小三角形与整个三角形是相
似的，特别是当步数n较大时，相似性更是明显，有无穷多个相似，每一小三角形与任何
其他三角形也都是相似的。
    上面是以正三角形说明的，那么换成一般的三角形是否可以呢?当然可以。如果最初
选一个非常一般的三角形，每次也取中点，去掉中间一个小三角形，最后得到的结论完
全一样。那么不用三角形是否可以呢?也当然可以。比如开始时取一个正方形，将它9等
分，去掉中间一个小正方形。以上都是在二维平面上操作，增加一维可以吗?当然可以。
其实数学家就是这样想问题的：不断推广，力求得到更一般性、更普适的结论。
    在计算机上实际生成谢氏三角形，有许多种方法。先介绍一种最难理解但又最简单
的方法。
    这是一个奇妙的算法，只用到了一个关键语句“IF (x and y)=0 THEN PutPixel…
…”。初看起来这似乎不可能，实际上这里用到了帕斯卡(B.Pascal,1623-1662)三角形
二进制坐标表示的理论。要严格证明此算法的有效性，需要回顾大数学家库默尔(E.E.K
ummer,1810-1893) 于1852年的一个研究结果，这里只简要作些解释。此算法并不实际去
计算谢氏三角形，而是 就平面上的所有点(x,y)，判断它们的颜色，确定每一点是“白
”还是“黑”。如果 对某一点判断的结果是“白”，则该点不属于帕斯卡三角形；如果
结果是“黑”，则该点属 于帕斯卡三角形，给它标上颜色(当然不限于黑色了)。因此需
要做两个循环。
    那么对于平面上的任一点(x,y)是如何判断其颜色的呢?先说明针对帕斯卡三角形PO
Q而定义的一种坐标系。设沿OP边为x轴，沿OQ轴为y 轴，此坐标系一般说来不是直角的
，x轴与y轴的夹角∠POQ可以任意 取。假设图上三个点的坐标是：A(5，2)，B(3，3)，
C(2，6)。把它 们的坐标写成二进制形式有：
A(101，010)，B(011，011)，C(010，110)
把各个二进制坐标上下对齐进行比较，如果某栏出现两个1，则该点标为“白”，否则该
点标为“黑”。照此规则，A点为“白”，B点为“黑”，C点为“黑” 。
Program Sierpinski_Gasket_1996_11_14;
uses Graph;
var
x,y:integer;
Gd,Gm:integer;
begin
Gd:=VGA; Gm:=VGAHi;
Initgraph(Gd,Gm,’D:\\PASCAL’);
if GraphResult <> grOK then Halt(1);
for y:=0 to 511  do ｛可以是0到255｝
for x:=0 to 511 do｛可以是0到255｝
   begin
     If (x and (y-x))=0 then｛本程序只有这一句是最关键的｝
     Putpixel(x+100,500-y,2);
   end;
readln;
CloseGraph;
end.
　
    现在介绍第二种方法(也叫“中点法”)，它比上一种容易理解一些，程序也不难。
本质上这种方法用到了迭代函数系统(IFS)的思想，关于IFS请参见5.4节。
Program SierpGasket1993;
uses graph,Crt;
var
p,a1,a2,b1,b2,c1,c2,x,y:real;
Gd,Gm:integer;
begin
a1:=8;  a2:=253;
b1:=253;  b2:=8;
c1:=253;  c2:=220;
x:=15; y:=15;
Gd:=VGA; Gm:=VGAHi;
Initgraph(Gd,Gm,’D:\\PASCAL’);
if GraphResult <> grOK then Halt(1);
randomize;
repeat
p:=random(100); ｛产生一个随机数p｝
if p<33 then
  begin
     x:=(x+b1)/2; y:=(y+b2)/2; ｛中点法由此得名｝
  end;
if (p<66) and (p>33) then
  begin
     x:=(x+c1)/2; y:=(y+c2)/2;
  end;
if p>66 then
  begin
     x:=(x+a1)/2; y:=(y+a1)/2;
  end;
Putpixel(round(x*2),round(y*2),15);
until KeyPressed;
end.
    生成谢氏四方形地毯、垫片的小程序为Carpet.PAS,您可以尝试按注释行提示的那样
改变d［1,6］、d［4,6］的赋值,这样会得到不同的花样。
{Carpet.PAS}
program SierCarpetFour;
uses
Graph, Crt;
var
Gd,Gm,ErrorCode,i,k,MaxY : integer;
x,y: real;
d:array［1..8,1..6］ of real;
begin
GD:= Detect;InitGraph(Gd,Gm,'d:\pascal');
ErrorCode := GraphResult;
if ErrorCode <> grOk then exit;
MaxY := GetMaxY;
for i:=1 to 8 do
begin
   d［i,1］:=0.3333333333;
   d［i,2］:=0;d［i,3］:=0;
   d［i,4］:=0.3333333333;
end;
d［1,5］:=1;  d［1,6］:=1; {可试验d［1,6］:=MaxY;}
d［2,5］:=MaxY; d［2,6］:=1;
d［3,5］:=1;  d［3,6］:=MaxY;
d［4,5］:=MaxY; d［4,6］:=MaxY div 1; {可尝试除以2, 3, 4}
d［5,5］:=MaxY div 2; d［5,6］:=1;
d［6,5］:=MaxY; d［6,6］:=MaxY div 2;
d［7,5］:=1;  d［7,6］:=MaxY div 2;
d［8,5］:=MaxY div 2; d［8,6］:=MaxY;
MaxY := GetMaxY;
randomize;
x := 0;y := 0;
repeat
i:=i+1;
k := random(8) + 1;
x := d［k,1］*x + d［k,2］*y + d［k,5］;
y := d［k,3］*x + d［k,4］*y + d［k,6］;
putpixel(round(2*x/3)+50,round(2*y/3),4)
readln;
end.

--
心事浩茫连广宇,于无声处听惊雷

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]