# A coding kata -- Fibonacci sequence

0112358132134……

## 伊始

• 递归的方法可以求出所有的解吗，当n=80800甚至8000或者更大值的时候可以求解吗
• 效率怎么样
• 你有什么方法提高效率吗
• 你是否利用了某些编程语言的特性
• 你能想出几种不同的解法
• 等等

## 递归实现

def fib(n):
if n == 0: return 0
elif n == 1: return 1
else: return fib(n-1) + fib(n-2)

$$T(n) = T(n - 1) + T(n - 2) + 1 ≈ 2^n = O(2^n)$$

## 递归优化

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)

## 动态规划

• 自底向上
def fib(n):
memo = [0, 1]
for i in range(2, n+1):
memo.append(memo[i - 1] + memo[i - 2])
return memo[n]
• 自顶向下
memo = {0: 0, 1: 1}
def fib(n):
if n in memo:
return memo[n]

if n == 0: return 0
elif n == 1: return 1
memo[n]  = fib(n - 1) + fib(n - 2)
return memo[n]

• 改进方案，高效缓存

def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a

namespace {
struct fib_cache {
fib_cache() : previous_{0}, last_{1}, size_{2} {}

size_t size() const { return size_; }

unsigned int operator[](unsigned int n) const {
return n == size_ - 1 ? last_ :
n == size_ - 2 ? previous_ :
throw std::out_of_range("The value is no longer in the cache");
}

void push_back(unsigned int value) {
size_++;
previous_ = last_;
last_ = value;
}

private:
unsigned int previous_;
unsigned int last_;
size_t size_;
};

} // namespace

unsigned int fib(unsigned int n) {
fib_cache cache;
if (cache.size() > n) {
return cache[n];
} else {
const auto result = fib(n - 1) + fib(n - 2);
cache.push_back(result);
return result;
}
}

## 矩阵算法

$$\left[ \begin{matrix} F_n\\ F_{n-1}\\ \end{matrix} \right] = \left[ \begin{matrix} F_{n-1} + F_{n-2}\\ F_{n-1}\\ \end{matrix} \right] =\left[ \begin{matrix} 1 & 1 \\ 1 & 0\\ \end{matrix} \right] * \left[ \begin{matrix} F_{n-1} \\ F_{n-2}\\ \end{matrix} \right]$$

$$\left[ \begin{matrix} F_n\\ F_{n-1}\\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ 1 & 0\\ \end{matrix} \right]^{n-1} * \left[ \begin{matrix} F_{1} \\ F_{0}\\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right]^{n-1} * \left[ \begin{matrix} 1\\ 0\\ \end{matrix} \right]$$

$$x^n= \begin{cases} x^{n/2} * x^{n/2}, &even\\ x^{(n-1)/2} * x^{(n-1)/2} * x, &odd \end{cases}$$

$$T(n) = T(n/2) + 1 = O(log n)$$