其他
斐波那契数列
斐波那契数列的增长速度非常快，像这个数：
4109266378488062431228061757602275200488546350691404731331209059476699865525985814512330794573159713192993537023560937664480427471312780415869653296
有148位数，你知道它是第几个斐波那契数吗？今天就要解答这个问题，上面这个数是第708个斐波那契数。
斐波那契数列经常被用来做为写递归的例子，但递归算起来实在是慢，因为有太多重复计算在里面。
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：斐波那契数列有个神奇的特性，就是当数列无穷时，后一项的数字除以前一项的数字，逼近黄金分割。
往期精彩