[python] 피보나치 수열 구현

• 문제 분류: 수학

[문제]

피보나치 수열 (Fibonacci Sequence)란?

피보나치 수열은 바로 앞의 두 항의 값을 합한 값이 다음의 항의 값이 된다. 

 F0=0, F1=1이다. 

 

<Definition>

:재귀적 형식(recursive definition)을 취한다.

(a) If n=0 or n=1, then Fn=n

(b) If n>1, then Fn=Fn-2+Fn-1

 

---

[코드]

1. recursive implementation

def fibon1(n):
    if n<=0:
        return 0

    elif n==1:
        return 1

    else:
        return fibon1(n-2)+fibon1(n-1)



user=int(input("숫자를 입력하세요: "))
a=fibon1(user)
print("fibonacci sequence of",user," is ",a)

2. literative implementation

def fibon2(n):
    first=0
    second=1
    
    if n==0:
        second=0

    elif n>=1:
        for i in range(1,n):
            third=first+second
            first=second
            second=third




    return second

user=int(input("숫자를 입력하세요: "))
a=fibon2(user)
print("fibonacci sequence of",user," is ",a)

 

3. 임의의 n값에 대해 F0 부터 Fn 까지 모든 값을 으로 출력

def fibon2(n):
    first=0
    second=1
    
    if n==0:
        second=0

    elif n>=1:
        for i in range(1,n):
            third=first+second
            first=second
            second=third




    return second

user=int(input("숫자를 입력하세요: "))
print("0부터", user, "까지 피보나치수열의 값을 출력합니다.")

i=0
while i<=user:
    a=fibon2(i)
    print("fibonacci sequence of",i," is ",a)
    i=i+1

 

4. 임의의 두 x1 과 x2 (x1 ≤ x2) 값에 대해 x1 보다 같거나 크고 x2 보다 같거나 작은 모든 피보나치 수를 계산

def sub_fibonacci(start,end):
    
    first=0
    second=1
    result=[]
    
    if start<=0:
        result.append(int("0"))

    while True:
        third=first+second
        if start<=second and end>=second:
            result.append(second)
        first=second
        second=third
        if second>end:
            break


    return result
        

start,end=input("범위의 처음과 끝 숫자를 입력하세요: ").split()
start=int(start)
end=int(end)
#n=int(input("찾을 숫자: "))
res=sub_fibonacci(start, end)
res=[int (i) for i in res]
print("범위 안에 있는 피보나치 수열숫자들은 ",res,"이다.")