Рекурсивная последовательность Фибоначчи

Итак, я написал рекурсивную программу, которая теперь запрашивает у пользователя много чисел Фибоначчи, которые они хотели бы выполнить. Проблема, с которой я столкнулся, заключается в том, что после 45-го числа он дает мне число со знаком «-», и это число не вписывается в последовательность. Как я могу изменить это, чтобы дать мне правильный номер? Вот рекурсивная часть кода, выполняющего вычисления:

void fibonacci (int a, int b, int n, int count)
{
    if(n < count) 
    {
        cout<<a+b<<endl;
        fibonacci(b, a+b, n+1, count);
    }
}

вот результат последовательности:

How many numbers do you want the Fibonacci sequence to process: 50
The starting numbers for the sequence are: 0, 1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863
-1109825406

Какие изменения мне нужно сделать, чтобы он заменил - # на действительные числа?


c++ recursion fibonacci
person A55666    schedule 31.03.2011    source источник

Ответы (4)


arrow_upward
9
arrow_downward

Вы столкнулись с проблемами, потому что тип данных int, который вы используете, составляет 32 бита и может содержать только значения до 2 ^ 31-1 = 2147483647, когда signed (по умолчанию, используется 31 бит, 1 бит занят, чтобы указать подписи, это также объясняет отрицательные числа), 2 ^ 32-1 = 4294967295, когда unsigned. Здесь вы можете использовать 64-битный тип данных (в большинстве случаев long long), но позже вы также столкнетесь с проблемами с этим (я думаю, около 94-го числа Фибоначчи).

«Настоящее» решение этой проблемы - написать свои собственные методы численных расчетов и использовать собственное представление чисел, например. массив символов. Вы также можете поискать одну из различных возможностей использования библиотеки «bignum». Вы должны найти дополнительную информацию об этом в некоторых вопросах SO, например, этот.

person schnaader    schedule 31.03.2011
comment
Кроме того, предпочтительно использовать unsigned типы для вещей, которые не могут быть негативными. - person Xeo; 31.03.2011
comment
Кстати, подумайте о том, чтобы добавить точную причину отрицательного представления к вашему ответу, чтобы сделать его более полным. - person Xeo; 31.03.2011
comment
@Xeo По мнению большинства экспертов, нет. Под беззнаковым обычно понимается необходимость манипуляций с битами или арифметики модулей. - person James Kanze; 31.03.2011
comment
Вы также можете использовать числа с плавающей запятой двойной точности (это тип double). Этот тип может поддерживать огромное количество (я думаю, 250 0 или больше). Плюс для больших целых чисел используйте 2.0E10, а не 2E10. 2.0E10 сделает это ровно 2 с 10 нулями. - person rauprog; 11.08.2018

arrow_upward
1
arrow_downward

объявление вашей переменной как unsigned int позволит вам выполнять немного больше взаимодействий, но вы все равно столкнетесь с проблемами. Увеличение размера вашей переменной с помощью long long int все равно задержит решение вашей проблемы. Вы не можете решить эту проблему, потому что рано или поздно вы превысите максимальное число, которое вы можете представить, какой бы тип данных вы ни выбрали.

person BlackBear    schedule 31.03.2011
comment
Или у вас закончится память. Некоторые реализации BigInt допускают бесконечную точность, но, в конце концов, бесконечность никогда не превышает объем доступной памяти. - person James Kanze; 31.03.2011

arrow_upward
0
arrow_downward

Ints хранит только 32 бита данных, максимальное значение - 2147483647. Ваши возвращаемые значения "переполнены". Используйте тип данных ulong, который содержит 64 бита и имеет максимальное значение 18 446 744 073 709 551 615.

person Joe Abrams    schedule 31.03.2011

arrow_upward
0
arrow_downward

Используйте тип double, потому что тип int будет быстро переполняться при вычислении умеренно больших чисел Фибоначчи. Для больших чисел следует использовать экспоненциальную запись с двойной плавающей запятой.

Поскольку вы используете предыдущие числа, сдвинутые на единицу вверх для каждой следующей итерации цикла, для рекурсивного вызова имеет смысл использовать fibonacci (a, a + b, n + 1, count) вместо fibonacci (b, a + b, n +1, кол). Я написал свою собственную рекурсивную функцию, которая менее рекурсивна, что проиллюстрирует, почему использовать другой рекурсивный вызов, чтобы сделать логику более понятной.

Написанная мною рекурсивная функция показывает, как быстро числа без плавающей точки переполняются числами Фибоначчи.

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <conio.h>
using std::cout;
using std::endl;

int fibonacci(double n, int count) {
    char ch;
    static double lastnminus1, lastnminus2;
    if (n == 1) {
     lastnminus1 = 1;
     lastnminus2 = 0;
    }
    cout << lastnminus1 + lastnminus2 << endl;
    double temp = lastnminus1;
    lastnminus1 = lastnminus1 + lastnminus2;
    lastnminus2 = temp;
    if (static_cast<int>(n) % 24 == 0) { 
        cout << "press a key" << endl;
        ch = getch();
    }
    if ( n < count)
        fibonacci(n+1,count);

    return 0;
}

int main()
{
    fibonacci(1,200);
    return 0;
}
person rauprog    schedule 11.08.2018