[알고리듬] #79 파스칼의 삼각형

[key word]  이항 계수, 시에르핀스키 삼각형

파이썬 실습창을 열 수 있습니다.실습창 열기

블레즈 파스칼(Blaise Pascal)

 

 

파스칼의 삼각형

파스칼의 삼각형은 이항계수를 삼각형 모양으로 출력한 것입니다.

이항계수(binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수입니다. 

전개식의 계수

 

항의 계수는 조합(combination)의 가짓수와 같습니다. 

각항은 nCr이며, 다음은 계산식입니다.

.      nCr=n!/(r!*(n-r)!)

 

1. 코딩하기

row=10
f=[1]                            #factorial 값을 미리 계산한다.
for i in range(1,row+1): f.append(i*f[i-1])

for n in range(row+1):
​​​​print(' '*3*(row-n),end='')  #각 줄의 출력 위치
​​​​for r in range(n+1):
​​​​​​​​a=f[n]//(f[r]*f[n-r])
​​​​​​​​print(f'{a:6d}',end='')
​​​​print() 
​​​​
'''
출력 결과입니다.
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​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
​​​​​1    10    45   120   210   252   210   120    45    10     1
​​​​​
9번 줄은 다음과 같이 코딩할 수 있습니다.
print('{0:6}'.format(a),end='')
'''

 

● 점화식(recurrence formula)으로 계산할 수도 있습니다. 다음에 공부합니다.

     inductive case: nCr=(n-r+1)/r*nC(r-1)

    base case: nC0=1

 

2.  시에르핀스키 삼각형

홀수만 출력하면 Sierpinski triangle(시에르핀스키 삼각형)입니다.

row=10
f=[1]    #factorial 값을 미리 계산한다.
for i in range(1,row+1): f.append(i*f[i-1])
for n in range(row+1):
​​​​print(' '*3*(row-n),end='')  #각 줄의 출력 위치
​​​​for r in range(n+1):
​​​​​​​​a=f[n]//(f[r]*f[n-r])
​​​​​​​​w=' '*6
​​​​​​​​if a%2!=0:w=f'{a:6}'
​​​​​​​​print(w,end='')
​​​​print() 
​​​​
'''
출력입니다.
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​1
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​1     1
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​1           1
​​​​​​​​​​​​​​​​​​​​​​​​​​1     3     3     1
​​​​​​​​​​​​​​​​​​​​​​​1                       1
​​​​​​​​​​​​​​​​​​​​1     5                 5     1
​​​​​​​​​​​​​​​​​1          15          15           1
​​​​​​​​​​​​​​1     7    21    35    35    21     7     1
​​​​​​​​​​​1                                               1
​​​​​​​​1     9                                         9     1
​​​​​1          45                                  45           1
​​​​​
'''

 

3. 시에르핀스키 삼각형(거북이 그림)

홀수이면 삼각형을 그렸습니다.

from turtle import*
from math import*                                     # 높이 계산에 sin 사용
from random import*                                   # 삼각형의 색깔
row=15                                                # 높이의 개수
f=[1]                                                 # 팩토리얼 값 미리 구함 
for i in range(1,row+1): f.append(i*f[i-1])
speed(0)
d=20                                                  # 삼각형의 한 변의 길이
for n in range(row+1):
​​​​for r in range(n+1):
​​​​​​​​a=f[n]//(f[r]*f[n-r])
​​​​​​​​if a%2:                                       # a가 홀수이면 
​​​​​​​​​​​​x,y=d*r-d/2*n,n*(-d*sin(60*3.14/180))+150 # 삼각형 그릴 위치
​​​​​​​​​​​​up(); goto(x,y); down()
​​​​​​​​​​​​r=randint(0,255)
​​​​​​​​​​​​g=randint(0,255)
​​​​​​​​​​​​b=randint(0,255)
​​​​​​​​​​​​fillcolor((r,g,b))
​​​​​​​​​​​​begin_fill()
​​​​​​​​​​​​for i in range(3):                        # 삼각형 그림
​​​​​​​​​​​​​​​​fd(d)
​​​​​​​​​​​​​​​​lt(120)
​​​​​​​​​​​​end_fill()    
ht()                                                  # 거북이 숨김          
done()

 

여러가지로 즐겨보세요.

수고하셨습니다.

안녕!