[C++]斐波那契数列

斐波那契数列的增长速度非常快，上次讲到了用GMP库来处理大数，于是再来一实例。像这个数：

4109266378488062431228061757602275200488546350691404731331209059476699865525985814512330794573159713192993537023560937664480427471312780415869653296

有148位数，你知道它是第几个斐波那契数吗？今天就要解答这个问题，上面这个数是第708个斐波那契数。

斐波那契数列经常被用来做为写递归的例子，但递归算起来实在是慢，因为有太多重复计算在里面。

#include <iostream>
#include <fstream>
#include <sstream>
#include <cassert>
#include <gmpxx.h>

struct fibo_t {
  static const int size = 1000;
  int fibo_size;
  mpz_class fibo[size];
};

fibo_t fibonacci(int N) {
  fibo_t fibo;
  assert(N <= fibo.size);

  fibo.fibo_size = N;

  fibo.fibo[0] = 0;
  fibo.fibo[1] = 1;
    
  for (int i=2; i<N; i++) {
    fibo.fibo[i] = fibo.fibo[i-1] + fibo.fibo[i-2];
  }
  return fibo;
}

这里我们使用for loop就好。同样的，我们需要使用GMP来存储大整数。

这里依然是使用结构体，方便存储相关的信息，这里记录了缓存向量最大有多大，实际存储有多大，以及缓存的斐波那契数列。

题目要求是给我们好多行数字，第一行是后面数字的个数，然后我们读了数字要报出来是第几个斐波那契数。

int main() {
  int N = 1000;
  fibo_t fibo = fibonacci(N);

  std::ifstream infile("data/id67.txt");
  std::string line;
  getline(infile, line);

  int n;
  std::stringstream ss(line);
  ss >> n;

  int idx[n];
  mpz_class fnum;
  for (int i=0; i<n; i++) {
    getline(infile, line);
    std::stringstream ss(line);
    ss >> fnum;
    for (int j = 0; j<fibo.fibo_size; j++) {
      if (fnum == fibo.fibo[j])
    idx[i] = j;
    }
  }
 
  for (int i=0; i<n; i++) {
    std::cout << idx[i] << " ";
  }
  std::cout << std::endl;
  return 0;
}

先缓存一下结果，就比较简单了，无非是比较数字，记录下位置，再打印出来。

PS1：斐波那契数列有个神奇的特性，就是当数列无穷时，后一项的数字除以前一项的数字，逼近黄金分割。

PS2：Rosalind上有个兔子繁殖问题，也是fibonacci数列，http://rosalind.info/problems/fib/。