[알고리듬] #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()

 

여러가지로 즐겨보세요.

수고하셨습니다.

안녕!