c++ - C++第N个斐波那契数大数运算问题

问题描述

我正在研究从斐波那契数列中计算第 N 个数的函数。

我正在使用该算法来计算它：https ://artofproblemsolving.com/wiki/index.php/Binet%27s_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

标签： c++c++11math

感谢@463035818_is_not_a_number的建议，我设法解决了这个错误 - 在字符串中添加数字，如下所示：

  1
  27
+ 59
----
  86

我也稍微改变了我的原始代码：

我将i其设为静态以防止函数从头开始计数
我没有使用不断增长的向量，而是使用了两个字符串 - 计算第三个数字，我们只需要两个前一个，不再需要了

这是功能：

//Soln Author:  ernikus

#pragma once

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


void reverseStr(std::string &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] = result;

        if (i == n)
        {
            i++;
            return result;
        }
            
    }

    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!

c++ - C++第N个斐波那契数大数运算问题

问题描述

解决方案

推荐阅读