Переполнение чисел Фибоначчи в С++

Я c++ новичок и одновременно начинаю изучать его, изучая алгоритм. Однако при написании этого алгоритма я столкнулся с некоторой проблемой -- число переполняется, что сильно отличается от переполнения, о котором я думал. Решить проблему я долго искал, но в итоге безрезультатно. Вот мой код:

#include <iostream>
using namespace std;

long long Fs[101];
long long F(int N) {
    if (Fs[N] != -1) {
        return Fs[N];
    }
    int res = F(N - 1) + F(N - 2);
    Fs[N] = res;
    return res;
}

void main() {
    // initialize Fs array
    for (auto& item : Fs) {
        item = -1;
    }
    Fs[0] = 0;
    Fs[1] = 1;
    cout << F(60) << endl;
    cout << endl;
    for (auto& item : Fs) {
        cout << item << endl;
    }
}

Часть результата показана здесь:

165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543

Вопрос:
Вы можете видеть, что число переполнения довольно мало, чем минимальное значение типа long long. Почему это произошло?


Приложение
Я нашел способ вывести индекс переполнения беззнакового типа при генерации fibonacci, вот код:

#include <iostream>
#include <limits>
using namespace std;
 
#define outFibonacci(nType) { int i = 1;\
    while (i++)\
        if (Fibonacci<nType>(i+1)==Fibonacci<nType>(i+2)){\
            cout<<"F("<<i<<")\t= "<<Fibonacci<nType>(i)<<endl;\
            break;\
        }\
    cout<< "Max Num\t= " << numeric_limits<nType>::max() << endl << endl;\
    }
 
template<typename _T> _T Fibonacci(_T n){
    _T f, f1, f2;
    f = f1 = f2 = 1;
    for (auto i=3; i<=n; ++i){
        f = f1 + f2;
        if (f<f2){ // Set overflow condition
            f=-1;
            break;
        }
        f1 = f2;
        f2 = f;
    }
    return f;
}
 
int main(void)
{   
    outFibonacci(unsigned short);
    
    outFibonacci(unsigned int);
    outFibonacci(unsigned long);
    
    outFibonacci(unsigned long long);
    outFibonacci(size_t);
    
    return 0;
}

и вот мой результат:

F(24)   = 46368
Max Num = 65535

F(47)   = 2971215073
Max Num = 4294967295

F(47)   = 2971215073
Max Num = 4294967295

F(93)   = 12200160415121876738
Max Num = 18446744073709551615

F(93)   = 12200160415121876738
Max Num = 18446744073709551615

Посмотрите на тип здесь: int res =... Если бы вы только не ввели эту переменную... (return Fs[N] = F(N - 1) + F(N - 2);)

molbdnilo 17.05.2022 10:28

Почему это произошло? Потому что res относится к типу int. Измените его на long long.

Daniel Langr 17.05.2022 10:29

Предложение: узнайте больше о отладка. Это быстро покажет, в чем проблема.

Daniel Langr 17.05.2022 10:40

В качестве примечания: f = f1 + f2; if (f<f2) действителен только для неподписанных, неопределенное поведение для подписанных. Конечно, вы применяете только делал к неподписанным, но имейте в виду ;)

Aconcagua 17.05.2022 10:53

О using namespace std...

Aconcagua 17.05.2022 10:54

Вы должны использовать uintmax_t вместо long long: en.cppreference.com/w/cpp/types/integer

Goswin von Brederlow 17.05.2022 11:01
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
0
6
55
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Эта строка в вашей функции int res = F(N - 1) + F(N - 2); делает ваш результат целым числом, которое затем приводится к типу long long. поэтому здесь происходит переполнение. Должен быть помечен некоторыми флагами компилятора.

long long F(int N) {
    if (Fs[N] != -1) {
        return Fs[N];
    }
    // int res = F(N - 1) + F(N - 2); // HERE !
    long long res = F(N - 1) + F(N - 2);
    Fs[N] = res;
    return res;
}

Что за..... Какой же я глупый.

zarkli 17.05.2022 10:37

Я рекомендую использовать некоторые флаги с вашим компилятором, работающим на g++ или clang: interrupt.memfault.com/blog/… Это может помочь вам определить такие вещи, у меня всегда будет как минимум -Wall -Wextra

SidoShiro92 17.05.2022 10:45

@zarkli Не глупо — просто без присмотра ;)

Aconcagua 17.05.2022 10:55

Иногда вам просто нужно встать; выпить кофе/чай/воду, прогуляться 2 минуты и вернуться к функции

SidoShiro92 17.05.2022 11:08

Другие вопросы по теме