反復と再帰でウサギの出産の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)
再帰的なアプローチを使用:
反復を使用する方法:
違い:反復アルゴリズムの効率は再帰アルゴリズムより効率が高く、再帰構想は問題の書き方を直接体現している.
ウサギのペアが生まれて、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))
違い:反復アルゴリズムの効率は再帰アルゴリズムより効率が高く、再帰構想は問題の書き方を直接体現している.