/ C#

又见斐波那契

fibonacci之前公司在找人面试的时候,我几乎必问的题目就是斐波那契数列,题目很简单,就是求斐波那契数列第n位的数值。很多教科书都会使用这个题目来做例子。每次我都是给面试者一只笔和一张纸,让他写出来,基本上不会给任何限制,随便使用任意语言,任意解法。之所以让我这么爱用这个题目的原因是,这个题目虽然简单,但是有一些小坑需要处理,可以和面试者讨论这些坑的处理方式,执行过程中发生了什么,探索一些不一样的解法等等,可以比较好的了解候选人的思维。然而,让我诧异的是,没有几个人能思路清晰的写出解法来,并说出思路以及里面的坑,好容易有写出来的却没法说清思路以及改进方式,甚至有许多工作多年的“资深”工程师都写不出来。

一般最常见的写法就是简单的递归实现:

public int Fibonacci(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
}

可是这里有个坑,递归会堆栈溢出,性能极差,时间复杂度为O(2n),大一点的数就求不出来了。

其实解法非常的多,用数组缓存结果,迭代递推,矩阵乘法,甚至还有通项公式,等等。许多算法教材里也都会提到,我就不必在这里展开了。

今天写这篇博客的原因是我看到的一个Ruby的写法十分的精炼且不晦涩,从没想过这样去写斐波那契。其实很简单,数组缓存结果,利用了一些Ruby的特性,用Javascript也可以写出类似的效果:

class Fib
	@@memo = { 0 => 0, 1 => 1 }

	def self.fib_rec(n)
		@@memo[n] ||= fib_rec(n - 1) + fib_rec(n - 2)
	end
end

函数的主体就一行代码,还是递归,用hash来缓存结果,利用或运算。不知道还有哪些语言有巧妙的写法?一起来分享一下。

Jackson Zhang

Jackson Zhang

Odd-e敏捷教练,主要涉及组织,团队,产品,技术,工程实践等,曾为多家知名企业提供教练与培训服务。译有《用户故事与敏捷方法》,《.NET单元测试的艺术》和《实例化需求说明》。擅长工程实践(如测试驱动开发,单元测试,重构,持续集成等),产品探索(Impact Mapping,Pretotyping,Lean Startup等)与团队协作。zbcjackson AT gmail.com

Read More