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

Question

Итак, я написал рекурсивную программу, которая теперь запрашивает у пользователя много чисел Фибоначчи, которые они хотели бы выполнить.Проблема, с которой я столкнулся, состоит в том, что после 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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

Поскольку вы используете предыдущие числа, сдвинутые на единицу для каждой следующей итерации цикла, для рекурсивного вызова имеет смысл использовать фибоначчи (a, a + b, n + 1, количество) вместо фибоначчи (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;
}

Answer 4

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