파스칼의 삼각형(colab 재귀판+메모화로 고속화)

소개



프랙탈 도형이 나타나는 파스칼의 삼각형(이모티콘으로 50단분)을 브라우저상(Colaboratory)상에서 묘화시켜 보았습니다.

브라우저 (colab)에서 그리기를 시도하고 싶다면 여기에서

↓생성되는 프랙탈 도형(20단분)


참고: 파스칼의 삼각형이란?



파스칼의 삼각형(파스칼의 깡패, 영국: 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)]))



참고:


  • 1 행 추가하는 것만으로 매우 간편한 고속화 그 1 메모화
  • 파스칼의 삼각형과 프랙탈 (Ruby+이모티콘 이용)
  • 파스칼의 삼각형 (wikipedia)
  • 좋은 웹페이지 즐겨찾기