查看原文
其他

[C++]斐波那契数列

2016-12-19 Y叔 biobabble



斐波那契数列的增长速度非常快,上次讲到了用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/。


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存