Pythonを使用してフィボナッチ関数を実装する方法

この記事では、Python を使用してフィボナッチ関数を実装する方法を主に紹介します。必要な方は参考にしてください。

フィボナッチ フィボナッチ数列は、任意のプログラミング言語を学べばおそらく実行できるでしょう。 。 これをみて。

私は最近 Python で遊んでいます。Learning Python と Core Python をざっと読んだ後、インターネット上で The Evolution of Python Programmers という興味深い投稿を偶然見つけました。そこで、階乗関数を完成させるために 10 個以上のメソッドを使用する投稿を真似する予定です。ここでは、9 つ​​の異なるスタイルでフィボナッチ関数を作成します。

要件は非常に単純です。nを入力し、n番目のフィボナッチ数を出力します。nは正の整数です

以下は9つの異なるスタイルです:

1) 初めてプログラムを作成するPythonプログラマー:

def fib(n):
  return nth fibonacci number

説明:
初めてプログラムを書く人は、プログラミング言語の構文ではなく、人間の言語の構文に従うことがよくあります。プログラミングが非常に得意な私の友人を例に挙げます。閏年を決定する最初のプログラムでは、次のように直接記述されます。年が閏年の場合、出力される年は閏年であり、それ以外の場合は閏年ではありません。

2) Python を学んだばかりの C プログラマー:

def fib(n):#{
 if n<=2 :
  return 1;
 else:
  return fib(n-1)+fib(n-2);
#}

説明:
初めて Python に触れたとき、プログラム ブロックを分割するために中括弧の代わりにインデントを使用する方法に非常に不満を感じました。適応性があり、各ステートメントの後にターミネータがないため、Python 関数を作成するたびに最初に行うことは、中括弧をコメント アウトし、同時に欠落しているコロンを追加することです。

3) 怠惰な Python プログラマー:

def fib(n):
  return 1 and n<=2 or fib(n-1)+fib(n-2)

説明:
Learning Python を見た後、Python には三項演算子がないことに気付きました。ただし、Python の bool 値は非常に特殊であり (C に似ており、ゼロ以外は true、空以外は true を意味します)、Python の論理ステートメントは短絡評価 (短絡評価) もサポートしていることを考慮すると、これは可能です。模造品？という発言が出てきます。

4) Lazier Python プログラマー:

 fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2)

説明: C# と Scheme で使用した
lambda キーワードは、C# よりも単純で、 Scheme での使用法と非常に似ているので、すぐに慣れました。すぐにそれに。この書き方は、Python シェルでいくつかの小さな関数を宣言するときによく使用されます。

5) データ構造の学習を終えたばかりの Python プログラマー:

def fib(n):
 x,y=0,1
 while(n):
  x,y,n=y,x+y,n-1
 return x

説明:
これまでのフィボナッチ関数はすべてツリー再帰の実装です。少しアルゴリズムを学んだとしても、低コストであることがわかるはずです。この再帰はうまくいきました。ここで、ツリー再帰から対応する反復に変更すると、効率が大幅に向上します。
Python のタプル割り当て機能は、コードを大幅に簡素化できるので、とても気に入っています。たとえば、前の tmp=a;a=b;b=tmp; は、簡潔かつ明確な文 a,b=b,a で直接実装できます。

6) SICP コースを受講している Python プログラマー:

def fib(n):
  def fib_iter(n,x,y):
   if n==0 : return x
   else : return fib_iter(n-1,y,x+y)

  return fib_iter(n,0,1)

説明:
ここでは、Scheme 言語で非常に一般的な末尾再帰記述方法を使用しました。 Scheme には反復はありませんが、不変条件と末尾再帰を使用して反復をシミュレートし、同じ効果を達成できます。ただし、Python が末尾再帰に対応する最適化を行ったかどうかはまだわかりません。また確認してみます。
追記: SICP を読んだ学生は、このプログラムが実際には SICP の第 1 章にある例であることが一目でわかります。

7) 賢い Python プログラマー:

fib=lambda n,x=0,y=1:x if not n else f(n-1,y,x+y)

説明:
基本的なロジックは上記の例と同じで、末尾再帰で記述されています。主な違いは、Python が提供するデフォルトのパラメーターと三項演算子を使用するため、コードが 1 行に簡略化されることです。デフォルト パラメーターについては、C++ を学習したことがある学生なら誰でも知っており、C# 4.0 にもこの機能が導入されています。

8) 線形代数を完了したばかりの Python プログラマー:

def fib(n):
 def m1(a,b):
  m=[[],[]]
  m[0].append(a[0][0]*b[0][0]+a[0][1]*b[1][0])
  m[0].append(a[0][0]*b[0][1]+a[0][1]*b[1][1])
  m[1].append(a[1][0]*b[0][0]+a[1][1]*b[1][0])
  m[1].append(a[1][0]*b[1][0]+a[1][1]*b[1][1])
  return m
 def m2(a,b):
  m=[]
  m.append(a[0][0]*b[0][0]+a[0][1]*b[1][0])
  m.append(a[1][0]*b[0][0]+a[1][1]*b[1][0])
  return m
 return m2(reduce(m1,[[[0,1],[1,1]] for i in range(n)]),[[0],[1]])[0]

