Блог

Главная - Вопросы по программированию - C N-е Число Фибоначчи Проблема Работы С Большим Числом

C N-е Число Фибоначчи Проблема Работы С Большим Числом

#c #c 11 #math

Вопрос:

Я работаю над функцией, которая считает N-е число из последовательности Фибоначчи.

Я использую этот алгоритм для его вычисления: https://artofproblemsolving.com/wiki/index.php/Binet’s_Formula

Проблема в том, что я работаю с большими числами, и я понятия не имею, как хранить данные, чтобы предотвратить их просчеты и другие ошибки :/

Я видел несколько сообщений в стеке, и люди предлагают разделить числа на части и вычислить их таким образом — я думаю, что это просто временное и своего рода примитивное решение.

Существует ли какой-либо новый, современный и не такой сложный метод хранения больших чисел и работы (включая математические операции) с ними без каких-либо ошибок??

Вот функция:

 std::string fibonacci(int n)
{

   long double numb = 1 / sqrt(5) * (pow(((1   sqrt(5)) / 2),n) - pow(((1 - sqrt(5)) / 2),n));

   return std::to_string(numb);

}

Вот вывод о том, как меняются результаты:

 Input:  40
Output: 102334155.000000
Answer: 102334155
    
Input:  50
Output: 12586269025.000021
Answer: 12586269025

Input:  60
Output: 1548008755920.002930
Answer: 1548008755920

Input:  70
Output: 190392490709135.437500
Answer: 190392490709135

Input:  80
Output: 23416728348467744.000000
Answer: 23416728348467685

Input:  90
Output: 2880067194370825216.000000
Answer: 2880067194370816120

Input:  100
Output: 354224848179263111168.000000
Answer: 354224848179261915075

Комментарии:

1. почему вы используете формулу Бинета? Похоже, что это в основном представляет аналитический интерес, но не совсем хорошо подходит для численных расчетов, потому что есть термин, который намного больше, чем конечный результат, и он основан на плавающих точках

2. кстати, у бедняги большая библиотека номеров std::string . Вы можете избежать переполнения, выполняя все операции только со строками так, как вы учили их в школе

3. Это похоже на какую-то онлайн-проблему, пожалуйста, предоставьте ссылку на нее, чтобы все требования были понятны.

4. Фибоначчи можно представить в виде матрицы, тогда вычислительный n элемент этой последовательности-это просто вычислительная n мощность матрицы ((1, 1), (1, 0)) . Похоже, вам придется реализовать сложение и умножение больших чисел.

5. Для этого нет встроенного оператора. Вы должны делать это вручную, как вы учили в начальной школе. Возьмите ручку и лист бумаги, чтобы добавить 1224 к 4321. Тщательно продумывайте каждый свой шаг, чтобы прийти к окончательному результату. Затем сделайте то же самое в коде

Ответ №1:

Благодаря советам @463035818_is_not_a_number мне удалось решить эту ошибку — добавить числа в строки, подобные этой:

   1
  27
  59
----
  86

Кроме того, я немного изменил свой исходный код:

  1. Я делаю i как статику, чтобы функция не начинала отсчет с самого начала
  2. Вместо постоянно растущего вектора я использовал две строки — для подсчета третьего числа нам нужны только два предыдущих, не более

Вот функция:

 //Soln Author:  ernikus

#pragma once

#include <iostream>
#include <string>
#include <vector>


void reverseStr(std::string amp;str)
{
    int n = str.length();

    for (int i = 0; i < n / 2; i  )
        std::swap(str[i], str[n - i - 1]);
}


int char_to_int(const char character)
{
    return (int(character) - 48);
}



std::string fibonacci(int n)
{
    static std::string number[2]{ "0", "1" };

    const int limit = 201;

    if ((n - 1) <= 1)
        return number[n - 1];

    for (static int i = 2; i <= limit; i  )
    {
        int size1 = number[0].size();
        int size2 = number[1].size();

        int size = size2;
        int diff = size - size1;

        std::cout << "Numer1: " << number[0] << "tNumber2: " << number[1] << std::endl;
        std::cout << "Size1: " << size1 << "tSize2: " << size2 << "tHigh Size: " << size << "tDiff: " << diff << std::endl;

        std::string result{};
        bool higher = false;

        for (int j = size - 1; j >= 0; j--)
        {
            int trial{ 0 };


            if ((j - diff) >= 0)
            {
                trial = char_to_int(number[0][j - diff])   char_to_int(number[1][j]);

                std::cout << "I.tNum1: " << number[0][j - diff] << "tNum2: " << number[1][j] << std::endl;
            }
            else
            {
                trial = char_to_int(number[1][j]);

                std::cout << "I.tNum2: " << number[1][j] << std::endl;
            }


            if (higher == true)
            {
                trial  ;
                higher = false;
            }

            if (trial >= 10)
            {
                higher = true;
                trial -= 10;
            }

            result  = std::to_string(trial);

            std::cout << "Trial: " << trial << "tResult: " << result << "tJ: " << j << std::endl;
        }

        if (higher == true)
        {
            result  = "1";
            higher = false;
        }

        reverseStr(result);

        std::cout << i << ". " << result << std::endl;

        number[0] = number[1];
        number[1] = resu<

        if (i == n)
        {
            i  ;
            return resu<
        }
            
    }

    return "0";
}

