斐波那契数列

斐波那契数列的增长速度非常快，像这个数：

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;  
}

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

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