Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonでn番目の項までのフィボナッチ数列の結果を見つけるプログラム

数nがあるとします。最初のn個のフィボナッチ項の合計を見つける必要があります（最大n個の項のフィボナッチシーケンス）。答えが大きすぎる場合は、10 ^ 8+7を法とする結果を返します。

したがって、入力がn =8の場合、最初のいくつかのフィボナッチ項は0 + 1 + 1 +2 + 3 + 5 + 8 + 13 =33

であるため、出力は33になります。

これを解決するには、次の手順に従います-

  • m：=10 ^ 8 + 7
  • メモ：=新しい地図
  • 関数solve（）を定義します。これにはn、mがかかります
  • nがメモにある場合、
    • メモを返す[n]
  • memo [n]：=n <2の場合はn、それ以外の場合（solve（n-1、m）+solve（n-2、m））mod m
  • メモを返す[n]
  • メインメソッドからメモ値のリストを取得し、それらの合計を取得します。

例

理解を深めるために、次の実装を見てみましょう-

m = 10**8+7
memo = {}
def solve(n, m):
   if n in memo:
      return memo[n]
   memo[n] = n if n < 2 else (solve(n-1, m)+solve(n-2, m)) % m
   return memo[n]

n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))

入力

8

出力

33

  1. Pythonで特定の漸化式のn番目の項を検索します

    bnと呼ばれる数列があるとすると、これはb1=1やbn+1 / bn=2nのような漸化式を使用して表されます。与えられたnのlog2（bn）の値を見つける必要があります。 したがって、入力が6の場合、出力はlog2（bn）=（n *（n-1））/ 2 =（6 *（6-1））/ 2 =15として5になります。 この関係を次のように解くことで、この問題を解くことができます- b n + 1 / b n =2 n b n / b n-1 =2 n-1 … b 2 / b 1 =2 1 、上記のすべてを掛けると、次のようになります （b n +

  2. フィボナッチ数列のn番目の倍数のPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −数が与えられているので、フィボナッチ数で数kのn番目の倍数を見つける必要があります。 この問題の解決策については、以下で説明します- 例 # find function def find(k, n):    f1 = 0    f2 = 1    i =2;    #fibonacci recursion    while i!=0:       f3 = f1 + f2; &