iOS 算法(1)-斐波那契数列

定义

• 斐波那契数列是一系列数字，除了第一个和第二个数字之外，任何数字都是前两个数字之和：
  0、1、1、2、3、5、8、13、21......
• 数列中的第一个斐波那契数的值为0，第四个斐波那契数为2，第n个斐波那契数的值可以通过下述公式计算：
  fib(n) = fib(n-1) + fib(n-2)

迭代计算

/*
*  prev与curr分别代表f(n-1)和f(n)
*  计算prev+curr赋值给curr，curr赋值给prev，经过n次赋值后可以算出结果
*/
func fib(_ n: UInt) -> UInt {
  var (prev, curr) = (0, 1)
  for _ in 0..<n {
      (curr, prev) = (curr + prev, curr)
  }
  return curr
}

这个算法是解决斐波那契数列问题的最优算法，计算出fib(n)只需要n-1次循环即可.

尝试使用递归

在这个算法中，需要注意的是要注意fib方法的边界值，即做好终止点的计算

/*
 *  斐波那契数列的数字都是基于fib(0)和fib(1)计算出来的，所以在递归方法里面，只要计算出fib(0)和fib(1)，其他情况调用递归即可。
*/
func fib(_ n: UInt) -> UInt {
  if n < 2 {
    return n
  }
  return fib(n-1) + fib(n-2)
}

递归优化

在斐波那契数列的递归计算中，因为所有的斐波那契数都是通过对其前两个数计算出来的，所以递归算法中，fib(n)的调用次数是与n相关的指数增长，在fib(20)的时候，就调用了21891次。基于这个情况，可以对递归算法进行缓存，即每调用计算出一个数，就缓存到cache中，这样可以有效避免指数级的调用，这是典型的用空间换时间的做法。

/*
 *  在优化算法里，将fib(0)、fib(1)两个斐波那契数作为初始值放到cache里，可以减少两次调用，并且在递归算法中，不用再额外计算这两个数
  * 判断如果数组中没有fib(n)的结果，就用递归算法去计算fib(n)，放到数组里面，并返回数组的值
*/
var fibCache: [UInt: UInt] = [0: 0, 1: 1]
func fib(_ n: UInt) -> UInt {
  if fibCache[n] == nil {
      fibCache[n] = fibCache[n-1] + fibCache[n-2]
  }
  return fibCache[n]!
}

在这个算法中，计算出fib(n)需要2n-1次递归计算，相对于第一个迭代算法来说，还是稍微复杂一点。

其他注意点

计算斐波那契数列，其他需要注意的情况就是注意负值和溢出的情况，上述算法中，fib函数中的参数n的类型是UInt非负整数，这样避免了负值情况。而溢出情况本文不做赘述。