Рекурсивные фибоначчи

Question

Я пытаюсь сгенерировать ряд Фибоначчи и предоставил код для того же самого ниже. Когда я запускаю этот код для меньших значений, он выводит правильные результаты. Однако, когда я пытаюсь вычислить ряд для числа, скажем, «50», он выводит правильные результаты до 47-го числа, а результат для 48,49 и 50-го члена неверен. Я попытался использовать unsigned long int, но это не исправило результаты. Могут ли некоторые подсказать, пожалуйста, что я здесь делаю не так? Благодарю.

#include<stdio.h>
unsigned long long int fibr(unsigned long long int);

int main(){
    unsigned long long  int n;
    printf("Enter a number\n");
    scanf("%llu",&n);
    //res=fibr(n);
      while(n>=0){
          printf("%llu\n",fibr(n));
          n--;
           }
     }
unsigned long long int fibr(unsigned long long int n){
     if((n==0)||(n==1))
         return n;
     else return fibr(n-1)+fibr(n-2);
     }

'После предложений я включил unsigned long long int. Изменили код выше, но теперь он дает ошибку сегмента. Любые намеки, пожалуйста. Мне не разрешается использовать любую другую библиотеку, кроме стандартной. «

Answer 1

Вы пытались использовать unsigned long long?

Answer 2

Вот ответ на ваш второй вопрос:

Я думаю, что у вас возникла эта проблема с самого начала:

while(n>=0){

- бесконечный цикл, поскольку n - целое число без знака.n станет отрицательным из-за уменьшения.Но так как он не подписан, он обернется и вызовет переполнение стека в вашей рекурсии.

Кроме того, ваш алгоритм, вероятно, самый медленный способ сделать это.Это работает в экспоненциальном времени.Так что, когда значение n большое, его запуск займет очень много времени.

Лучший способ заключается в следующем:

int n = 48;
return (unsigned long long)(pow(1.6180339887498948,n) * 0.44721359549995794 + 0.5);

Этот метод будет работать в постоянное время.:)

Answer 3

Преобразование fibr() для запоминания его результатов сокращает время работы fibr (90) до нескольких миллисекунд на моей машине.Переключение с рекурсии на итерацию должно иметь аналогичные результаты.

Answer 4

Вы получаете целочисленное переполнение.Для unsigned int самое большое возможное значение - 4294967295, но 48-е число Фибоначчи - 4807526976.

Answer 5

C типы данных ограничены по размеру.Поэтому, если вы используете int, long или long long, в какой-то момент ваш результат будет переполнен из-за быстро растущей природы числа Фибоначчи.Для хранения таких больших чисел вам понадобится реализация BigInteger.Посмотрите на «BigInt» в C? для этого.