正月はフラクタル
という風習についてはこちら。
以前公務員試験で出題された問題だそうです。
- 平面上の 3 点 A,B,C を決めます。
- ここでは A=(100,100),B=(200,100),C=(150,200) とします。
- 点 A をスタート地点とします。
- 以下を繰り返します。
- 現在地に点を打ちます。
- A,B,C からランダムに 1 点選び、現在地との中点をとり、新しい現在地とします。
さて、どんな図形が浮かび上がってくるでしょうか。
ちなみに PostScript で書くとこんな感じです。
%!PS gsave 100 100 10000{ 2 copy .2 .2 rectfill [[100 100][200 100][150 200]]rand 3 mod get{ 3 2 roll add 2 div }forall }repeat pop pop grestore
- 答え
- ほぼシェルピンスキー・ガスケット 。再帰も二項定理もセルオートマトンも無しでシェルピンスキー・ガスケットがだいたい書けてしまいます。
- おまけ
- シェルピンスキー・カーペット の場合。正方形の頂点と辺の中点の 8 点からランダムに選び、現在地まで結んだ点を 1:2 に分ける点を新しい現在地にすれば書けます。
%!PS gsave 100 100 50000{ 2 copy .2 .2 rectfill [ [100 100][100 150][100 200][150 200] [200 200][200 150][200 100][150 100] ]rand 8 mod get{ 2 mul 3 2 roll add 3 div }forall }repeat pop pop grestore