#はじめに
フラクタル図形が表れるパスカルの三角形(絵文字で50段分)をブラウザ上(Colaboratory)上で描画させてみました。
##参考:パスカルの三角形とは
パスカルの三角形(パスカルのさんかくけい、英: Pascal's triangle)は、二項展開における係数を三角形状に並べたものである ( wikipedia )
この三角形の作り方は単純なルールに基づいている。まず最上段に 1 を配置する。それより下の行はその位置の右上の数と左上の数の和を配置する。例えば、5段目の左から2番目には、左上の 1 と右上の 3 の合計である 4 が入る。このようにして数を並べると、上から n 段目、左から k 番目の数は、二項係数
に等しい。これは、パスカルによって示された以下の式に基づいている。
負でない整数 n ≥ k に対して
##描画用のソースコード(&簡単な流れ)
再帰を使うとパスカルの三角形の漸化式はスムーズに書けます。
def c(n,k):
return 1 if(k<=0 or n<=k) else c(n-1, k-1) + c(n-1, k)
テストとして上記の式を(リスト形式で)10段分表示。
for i in range(10):
print([c(i,j) for j in range(i+1)])
'''OUTPUT:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
'''
少しだけアレンジし、剰余利用+文字列でリスト展開表示
def c(n,k):
return 1 if(k<=0 or n<=k) else ( c(n-1, k-1) + c(n-1, k) ) %4
for i in range(10):
print(' '.join([ str( c(i,j)) for j in range(i+1) ] ))
'''OUTPUT:
1
1 1
1 2 1
1 3 3 1
1 0 2 0 1
1 1 2 2 1 1
1 2 3 0 3 2 1
1 3 1 3 3 1 3 1
1 0 0 0 2 0 0 0 1
1 1 0 0 2 2 0 0 1 1
'''
絵文字を使ったアレンジをすると…(遅いので20段まで、結果はタイトル下の画像)
e = ['🍈','🍎','🍇','🍊']
for i in range(20):
print(' '.join([ str(e[c(i,j)%4]) for j in range(i+1)]))
##メモ化で簡単に超高速化
同じ計算が繰り返される再帰計算の場合、「メモ化」を行うと超高速化できます。
方法は一行追加するのみです。
#50段ブラウザで描画させるソースコード(メモ化高速版)
from functools import lru_cache
@lru_cache(maxsize=1000)
def c(n,k):
return 1 if(k<=0 or n<=k) else ( c(n-1, k-1) + c(n-1, k) ) %4
e = ['🍈','🍎','🍇','🍊']
for i in range(50):
print(' '.join([ str(e[c(i,j)%4]) for j in range(i+1)]))
#参考:
-
パスカルの三角形とフラクタル (Ruby+絵文字利用)