1000-значный номер в Python - PullRequest
Новая
       8

1000-значный номер в Python

0 голосов
/ 28 ноября 2018

Я решал проект Эйлера, в котором я столкнулся с вопросом, который задавал мне индекс первого 1000-значного числа Фибоначчи.

Сначала я использовал этот код, но занимал слишком много времени. 

def fibonacci(num):
    if (num==0):
        return 0;
    if(num==1):
        return 1;
    return fibonacci(num-1) + fibonacci(num-2);


def numOfDigits(num):
    numOfDigits = 0;
    while (num>0):
        num = num/10;
        numOfDigits += 1;
    return numOfDigits;

def main():
    n=0;
    while(n>=0):
        fib = fibonacci(n);
        num = numOfDigits(fibonacci(n));
        print n,"\t",fib;
        if(num>=1000):
            break;
        n+=1;
    print "answer:",n;
main();

Затем я немного погуглил и нашел формулу binnet , которая сделала его очень быстрым. 

import math as mt;

def fibonacci(num):
    phi = (mt.sqrt(5)+1.00)/2.00;
    return ((phi**num)-((-phi)**(-num)))/mt.sqrt(5);

def numOfDigits(num):
    numOfDigits = 0;
    while (num>0):
        num = num/10;
        numOfDigits += 1;
    return numOfDigits;

def main():
    n=0;
    while(n>=0):
        fib = fibonacci(n);
        num = numOfDigits(fibonacci(n));
        print n,"\t",fib;
        if(num>=1000):
            break;
        n+=1;
    print "answer:",n;
main();

Но тут возникла проблема: 

1471    1.17851144788e+307
1472    1.9068715788e+307
1473    3.08538302668e+307
1474    4.99225460548e+307
Traceback (most recent call last):
  File "src/ThousandDigitFibonacciNum.py", line 29, in <module>
    main();
  File "src/ThousandDigitFibonacciNum.py", line 22, in main
    fib = fibonacci(n);
  File "src/ThousandDigitFibonacciNum.py", line 10, in fibonacci
    return ((phi**num)-((-phi)**(-num)))/mt.sqrt(5);
OverflowError: (34, 'Result too large')

Первое сомнение в том, что результат слишком велик, чтобы его можно было вернуть или рассчитать?И каково же решение этой проблемы?

1 Ответ

0 голосов
/ 28 ноября 2018

Для каждого n вы пересчитываете все числа Фибоначчи F(1)...F(n-1), чтобы вычислить F(n).Вместо этого вы можете вычислять каждое число Фибоначчи только один раз, проверяя для каждого, имеет ли оно соответствующее количество цифр: 

def fibo():
    a = 0
    b = 1
    while True:
        yield a
        a, b = b, a+b

for index, number in enumerate(fibo()):
    if len(str(number)) == 1000:
        print(index)
        break
...