用Python实现斐波那契（Fibonacci）函数
Fibonacci斐波那契数列，很简单，就是一个递归嘛，学任何编程语言可能都会做一下这个。
最近在玩Python，在粗略的看了一下Learning Python和Core Python之后，偶然发现网上有个帖子Python程序员的进化写的很有意思。于是打算仿照一篇，那篇帖子用了十余种方法完成一个阶乘函数，我在这里会用九种不同的风格写出一个Fibonacci函数。
要求很简单，输入n，输出第n个Fibonacci数，n为正整数
下面是这九种不同的风格：
1）第一次写程序的Python程序员：
def fib(n): return nth fibonacci number
说明：
第一次写程序的人往往遵循人类语言的语法而不是编程语言的语法，就拿我一个编程很猛的哥们来说，他写的第一个判断闰年的程序，里面直接是这么写的：如果year是闰年，输出year是闰年，否则year不是闰年。
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，非零即真，非空即真），再加上Python的逻辑语句也是支持短路求值（Short-Circuit Evaluation）的，这就可以写出一个仿？语句出来。
4）更懒的Python程序员：
fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2)
说明：
lambda关键字我曾在C#和Scheme里面用过，Python里面的lambda比C#里简便，并很像Scheme里的用法，所以很快就适应了。在用Python Shell声明一些小函数时经常用这种写法。
5）刚学完数据结构的Python程序员：
def fib(n): x,y=0,1 while(n): x,y,n=y,x+y,n-1 return x
说明：
前面的Fibonacci函数都是树形递归的实现，哪怕是学一点算法就应该知道这种递归的低效了。在这里从树形递归改为对应的迭代可以把效率提升不少。
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第一章里的一个例子。
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]
说明：
这段代码就不像之前的代码那样清晰了，所以先介绍下原理（需要一点线性代数知识）：
首先看一下之前的迭代版本的Fibonacci函数，很容易可以发现存在一个变换：y->x, x+y->y。换一个角度，就是[x,y]->[y,x+y]。
在这里，我声明一个二元向量[x,y]T，它通过一个变换得到[y,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的结果就是下一个Fibonacci数值，即：
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，然后利用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的计算机编程入门语言。
Outils d'IA chauds
Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes
AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.
Undress AI Tool
Images de déshabillage gratuites
Clothoff.io
Dissolvant de vêtements AI
AI Hentai Generator
Générez AI Hentai gratuitement.
Article chaud
Outils chauds
Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit
SublimeText3 version chinoise
Version chinoise, très simple à utiliser
Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP
Dreamweaver CS6
Outils de développement Web visuel
SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)
PHP et Python: exemples de code et comparaison
Apr 15, 2025 am 12:07 AM
PHP et Python ont leurs propres avantages et inconvénients, et le choix dépend des besoins du projet et des préférences personnelles. 1.Php convient au développement rapide et à la maintenance des applications Web à grande échelle. 2. Python domine le domaine de la science des données et de l'apprentissage automatique.
Comment est la prise en charge du GPU pour Pytorch sur Centos
Apr 14, 2025 pm 06:48 PM
Activer l'accélération du GPU Pytorch sur le système CentOS nécessite l'installation de versions CUDA, CUDNN et GPU de Pytorch. Les étapes suivantes vous guideront tout au long du processus: CUDA et CUDNN Installation détermineront la compatibilité de la version CUDA: utilisez la commande NVIDIA-SMI pour afficher la version CUDA prise en charge par votre carte graphique NVIDIA. Par exemple, votre carte graphique MX450 peut prendre en charge CUDA11.1 ou plus. Téléchargez et installez Cudatoolkit: visitez le site officiel de Nvidiacudatoolkit et téléchargez et installez la version correspondante selon la version CUDA la plus élevée prise en charge par votre carte graphique. Installez la bibliothèque CUDNN:
Explication détaillée du principe docker
Apr 14, 2025 pm 11:57 PM
Docker utilise les fonctionnalités du noyau Linux pour fournir un environnement de fonctionnement d'application efficace et isolé. Son principe de travail est le suivant: 1. Le miroir est utilisé comme modèle en lecture seule, qui contient tout ce dont vous avez besoin pour exécuter l'application; 2. Le Système de fichiers Union (UnionFS) empile plusieurs systèmes de fichiers, ne stockant que les différences, l'économie d'espace et l'accélération; 3. Le démon gère les miroirs et les conteneurs, et le client les utilise pour l'interaction; 4. Les espaces de noms et les CGROUP implémentent l'isolement des conteneurs et les limitations de ressources; 5. Modes de réseau multiples prennent en charge l'interconnexion du conteneur. Ce n'est qu'en comprenant ces concepts principaux que vous pouvez mieux utiliser Docker.
Python vs JavaScript: communauté, bibliothèques et ressources
Apr 15, 2025 am 12:16 AM
Python et JavaScript ont leurs propres avantages et inconvénients en termes de communauté, de bibliothèques et de ressources. 1) La communauté Python est amicale et adaptée aux débutants, mais les ressources de développement frontal ne sont pas aussi riches que JavaScript. 2) Python est puissant dans les bibliothèques de science des données et d'apprentissage automatique, tandis que JavaScript est meilleur dans les bibliothèques et les cadres de développement frontaux. 3) Les deux ont des ressources d'apprentissage riches, mais Python convient pour commencer par des documents officiels, tandis que JavaScript est meilleur avec MDNWEBDOCS. Le choix doit être basé sur les besoins du projet et les intérêts personnels.
Miniopen Centos Compatibilité
Apr 14, 2025 pm 05:45 PM
Minio Object Storage: Déploiement haute performance dans le système Centos System Minio est un système de stockage d'objets distribué haute performance développé sur la base du langage Go, compatible avec Amazons3. Il prend en charge une variété de langages clients, notamment Java, Python, JavaScript et GO. Cet article introduira brièvement l'installation et la compatibilité de Minio sur les systèmes CentOS. Compatibilité de la version CentOS Minio a été vérifiée sur plusieurs versions CentOS, y compris, mais sans s'y limiter: CentOS7.9: fournit un guide d'installation complet couvrant la configuration du cluster, la préparation de l'environnement, les paramètres de fichiers de configuration, le partitionnement du disque et la mini
Comment faire fonctionner la formation distribuée de Pytorch sur CentOS
Apr 14, 2025 pm 06:36 PM
La formation distribuée par Pytorch sur le système CentOS nécessite les étapes suivantes: Installation de Pytorch: La prémisse est que Python et PIP sont installés dans le système CentOS. Selon votre version CUDA, obtenez la commande d'installation appropriée sur le site officiel de Pytorch. Pour la formation du processeur uniquement, vous pouvez utiliser la commande suivante: pipinstalltorchtorchVisionTorChaudio Si vous avez besoin d'une prise en charge du GPU, assurez-vous que la version correspondante de CUDA et CUDNN est installée et utilise la version Pytorch correspondante pour l'installation. Configuration de l'environnement distribué: la formation distribuée nécessite généralement plusieurs machines ou des GPU multiples uniques. Lieu
Comment choisir la version Pytorch sur Centos
Apr 14, 2025 pm 06:51 PM
Lors de l'installation de Pytorch sur le système CentOS, vous devez sélectionner soigneusement la version appropriée et considérer les facteurs clés suivants: 1. Compatibilité de l'environnement du système: Système d'exploitation: Il est recommandé d'utiliser CentOS7 ou plus. CUDA et CUDNN: La version Pytorch et la version CUDA sont étroitement liées. Par exemple, Pytorch1.9.0 nécessite CUDA11.1, tandis que Pytorch2.0.1 nécessite CUDA11.3. La version CUDNN doit également correspondre à la version CUDA. Avant de sélectionner la version Pytorch, assurez-vous de confirmer que des versions compatibles CUDA et CUDNN ont été installées. Version Python: branche officielle de Pytorch
Comment installer nginx dans Centos
Apr 14, 2025 pm 08:06 PM
CENTOS L'installation de Nginx nécessite de suivre les étapes suivantes: Installation de dépendances telles que les outils de développement, le devet PCRE et l'OpenSSL. Téléchargez le package de code source Nginx, dézippez-le et compilez-le et installez-le, et spécifiez le chemin d'installation AS / USR / LOCAL / NGINX. Créez des utilisateurs et des groupes d'utilisateurs de Nginx et définissez les autorisations. Modifiez le fichier de configuration nginx.conf et configurez le port d'écoute et le nom de domaine / adresse IP. Démarrez le service Nginx. Les erreurs communes doivent être prêtées à prêter attention, telles que les problèmes de dépendance, les conflits de port et les erreurs de fichiers de configuration. L'optimisation des performances doit être ajustée en fonction de la situation spécifique, comme l'activation du cache et l'ajustement du nombre de processus de travail.
