[알고리듬] #51 피보나치 수열

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

 

 

 

1. 피보나치 수열

 

피보나치 수는 정수로 된 다음과 같은 수열입니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

 

피보나치 수는 다음과 같이 정의됩니다.

Fn = Fn-1 + Fn-2

시작은 F0 = 0이고 F1 = 1

 

피보나치 수열(Fibonacci sequence)은 피보나치로 더 잘 알려진 수학자 레오나르도 피사( Leonardo of Pisa)의 이름을 따서 명명되었습니다. 그의 저서 "Liber Abaci"(1202년 출판)에서 그는 이 수열을 토끼를 계산하는 방법으로 소개했습니다. 그의 피보나치 수열은 F1 = 1로 시작하는 반면, 현대 수학에서는 F0 = 0으로 시작합니다. 그러나 이는 수열의 다른 항에는 영향을 미치지 않습니다.

 

피보나치 수는 다음 조건을 충족하는 가상의 토끼 개체수의 결과입니다.

• 새로 태어난 토끼 한 쌍(수컷 한 마리, 암컷 한 마리)이 초기 개체수를 형성합니다.
• 이 토끼들은 한 달이 되면 짝짓기를 할 수 있으므로 두 번째 달 말에 암컷은 또 다른 한 쌍의 토끼를 낳을 수 있습니다
• 이 토끼들은 죽지않습니다.
• 짝짓기릏 한 토끼 쌍은 두 번째 달부터 매달 한 쌍(수컷 1마리, 암컷 1마리)의 새로운 쌍을 낳습니다.

피보나치 수는 n개월 후 토끼 쌍의 수입니다. 즉, 10개월 후에는 F10 = 55 쌍의 토끼를 갖게 됩니다.

F10 = 55는 반복적 해결 방식(iterative solution method)으로 구할 수 있습니다.

 

토끼 쌍의 수를 입력받아서,

몇 개월 후인가 구하여 보세요. 

 

바로 코딩하여 보세요. 복습입니다.

pair=int(input())
a,b=0,1
n=0
while a<pair:
    a,b=b,a+b
    n+=1
print(n)

2. 트리보나치 수열

트리보나치 수열(tribonacci sequence)은 각 항이 이전 세 항의 합인 수열입니다. 

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777, 6 15693474, 1132436852…

트리보나치 수열의 일반적인 형태입니다.  

a(n) = a(n-1) + a(n-2) + a(n-3), 
with
a(0) = a(1) = 0, a(2) = 1  #처음 3개의 항은 0, 0, 1

 

n 값을 입력받아서,

처음부터 n개의  트리보나치  수열을 출력하세요.

 

다음은 예입니다. 

Input : 5
Output : 0, 0, 1, 1, 2

Input : 10
Output : 0, 0, 1, 1, 2, 4, 7, 13, 24, 44

Input : 20
Output : 0, 0, 1, 1, 2, 4, 7, 13, 24, 44,
         81, 149, 274, 504, 927, 1705, 3136, 
          5768, 10609, 19513

 

코딩하여 보세요.

n=int(input())
r=[]                      # 수열을 모을 예정
a,b,c=0,0,1               # 초기값(initial value)
i=1                       # 항(item)의 개수를 헤아림
while i<=n:
    r.append(a)           # 항을 모음
    a,b,c=b,c,a+b+c       
    i+=1
w=', '.join(map(str,r))   # 한 사이에 ','를 넣음 
print(w)

 

n-nacci(엔 나치) 수열은 이전(앞) n개 항의 합으로 다음 항을 만드는 수열입니다.

n=2는 피보나치, n=3은 트리보나치, n=4는 tetranacci(테트라나치) 등으로 부릅니다.

 

수고하셨습니다.

오늘 끝.