Taratta: ページの作成:「

 # フィボナッチ数 # F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1} で定義される  def fibo1(n):     if (n == 0):         return 0     elif (n == 1):         r…」

2022-11-13T05:55:02Z

ページの作成:「<pre> # フィボナッチ数 # F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1} で定義される def fibo1(n): if (n == 0): return 0 elif (n == 1): r…」

新規ページ

<pre>
# フィボナッチ数
# F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1} で定義される

def fibo1(n):
if (n == 0):
return 0
elif (n == 1):
return 1
else:
return fibo1(n-2)+fibo1(n-1)

# 自分自身を２回再帰呼び出ししているので、n が大きくなると
# かかる時間が指数関数的に増大する。
# fibo1(35)
# で答えが出るまでに 5 秒くらい。
# それより大きい数では飛躍的にかかる時間が長くなる。

# フィボナッチ数(if 文と for 文を使って)

def fibo2(n):
if (n == 0):
return 0
elif (n == 1):
return 1
else:
k0 = 0
k1 = 1
for i in range(2, n+1):
k2 = k1 + k0
k0 = k1
k1 = k2
return k2

# fibo2(100000)
# くらいでも一瞬で答えが出る

# フィボナッチ数(浜田の解法1)

# n が奇数の時、F_n = F_{(n+1)/2}^2 + F_{(n-1)/2}^2
# n が偶数の時、F_n = F_{n/2 + 1}^2 - F_{n/2 - 1}^2
# という性質を使う

def fibo3(n):
if (n == 0):
return 0
elif (n == 1):
return 1
elif (n%2 == 1):
return fibo2(n//2+1)**2 + fibo2(n//2)**2
else:
return fibo2(n//2+1)**2 - fibo2(n//2-1)**2

# フィボナッチ数(浜田の解法2)

# fibo3 では実は fibo2 を2回呼び出しているので余分に繰り返し
# 計算していることになるので、さらに改善できるはずである
# (効果が目に見えるのはよほど大きい n の場合になるが)。
# この関係式を繰り返し適用することにより、計算量オーダーをさらに
# 改善できることがわかる。
# 下に、fibo_i(n) という、隣り合うフィボナッチ数のペアを返す内部関数を
# 定義し、その内部関数を呼び出す形で fibo4(n) を定義する。

def fibo_i(n):
if (n == 0):
return [1, 0]
elif (n == 1):
return [0, 1]
elif (n == 2):
return [1, 1]
else:
l = fibo_i(n//2)
a = l[0]
b = l[1]
c = l[0]+l[1]
if (n%2 == 1):
return [c**2 - a**2, c**2 + b**2]
else:
return [b**2 + a**2, c**2 - a**2]

def fibo4(n):
if (n == 0):
return 0
elif (n == 1):
return 1
elif (n == 2):
return 1
else:
l = fibo_i(n//2)
a = l[0]
b = l[1]
c = l[0]+l[1]
if (n%2 == 1):
return c**2 + b**2
else:
return c**2 - a**2
</pre>

この他にも色々試して、追加してください。

[[Category:学習ガイド]]

Python実行例フィボナッチ数 - 版の履歴

Taratta: ページの作成:「
# フィボナッチ数 # F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1} で定義される def fibo1(n): if (n == 0): return 0 elif (n == 1): r…」

Python実行例 フィボナッチ数 - 版の履歴

Taratta: ページの作成:「 # フィボナッチ数 # F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1} で定義される def fibo1(n): if (n == 0): return 0 elif (n == 1): r…」

Python実行例フィボナッチ数 - 版の履歴

Taratta: ページの作成:「
# フィボナッチ数 # F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1} で定義される def fibo1(n): if (n == 0): return 0 elif (n == 1): r…」