反復と再帰でウサギの出産のpythonプログラムをそれぞれ書く(フィボナッチ数列)


質問:
ウサギのペアが生まれて、3月から、毎月1対のウサギを生んで、生まれたウサギも3月から毎月1対のウサギを生んで、n年後、全部で何匹のウサギがありますか?

1
2
3
4
5
6
7
8
9
10

n
数量(対)
1
1
2
3
5
8
13
21
34
55

F(n-2)+F(n-1)
考え方:前の2ヶ月のウサギの対数はすべて1対で、3ヶ月目からウサギの対数は前の2ヶ月のウサギの対数の和です
F(1)=F(2)=1 F(n)=F(n-2)+F(n-1)
再帰的なアプローチを使用:
def F2(temp):
    if temp<1:
        print("    !")
        return -1
    
    if (temp==1 or temp==2):
        return 1
    else:
        return F2(temp-2)+F2(temp-1)


temp=int(input("        :"))
result=F2(temp)
print("%d   , %d    "%(temp,result))

反復を使用する方法:
def F1(n):
    n1=1
    n2=1
    n3=1
    if n<1:
        print("    !")
        return -1
    while (n-2)>0:
        n3=n2+n1
        n2=n3
        n1=n2
        n-=1

    return n3
n=int(input("        :"))
result=F1(n)
if result!=-1:
    print("%d   ,   %d    !"%(n,result))
    


違い:反復アルゴリズムの効率は再帰アルゴリズムより効率が高く、再帰構想は問題の書き方を直接体現している.