从斐波那契据数列简单谈程序的几个层次

从斐波那契数列简单谈程序的几个层次

写一个生成斐波那契数列的程序，初学计算机迟早会写那么一次，至少看过别人的代码一次。

一、小鸟层次

int fibonacci_a(int n) { if( n== 0 || n==1 ) return n; else return fibonacci_a(n-1) + fibonacci_a(n-2); }        其实我相信100个程序员里面有80个能写出这样一个程序。事实这确实不是个什么复杂的函数，看了数学公式，然后心安理得地写出这样一个程序，或者从课本上看到这样一个程序，然后敲上一遍，许多人会认为至少斐波那契数列的生成算是掌握了。但如果他调用一下fibonacci_a(1000),我觉得他多半是没法在吃晚饭前等到结果了。所以这是一个菜鸟程序，或许程序员并不是菜鸟，但至少在这个程序上是菜鸟。

二、高手层次

int fibonacci_b(int n) { int *arr = new int[n]; arr[0] = 0,arr[1] = 1; for(int i=2; i<=n; ++i) arr[i] = arr[i-1] + arr[i-2]; return arr[n]; }        如果知道这样也可以完成斐波那契数列的生成，至少应该是个高手了。这是一个典型的空间换取时间的例子。如果知道自己用的是动态规划技术，那么无疑更好了。你可以安心地调用fibonacci(10000)，很慢的机子应该也能瞬间得到结果。但似乎还是有点美中不足，new有点耗时间，空间耗费也很大。

三、完美主义者

int fibonacci_c(int n) { int arr[3] = {0,1,1}; for( ; n>2; n-=3 ) arr[0] = arr[1] + arr[2], arr[1] = arr[0] + arr[2], arr[2] = arr[0] + arr[1]; return arr[n]; }         仔细观察后，你会发现其实许多前面的运算结果是可以不保留的，那么三个临时空间就足够。速度比上一个版本还要快，空间到了完全可以接受的程度。极限主义者发现其实还可以进一步缩减到只用两个临时空间，但速度会变慢（为什么？判断次数多了），数学理论上有直接的公式，是否更快呢？因为涉及到乘法，其实并不能加快运算，就算使用快速乘法技术（n次方只需要log n 次乘法），依然会遇到精度问题，而且代码变得并不通俗易懂。那么一个完美主义者也可以接受这个版本了，时间复杂度优秀，空间复杂度优秀，代码没有精度问题可能导致的错误，代码简洁。C++中有模板元编程可以直接生成需要的斐波那契数，而且几乎不费程序时间（编译时间在n大的时候和第一个版本一样恐怖），但却要求n只能是常数。好了，你拥有一个完美主义者应该有的斐波那契数生成版本了。

        什么是好的代码？好的性能（时间复杂度），好的内存占用（尽量少），没有错误（尽量），代码简洁（至少保证自己半年还能读懂），知道尺度（不过于追求某些工程上极限技术，而更乐于本质的创新）。然后写好下一段代码！你写得最好的代码是什么？下一段！