파스칼의 삼각형(colab 재귀판+메모화로 고속화)
10422 단어 math프랙탈 모양파이썬초보자colaboratory
소개
프랙탈 도형이 나타나는 파스칼의 삼각형(이모티콘으로 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)]))
참고:
def c(n,k):
return 1 if(k<=0 or n<=k) else c(n-1, k-1) + c(n-1, k)
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
'''
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)]))
Reference
이 문제에 관하여(파스칼의 삼각형(colab 재귀판+메모화로 고속화)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/zaq9/items/8348d1c9296643430fff텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)