Python을 사용하여 피보나치 함수를 구현하는 방법

이 글은 주로 Python을 사용하여 피보나치 함수 관련 정보를 소개합니다. 필요한 친구들은

피보나치 피보나치 수열을 참조하세요. 아주 간단합니다. 아마 이렇게 할 수 있을 겁니다.

저는 최근 Python을 플레이하고 있습니다. Learning Python과 Core Python을 대충 살펴본 후, 우연히 인터넷에서 Python 프로그래머의 진화에 관한 게시물을 발견했습니다. 그래서 저는 계승 함수를 완성하기 위해 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에서는 프로그램 블록을 나누기 위해 중괄호 대신 들여쓰기를 사용하는 것이 매우 불편하고 각 명령문 뒤에 종결자가 없으므로 Python 함수를 작성한 후 가장 먼저 하는 일은 일반적으로 중괄호를 주석 처리하고 누락된 콜론을 추가하는 것입니다.

3) 게으른 Python 프로그래머:

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

설명:
Learning Python을 보기 전까지는 Python을 몰랐습니다. 삼항 연산자가 없나요? 그러나 Python의 bool 값은 매우 특별하고(C와 약간 유사하며 0이 아닌 것은 true를 의미하고, 비어 있지 않은 것은 true를 의미함) Python의 논리문도 단락 평가(Short-Circuit Evaluation)를 지원하므로 이는 가능합니다. 모방? 성명이 나옵니다.

4) 게으른 Python 프로그래머:

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

참고:
lambda 키워드는 C# 및 Scheme에서 사용한 적이 있지만 Python에서는 람다 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 Tail-recursion을 사용했습니다. 언어에서 매우 일반적인 쓰기 방법입니다. Scheme에는 반복이 없지만 불변성과 꼬리 재귀를 사용하여 반복을 시뮬레이션하여 동일한 효과를 얻을 수 있습니다. 그러나 Python이 꼬리 재귀에 대해 해당 최적화를 수행했는지는 여전히 알 수 없습니다.
PS: SICP를 읽은 학생들은 이 프로그램이 실제로 SICP 1장의 예제라는 것을 한눈에 알 수 있습니다.

7) 영리한 Python 프로그래머:

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

설명:
기본 논리와 위의 예 동일, 둘 다 꼬리 재귀 방식으로 작성되었습니다. 가장 큰 차이점은 Python에서 제공하는 기본 매개변수와 삼항 연산자를 사용하므로 코드를 한 줄로 단순화한다는 것입니다. 기본 매개변수에 대해서는 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]

설명:
이 코드는 다음과 같습니다. 이전 코드처럼 명확하므로 먼저 원리를 소개하겠습니다(선형 대수학에 대한 약간의 지식 필요).
먼저 이전 피보나치 함수의 반복 버전을 살펴보면 변환이 있음을 쉽게 알 수 있습니다. >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에 대해 n A 변환을 수행하여 [fib를 얻을 수 있습니다. (n),fib(n+1)]T, 따라서 fib(n)을 얻습니다.

여기에서는 이진 행렬 곱셈 함수 m1과 이진 벡터에 대한 변환 m2를 정의한 다음 축소 연산을 사용하여 연속 곱셈 연산을 완료하여 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!