Matlab 教材:遞迴範例--Koch 雪花

動態系統的研究發現,某些看似低等的生物之所以能夠表現出令人驚訝的、 看似經過深思熟慮的行動或組織,其實只是遵循非常簡單的指令。 大量而重複地遵循非常簡單的動作,就能產生令人迷炫的複雜成果。 有很多以這個概念發展出來的科普讀物或科幻小說;以科普而言, 《混沌》和《複雜》都是暢銷的作品,都由天下文化翻譯出版; 以科幻而言,Michael Crichton 是個中高手, 他的成名作《侏儸紀公園》和續集《失落的世界》, 以及 2003 年的近作《奈米獵殺》都有應用動態系統於生物學的情節在內。

這種「寓複雜於簡單」的概念,早在 1904 年的『Koch 雪花』便出場了, 它的構成元素是:『拿一根線段,截去中央的三分之一, 用那個長度造成一個缺了底邊的正三角形,與原來的線段接在一起, 形成一個「中央凸起三分之一的折線段」』。 我們稱這個簡單的動作為「翹起中間三分之一」。 就是這麼一個簡單的規則,重複實施在每一節線段上,就會出現複雜的景象。

所謂的「翹起」有兩個方向,要正式寫程式時,必須指定一致的翹起方向。 下面的程式是,給定一個線段的起點和終點, 假設線段的方向是從起點指向終點,而翹起的方向則是線段方向的左側。 利用簡單的幾何和代數,只要給定起點和終點的座標, 就可以計算出來翹起的兩個底部端點座標和翹起的頂點座標。 因此,在電腦上實現所謂的「翹起」, 其實就是根據輸入的一個 (有方向性) 的線段,畫出四個線段。 例如給一個從 (0,0) 到 (1,0) 的線段,如左圖。 「翹起」之後,變成相連的四個線段,如右圖。

 

上述想法可以繼續做下去:一根線段「翹起」成四根線段; 每一根線段可以再「翹起」成四根線段,共 16 根; 而每一根線段可以再「翹起」成四根線段,共 64 根,依此類推。 只要把方向抓對,那麼可以控制每一個線段都是向「外」翹起, 如下面兩張圖。

 

所以,上述想法本身就是一種遞迴。用 Matlab 很容易寫出來, 因為 Matlab 本來就有測繪功能:給兩點,Matlab 可以畫出連線的線段。 這是 [製圖--折線圖] 和 [多重折線圖] 那兩節講解的功能。 我們寫一個 koch() 函式來實現這個想法。

koch() 應該取得三個參數,如

koch(p, q, n)
其中 p 是起點的平面座標向量,例如 p=[0;0];, 而 q 是起點的平面座標向量,例如 q=[1;0];。 第三個參數 n 是一個無號整數 (0 或正整數), 代表要「翹起」幾個回合; 所謂一個回合,是指將每一根線段都「翹起」一次。 前面那四張圖,就分別是 n 為 0, 1, 2 和 3 的效果。

koch() 的想法很巧妙: 如果指定的「回合」是 0,就用 plot() 函式把線段畫出來。 否則就把輸入的線段「翹起」成四根線段, 把每一根線段送去下一回合 koch() 去做 (把回合數減一)。 程式如下:

function koch(p,q,n)
if (n==0)
    plot([p(1);q(1)], [p(2);q(2)], 'LineWidth',4,'Color','red');
    hold on;
else
    c = q-p;
    c = [-c(2); c(1)];
    c = (p+q)/2 + c/sqrt(12);   % 求出「向左側翹起 1/3」的頂點座標向量 c
    a = (2*p+q)/3;              % 求出從 p 到 q 的 1/3 處端點座標向量 a
    b = (p+2*q)/3;              % 求出從 p 到 q 的 2/3 處端點座標向量 b
    koch(p, a, n-1);            % 對 pa 線段做下一回合
    koch(a, c, n-1);            % 對 ac 線段做下一回合
    koch(c, b, n-1);            % 對 cb 線段做下一回合
    koch(b, q, n-1);            % 對 bq 線段做下一回合
end
koch() 程式只有兩個技術需要稍加解釋。 首先,plot() 的前兩個參數只是要話 p 至 q 的線段而已,沒什麼特別。 plot() 的後四個參數是要 Matlab 用 4 point 粗的紅色線條來畫折線圖。 而 hold on 是讓以前畫的圖保持在圖形視窗裡, 否則新的 plot() 指令會自動清除留在圖形視窗裡面的任何舊圖。

使用 koch() 需注意的是,pq 必須是向量。 譬如要說 p=[0;0];q=[1;0]; 而不是說 p=[0,0];q=[1,0];。 其實很容易改寫 koch() 來幫助使用者不受這個限制,留給讀者當習題。

koch() 會打開 Matlab 的圖形視窗,在裡面畫圖。 但是 koch() 執行之後的 hold 狀態是 on, 需自行將它關閉,以免以後畫的所有圖都疊在一起了。 此外,koch() 也沒有為我們處理座標邊框,因此圖形的比例不太對, 這也需要在 koch() 執行之後再處理。以下是一組例子。

p=[0;0];
q=[1;0];
koch(p,q,2)
hold off
axis([0 1 -0.2 0.8])
axis square
axis off

習題

  1. 請修改 koch() 做「驗明輸入」動作, 使得如果發現 pq 的維度不是 2, 則發出錯誤訊息且中斷執行。而如果 pq 是二維序列, 則幫他轉換成二維向量,並繼續執行。
  2. 請根據這一節教材針對 koch() 的介紹與描述, 為 koch() 寫線上說明文件。
  3. 請利用 Matlab 的 koch() 函式畫出第二回合的 Koch 雪花,如下圖

  4. 請利用 Matlab 的 koch() 函式畫出第四回合的 Koch 雪花,如下圖

[BCC16-B]
單維彰 (2004/05/06) ---
[Prev] [Next] [Up]