Нахождение 1500000-го числа Фибоначчи с использованием C ++ - PullRequest
Новая
       22

Нахождение 1500000-го числа Фибоначчи с использованием C ++

3 голосов
/ 09 мая 2011

Я написал следующий код, чтобы найти 1500000-е число Фибоначчи (Пожалуйста, не обращайте внимания на ужасные отступы, я написал это примерно через 2 минуты). Мне нужно это как строка. Это должно, гипотетически работать: 

#include <cstdlib>
#include <iostream>
#include <sstream>
int i;
int b=1;
int c=2;
using namespace std;

int main(int argc, char *argv[])
{

    int fib=1500000;

for (i=1;i<fib-3;i++){
c=b+c;
b=c-b;
}
   stringstream ss;
   ss << c;
   string d=ss.str();
cout << d << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

Он проходит процесс 1500000-3 раза (каждый раз повторяется на 3 числа) Я понимаю, что проблема в том, что число слишком большое, чтобы его можно было содержать как int. Есть ли способ для меня, чтобы сохранить его, не содержащий его как int или файл (так как это было бы крайне неэффективно)? Если так, как бы я это сделал?

Ответы [ 2 ]

2 голосов
/ 09 мая 2011

Использование библиотеки Bignum .

1 голос
/ 09 мая 2011

Если вам нужна точная форма, вы можете использовать одно из других рекуррентных отношений с библиотекой bignum: 

fib(2*n) = fib(n)^2 + fib(n-1)^2
fib(2*n-1) = fib(n)*(2*fib(n-1)+fib(n))

Что должно уменьшить количество вычислений, необходимых для O (log (n)), а не O (n) Вы можете увидеть псевдокод для метода, основанного на этом здесь: n-е число Фибоначчи в сублинейном времени

Обратите внимание, что для n-го числа Фибоначчи требуется около n * log (phi) / log (2) = n * 0,69 двоичных цифр для представления, поэтому точное представление 1,5M ^ -ой потребуется около 130 КБ для представления в двоичной или 300 КБ в виде строки (приблизительно 2 ^ (10000000) или 10 ^ (300000))

Удалено как двойное переполнение при n = 1500

Вы можете сделать это напрямую, используя удвоения следующим образом (адаптировано из http://en.wikipedia.org/wiki/Fibonacci_number): 

double fib( int n )
{
   static const SQRT_5 = sqrt(5.0);
   static const phi = (1.0+SQRT_5)/2.0;
   return floor( (pow(phi,n)/SQRT_5) + 0.5 );
}

Хотя, если вам нужна каждая цифра, это не сработает. (Это даст только каждую цифру до 78 числа Фибоначчи)

...