Результат очень удовлетворительный 🙂

 Input:  180
Output: 18547707689471986212190138521399707760
Answer: 18547707689471986212190138521399707760
Correct Answer!

Input:  190
Output: 2281217241465037496128651402858212007295
Answer: 2281217241465037496128651402858212007295
Correct Answer!

Input:  200
Output: 280571172992510140037611932413038677189525
Answer: 280571172992510140037611932413038677189525
Correct Answer!

Input:  222
Output: 11111460156937785151929026842503960837766832936
Answer: 11111460156937785151929026842503960837766832936
Correct Answer!

Input:  1111
Output: 6851462981265369536304298877223231154064355390623195419885661484162849735541256952762360871448156142552148460793441585691068131682370855135019896825808086317430648360941203391832868742715640036246053259136014253626356840914521594989Answer: 6851462981265369536304298877223231154064355390623195419885661484162849735541256952762360871448156142552148460793441585691068131682370855135019896825808086317430648360941203391832868742715640036246053259136014253626356840914521594989Correct Answer!

Input:  11111
Output: 515449135231559341621591189426925989418721609167804403107087312453694294479381404009230187092526675635022414542794904158934368158350216751867828729213516067642461147232232268304004580596220514978296704097915617589481297010691749471374967376304898014174716132125169572206688299944881902864940487579850754037243411123276226268998274067232370656873037885028569262362061989878439356579125363739644638605976667733232134130196207453194213358616463005487086631652051025004934485196108344869244852506414543015664379038338857611347469102943415360234480491921571800239803284078147859161629100936007246749423449323827401152142684138017539299637210829955409666781554035555164800825902557894478979141680264821730580654526990976167873657740460977594388216677737796493623940501749951993194553070912364327001564086186444836587037180810655016948562608480145057901528396467327800369394725748856906177005886944277609832795419082424474419033931754123200248752600310587761729439189440527073799320938597514569967706344559861576816209214912702962065352672071494639021231263782338510241176219316180788341549329905272081790433223099472061887224254193326845457247107409050092252994931668934553671721376871177693036352993174131508107261653495025271505086039171034392185521383307925723081097129536244468148375789733582131797176285225457221029865658845503179175504307577930140222583997281098099332145783930418777810346276337273420733754768191403158839413163368990092771464626510432292314209966950363068432367028332284209840897425718364670733733609565321893240873729315360915814803137552560521106490937691421540344502423323064743545226360364012549367167257038202145921861042955299329942301124074181956428710271876930526019606797077558959445434943166179407403375284366340173639269807373108055388080201746447050804598946499248800891171987624229020766742994219485280547337990630263452898332213470171667603200991268579583095661682595442200149483262133621860660302141160974707437100532341443580636798210704649175613121627855118061762876137389590812891131603206815601843823369210865672605256743142632199819790960079549275267815983406188538500072911327187912330503064073869613282412315795790671452556371408354045852898125070873750632615799469070245720036053071341314252092446074260578417947762296896685389368685659291620443322232933074723685001342680075497489
Answer: 515449135231559341621591189426925989418721609167804403107087312453694294479381404009230187092526675635022414542794904158934368158350216751867828729213516067642461147232232268304004580596220514978296704097915617589481297010691749471374967376304898014174716132125169572206688299944881902864940487579850754037243411123276226268998274067232370656873037885028569262362061989878439356579125363739644638605976667733232134130196207453194213358616463005487086631652051025004934485196108344869244852506414543015664379038338857611347469102943415360234480491921571800239803284078147859161629100936007246749423449323827401152142684138017539299637210829955409666781554035555164800825902557894478979141680264821730580654526990976167873657740460977594388216677737796493623940501749951993194553070912364327001564086186444836587037180810655016948562608480145057901528396467327800369394725748856906177005886944277609832795419082424474419033931754123200248752600310587761729439189440527073799320938597514569967706344559861576816209214912702962065352672071494639021231263782338510241176219316180788341549329905272081790433223099472061887224254193326845457247107409050092252994931668934553671721376871177693036352993174131508107261653495025271505086039171034392185521383307925723081097129536244468148375789733582131797176285225457221029865658845503179175504307577930140222583997281098099332145783930418777810346276337273420733754768191403158839413163368990092771464626510432292314209966950363068432367028332284209840897425718364670733733609565321893240873729315360915814803137552560521106490937691421540344502423323064743545226360364012549367167257038202145921861042955299329942301124074181956428710271876930526019606797077558959445434943166179407403375284366340173639269807373108055388080201746447050804598946499248800891171987624229020766742994219485280547337990630263452898332213470171667603200991268579583095661682595442200149483262133621860660302141160974707437100532341443580636798210704649175613121627855118061762876137389590812891131603206815601843823369210865672605256743142632199819790960079549275267815983406188538500072911327187912330503064073869613282412315795790671452556371408354045852898125070873750632615799469070245720036053071341314252092446074260578417947762296896685389368685659291620443322232933074723685001342680075497489
Correct Answer!
Метки: