有 100 阶楼梯,一个人从底往上爬,每次爬 1 阶或 2 阶,请编个算法说明一共多少种走法?后面的问题更有一些深度:这个算法(他会给出一个正确的算法思路)有什么效率上的问题,如何解决;如果这个算法经常要被调用,如何设法使效率提高?
F(n) = F(n-1) + F(n-2), n = 阶数
F(0) = F(1) = 1,这个是 Fibonacci 数列,最直观的是递归,复杂度是指数;然后是线性的算法;接下来有一个对数的算法。如果是经常被调用,可以修改线性的算法,设一个 cache F[0...n],在算之前,先查一下这个 cache,如果没有,就重新算一下。
参考:Fibonacci 数列的三种算法 (http://enihcam.iblog.com/post/5251/124345)
Tuesday, February 24, 2009
google fabiccon
Subscribe to:
Post Comments (Atom)

No comments:
Post a Comment