構造謝爾賓斯基三角
<div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even"> <p>關於<a href="https://bit.ly/3SUqIts" target="_blank">謝爾賓斯基三角（Sierpinski triangle）</a>，是由波蘭數學家謝爾賓斯基在1915年提出的碎形圖案，最基本的構造方式是透過幾何來處理，而我在先前專欄文章〈<a href="https://www.ithome.com.tw/voice/110732" target="_blank">遞迴、碎形與數學</a>〉就談過作法：可以畫一個實心三角形，去掉邊長中點形成的三角形，接著針對新的小實心三角形、不斷重複以上的動作，之後就能夠產生謝爾賓斯基三角。</p> <p><span style="font-size:28px;"><strong>幾何／L-system／細胞自動機</strong></span></p> <p>使用程式碼描述謝爾賓斯基三角，顯得有點囉嗦，如果我們使用先前專欄<a href="https://www.ithome.com.tw/voice/137795" target="_blank">〈碎形與L-system〉</a>談過的L-system，此時，可以從公理（axiom）F-G-G出發，使用規則F->F-G+F+G-F與G->GG來衍生，等到衍生結束之後，以F替代G，最後依衍生出來的符號串——F是前進、+、-與左轉、右轉來繪圖，就能繪製謝爾賓斯基三角。</p> <p>談到碎形，略為接觸過電腦繪圖的開發者，應該都會繪製碎形樹，例如，<a href="https://bit.ly/3ArbPYo" target="_blank">〈tree〉</a>是我基於p5.js的碎形樹實作，那麼，你有辦法將碎形樹變成謝爾賓斯基三角嗎？其實，這並不困難，只要每次衍生三個分支，而分支之間的角度為120度，以及每次新分支會是上一次遞迴分支的一半長度，依此處理之後，就能得到謝爾賓斯基三角。</p> <p>原理並不難理解，畢竟120度分支會構成正三角形，至於每次新分支是上一分支的一半長度，這不就是對應取三角形邊長一半的意思嗎？有興趣看看p5.js實作的人，可以參考我寫的<a href="https://bit.ly/3dBZhEA" target="_blank">〈TT Transformer〉</a>。</p> <p>對於直角座標，如果x座標、y座標使用(x?y)運算，其中的?，可以是+、-、*、/、^、&、|、%等運算子，將得到的數字在(x,y)處畫出來——圖片可參考<a href="https://bit.ly/3Cbwnp1" target="_blank">〈x?y〉這則推文</a>，我們即可觀察到謝爾賓斯基三角嗎？使用&運算而x&y為0的圖案就是了，在<a href="https://bit.ly/3pun6AQ" target="_blank">〈Matplotlib散佈圖〉</a>裡的謝爾賓斯基三角，就是這麼畫出來的。</p> <p>基於位元邏輯運算得到謝爾賓斯基三角，並不是偶然，而是一種細胞自動機的變化，我在先前專欄文章<a href="https://www.ithome.com.tw/voice/139532" target="_blank">〈細胞自動機〉</a>也談過，1983年英國電腦科學家Stephen Wolfram發表的基本細胞自動機（Elementary cellular automaton），在規則90時所畫出來的圖案，就是謝爾賓斯基三角。</p> <p><span style="font-size:28px;"><strong>巴斯卡三角／河內塔</strong></span></p> <p>謝爾賓斯基三角的構造方式如此多元，甚至可能藏在意想不到之處，例如，在<a href="https://bit.ly/3zUFxDC" target="_blank">巴斯卡三角</a>裡，也隱含著謝爾賓斯基三角。我們可以試著將巴斯卡三角裡每個數字，繪製在一個圓（或方格），然後去掉2倍數的圓，就能得到謝爾賓斯基三角。</p> <p>其實，我們也可以去掉巴斯卡三角裡3或4或5的倍數，這可以得到不同的圖樣，有興趣了解的人，可參考<a href="https://bit.ly/3Cbjk73" target="_blank">〈Pascal's Triangle Patterns〉</a>。</p> <p>或許跟謝爾賓斯基三角有著最神祕關係的，就是1883年法國數學家Edouard Lucas提出的河內塔吧！若有三個柱子、三個盤子，使用(abc)來表示小、中、大三個盤子，分別在a、b、c柱子，例如小中大盤都在1柱，就使用(111)代表當時河內塔的狀態，小中大盤各在2、1、1柱，就使用(211)表示，小中大盤各在3、1、1柱，就使用(311)。</p> <p>由於(111)可以轉移至(211)或(311)，相對地，(211)、(311)都可以轉移至(111)，而(211)與(311)彼此間也可以轉換，若將可轉換的狀態間連線，能夠構成以下的三角形：</p> <p class="rtecenter"><img alt="" src="https://s4.itho.me/sites/default/files/images/hanoi-tower-4.jpg" style="width: 218px;" /></p> <p>如果將河內塔全部的狀態轉換，依以上方式連線，構成的河內塔狀態轉移圖，就會是謝爾賓斯基三角；若有n個盤子，可以用n位數來表示從小至大的四個盤子，分別在哪個柱子上，例如，(2111)表示最小的盤子在2號柱，另三個盤子在1號柱……，那麼狀態轉移圖會變得更大，也就是得到一個更大的謝爾賓斯基三角，若你想看到呈現的形狀與關係的圖片，可參考<a href="https://bit.ly/3R6FmfN" target="_blank">〈河內塔〉</a>。</p> <p><span style="font-size:28px;"><strong>混沌遊戲</strong></span></p> <p>如果想玩個不插電遊戲來畫出謝爾賓斯基三角，巴斯卡三角是個不錯的方式；另一種方式是丟骰子，首先點出三角形的三個頂點ABC，隨機在三角形內部選一點p0，然後開始丟骰子（如果得到1或2，選擇頂點A，3或4選B，5或6選C），在選擇的頂點與點p0間取中點畫出p1，繼續丟骰子，在選擇的頂點與點p1間取中點畫出p2，丟骰子，在選擇的頂點與點p2間取中點畫出p3……</p> <p>如果努力不懈地丟骰子，畫出來的點會逐漸形成謝爾賓斯基三角的圖樣，我們可以在<a href="https://bit.ly/3QMVpil" target="_blank">〈Chaos Game - Numberphile〉</a>看到這個過程。其實，丟骰子只是個隨機選取頂點的過程，而這個不插電的遊戲稱為<a href="https://bit.ly/3PpvsEt" target="_blank">混沌遊戲（Chaos game）</a>。</p> <p>被稱為混沌的原因，是因為最初的點是隨機選取的，而每次也是隨機選取頂點，乍看似乎會得到個混沌不明的結果，最後卻得到了謝爾賓斯基三角。基本上，這個遊戲可以擴展至三維，使用第四個頂點構成正四面體，每次隨機選取四個頂點之一，其餘步驟同上，如此一來，就可以構成謝爾賓斯基四面體（Sierpinski Tetrahedron）。</p> <p>其實，混沌之中並不完全是混沌，畢竟這裡隱含著每次迭代時的固定規則，若使用一般化來表示，對任一點進行pk，透過迭代函式f可得到pk+1點，也就是pk+1=f(pk)，這稱為迭代函式系統（iterated function system, IFS），而迭代函式系統是產生碎形的一種方式。</p> <p>當然，在混沌中，並不是任何規則都會收斂成某個圖樣（或稱為狀態），例如，方才的玩法對於正方形的四個頂點，並不會產生碎形，然而，若我們試著在選取頂點時加些規則（或稱為限制），就有可能產生碎形（可參考<a href="https://en.wikipedia.org/wiki/Chaos_game" target="_blank">維基百科〈Chaos game〉的圖片</a>）。</p> <p>如果混沌裡的規則（也就是迭代函式）可以收斂至某個狀態，該狀態被稱為迭代函式系統的吸引子（attractor）或不動點（fixed point）。對此，你是否想到類似的系統呢？我在先前專欄文章〈<a href="https://www.ithome.com.tw/voice/149092" target="_blank">淺談反應擴散系統</a>〉、〈<a href="https://www.ithome.com.tw/voice/151846" target="_blank">實現差別生長演算</a>〉談過的，就是類似的概念！</p> <p><span style="font-size:28px;"><strong>不同角度而息息相關</strong></span></p> <p>為何河內塔狀態轉移圖會出現謝爾賓斯基三角？關於數學上的道理，你可以參考〈<a href="https://bit.ly/3JYasUi" target="_blank">Sierpinski Gasket and Tower of Hanoi</a>〉；從另一角度來看，狀態轉移是自動機的範疇，而基本細胞自動機規則90可以繪出謝爾賓斯基三角，河內塔狀態轉移圖看似謝爾賓斯基三角，好像也就可以理解了。</p> <p>類似地，混沌遊戲可以繪出謝爾賓斯基三角，也可以從數學上證明，有興趣可參考<a href="https://bit.ly/3JZXJjW" target="_blank">〈Chaos Game〉</a>；或者應該說，碎形、自動機、混沌理論、人工生命、人工智慧等，都是彼此息息相關，從不同角度解釋某些現象的課題，能夠發現同一現象的不同構造方式，正是探索電腦科學最美妙的過程。</p> </div></div></div><div class="field field-name-field-tags field-type-taxonomy-term-reference field-label-above"><div class="field-label">Tags: </div><div class="field-items"><div class="field-item even"><a href="/tags/%E7%A8%8B%E5%BC%8F%E4%BA%BA">程式人</a></div><div class="field-item odd"><a href="/tags/%E6%9E%97%E4%BF%A1%E8%89%AF">林信良</a></div><div class="field-item even"><a href="/tags/%E7%A8%8B%E5%BC%8F%E5%AD%B8%E7%BF%92">程式學習</a></div><div class="field-item odd"><a href="/tags/%E8%AC%9D%E7%88%BE%E8%B3%93%E6%96%AF%E5%9F%BA%E4%B8%89%E8%A7%92">謝爾賓斯基三角</a></div><div class="field-item even"><a href="/tags/sierpinski-triangle">Sierpinski triangle</a></div><div class="field-item odd"><a href="/tags/%E5%B7%B4%E6%96%AF%E5%8D%A1%E4%B8%89%E8%A7%92">巴斯卡三角</a></div><div class="field-item even"><a href="/tags/%E6%B7%B7%E6%B2%8C%E9%81%8A%E6%88%B2">混沌遊戲</a></div><div class="field-item odd"><a href="/tags/%E8%87%AA%E5%8B%95%E6%A9%9F">自動機</a></div></div></div>