説明:
このコードは前のコードほど明確ではないため、最初に原理を紹介します (線形代数の知識が少し必要です) ) :
まず、フィボナッチ関数の以前の反復バージョンを見てください。y->x、x+y->y という変換があることが簡単にわかります。別の角度から見ると、[x,y]→[y,x+y]となります。
ここでは、変換を通じて [y,x+y]T を取得するバイナリ ベクトル [x,y]T を宣言します。変換行列は [[1,0],[1] であることが簡単に得られます。 ,1] ]、つまり: [[1,0],[1,1]]*[x,y]T=[y,x+y]T
バイナリ行列 A=[[1, 0],[ 1,1]]、バイナリ ベクトル x=[0,1]T、Ax の結果が次のフィボナッチ値であることは簡単にわかります:
Ax=[fib(1),fib (2)]T
また:
Ax=[fib(2),fib(3)]T
………………
類推すると、次のようになります:

Aⁿx=[fib(n),fib(n-1)]T

つまり、バイナリ ベクトルをペアにすることで [0, 1]T は A 変換を n 回実行し、[fib(n), fib(n+1)]T を取得し、fib(n) を取得します。

ここでは、バイナリ行列乗算関数 m1 とバイナリ ベクトルの変換 m2 を定義し、次に、reduce 演算を使用して連続乗算演算を完了して Aⁿx を取得し、最後に fib(n) を取得します。

9) ACM コンテストへの参加を準備している Python プログラマー:

 def fib(n):
 lhm=[[0,1],[1,1]]
 rhm=[[0],[1]]
 em=[[1,0],[0,1]]
 #multiply two matrixes
 def matrix_mul(lhm,rhm):
  #initialize an empty matrix filled with zero
  result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))]
  #multiply loop
  for i in range(len(lhm)):
   for j in range(len(rhm[0])):
    for k in range(len(rhm)):
     result[i][j]+=lhm[i][k]*rhm[k][j]
  return result
 
 def matrix_square(mat):
  return matrix_mul(mat,mat)
 #quick transform
 def fib_iter(mat,n):
  if not n:
   return em
  elif(n%2):
   return matrix_mul(mat,fib_iter(mat,n-1))
  else:
   return matrix_square(fib_iter(mat,n/2))
 return matrix_mul(fib_iter(lhm,n),rhm)[0][0]

手順:

看过上一个fib函数就比较容易理解这一个版本了，这个版本同样采用了二元变换的方式求fib(n)。不过区别在于这个版本的复杂度是lgn，而上一个版本则是线性的。

这个版本的不同之处在于，它定义了一个矩阵的快速求幂操作fib_iter，原理很简单，可以类比自然数的快速求幂方法，所以这里就不多说了。

PS：虽然说是ACM版本，不过说实话我从来没参加过那玩意，毕竟自己算法太水了，那玩意又太高端……只能在这里YY一下鸟~

python中，最基本的那种递归（如下fib1)效率太低了，只要n数字大了运算时间就会很长；而通过将计算的指保存到一个dict中，后面计算时直接拿来使用，这种方式成为备忘(memo)，如下面的fib2函数所示，则会发现效率大大提高。

在n=10以内时，fib1和fab2运行时间都很短看不出差异，但当n=40时，就太明显了，fib1运行花了35秒，fab2运行只花费了0.00001秒。
n=40时，输出如下：

jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py 
2014-10-16 16:28:35.176396
fib1(40)=102334155
2014-10-16 16:29:10.479953
fib2(40)=102334155
2014-10-16 16:29:10.480035

这两个计算Fibonacci数列的函数，如下：https://github.com/smilejay/python/blob/master/py2014/fibonacci.py

import datetime

def fib1(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fib1(n - 1) + fib1(n - 2)
 
known = {0: 0, 1: 1}
 
def fib2(n):
  if n in known:
    return known[n]
 
  res = fib2(n - 1) + fib2(n - 2)
  known[n] = res
  return res

if __name__ == '__main__':
  n = 40
  print(datetime.datetime.now())
  print('fib1(%d)=%d' % (n, fib1(n)))
  print(datetime.datetime.now())
  print('fib2(%d)=%d' % (n, fib2(n)))
  print(datetime.datetime.now())

后记：

由于刚学习Python没多久，所以对其各种特性的掌握还不够熟练。与其说是我在用Python写程序，倒不如说我是在用C，C++，C#或是Scheme来写程序。至于传说中的Pythonic way，我现在还没有什么体会，毕竟还没用Python写过什么真正的程序。
Learning Python和Core Python都是不错的Python入门书籍，前者更适合没有编程基础的人阅读。
Python是最好的初学编程入门语言，没有之一。所以它可以取代Scheme成为MIT的计算机编程入门语言。

以上がPythonを使用してフィボナッチ関数を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。