C++ 计算斐波那契数列第100万项的精确整数值

您所在的位置：网站首页 › 用python算斐波那契数列的第多少项 › C++ 计算斐波那契数列第100万项的精确整数值

C++ 计算斐波那契数列第100万项的精确整数值

2024-06-23 23:38| 来源: 网络整理| 查看: 265

上一篇《各整型数据能计算出斐波那契数列的最大项数是几？》答案是用unsigned long long型计算，最大只能输出第93项，再往后一项就溢出了。如果要计算的项数上万、几十万，甚至到百万级，就只能用字符串来帮忙了；因为理论上string的最大长度可以到4个G，所以可以认为它是无限的。用字符串代替数字做加法运算，自定义函数如下：

string strAdd(string a, string b) { unsigned short j=0,k=0; string c; size_t n = b.size(); if (a.size()0;i--){ k=(a[i-1]-'0')+(b[i-1]-'0')+j; if (k>9){ c+=(k-10)+'0'; j=1; } else{ c+=k+'0'; j=0; } } reverse(c.begin(),c.end()); if (j==1) c='1'+c; return c; }

这样就可以用常规的几种方法来计算斐波那契数列的精确整数值了，先来算一下第100,000项的值：

25974069347221724166155034021275915414880485386517696584724770703952534543511273 68626555677283671674475463758722307443211163839947387509103096569738218830449305 22876385313349213530267927895670105127657827163560807305053220024323311438398651 61378272381247774537783372999162146340500546698603908627509966393664092118901252 71960172105060300350586894028558103675117658251368377438684936413457338834365158 77542537191241050033219599133006220436303521375652542182399869084855637408017925 17616293917549634585586163007628199160811098365263529954406942842065710460449038 05647136346033000520852277707554446794723709030979019014860432846819857961015951 00185060826491923458731339915013391993236310230186417253647713626647508013398243 12317034314529641817900511879573167668349799016820118499077566864568450662873924 85603914047605199550066288826345877189410680370091879365001733011710028310473947 45625609144493282137485557386408057981302826664027035429441210491999580313187680 58991865134251759599115205631553377039969410355182752749199598022575079020377981 03089922984996304496255814045517000250299764322193462165366210841876745428298261 39823447836658158804081900330738293950008213200937471548513102722081730543226486 69496309879147143629255542526240439996153269798768075106468190687921182991679644 09178271868561702918102212679267401362650499784968843680975254700131004574186406 44829948587255174474669565187912691699324456481767332225714931496776334584662383 03338202397024368594782876418757885729107101337003000942293335972927791914092128 04901545976262791057055248158884051779418192905216769576608748815567860128818354 35429230739781015478570132843861272862017665395344499300198006295389369855007232 86651317181135886613537472684585432548981137176605194616937916884425342594781263 10388952047956594380715301911253964847112638900713362856910155145342332944128435 72209962867461194209516610023097407099655319005081586699114454426478828726428450 17253320486483194578920399848938236367456182203750973485668474338872490493370316 33826571760729778891798913667325190623247118037280173921572390822769228077292456 66275053833750069260772105936194212689203025674435653780083183063759333450235025 69729065152853271943677560156660399164048825639676930792905029514886934137991251 74856667074717514938979038653338139534684837808612673755438382110844897653836848 31825883633991731045585090566384620250146313118310874290772926221594302042915947 40306101839816855066950261973761508571761199475875722129872053120607918649803615 96092339594104118635168854883911918517906151156275293615849000872150192226511785 31508925102752804515123860379218469212153382928713692432152733271415747882959026 01571954853164447945467502858402360002383447905203451080332820138038807089807348 32620122795263360677366987578332625485944906021917368867786241120562109836985019 72901771578011204045864915393511578349954610063663574544850824188827906753135995 05192062229760153765297973085881648731173082370598284894044874039320535929359764 54165560795472477862029969232956138971989467942218727360512336559521133108778758 22887959758032045960847902450638519417431261637751045992110248687949634170686209 29088930685252348056925998333775103901013166178123051145719327066291671254465121 51746802548190358351688971707570677865618800822034683632101813026232996027599403 57999777404624495211453158837035790448329315000724617341735580556783215345434117 00202585608091662941986374015145695722728369219632295111877625307534025947814482 04657460288485500062806934811398276016855584079542162057543557291510641537592939 02288435612079264370556006236798654438246437394697247194599655579550583803482559 78396827760847315302517889517186307227611036305093600742622617173630586132915440 24695432904616258691774630578507674937487992329181750163484068813465534370997589 35360740517290941269765759329515681862474712763646883655175701835341727466260730 65104511957628663499228486787805910851189856535554349587616640164475880286336297 04046289097067736256584300235314749461233912068632146637087844699210427541569410 91224656857120471724113337848981676409692498163342117685715031167104006817530319 21154156119580425706586931272762137106974722260296555246110537155545324997508432 75200199214301910505362996007042963297805103066650638786268157658772683745128976 85079636637105938091122542883583919412115477375998130192165095214013330607098731 37329265181692268450634439540567298120315463923249817937804691037934221694952291 00793029949237507299325063050942813902793084134473061411643355614764093104425918 48136393054236937897652052645634764831827263337151211203062923388928648794920973 78478618848682608046473195392008403983080088038690495574197562192939221108257663 97681361044490024720948340326796768837621396744075713887292863079821849314343879 77808873795889684094614341592713175783651145782893558185990292353438888884658745 21308381377794436361197628390368945957601203165022798579015453447473527069728514 54599861422902737291131463782045516225447535356773622793648545035710208644541208 98423503890877022303984938021473480968743333622544915011741175157070456105089527 40002063804979679604026178186644812485472696308234733772455433905198413087697812 76565916764229022948181763075710255793365008152286383634493138089971785087070863 63220586901893837776606300606675773242727292924742129526500070664672273000995612 41914091389846752249557907293984956087504566942177715511073466304566039441362358 88443676215273928597072287937355966723924613827468703217858459948257514745406436 46099705931612059684156047323439665245723165031779283386059038836041769142873273 57039868033426046700717173635730911229813069032861371225979370966057751729645282 63757434075792282180744352908669606854021718597891166333863858589736209114248432 17864503947919542420819162608857106911043399480147301310086984886643072121676247 31196181907378207665829682807960794822595490363282665780069948568253005364366748 22534603705134503603152154296943991866236857638062351209884448741138600171173647 63212602996140856192559970756682786677873237741944446227539990929104469771647615 11186723272386792081333673061819448493966071233452718565202536436219641987827529 78813060080313141817069314468221189275784978281094367751540710106350553798003842 21904550848223938699329692665922111274269813306230007346562849809363669304944680 16285537126334126203784919194986000972008367278766507868863069334189952257683143 90832484886340318940194161036979843833346608676709431643653538430912157815543512 85207772085809890209958644960247949197068723076568710923438071950982481447315781 37800806393584187566550985013218828528401849814076907385073695353777118803885289 35347600930338598691608289335421147722936561907276264603726027239320991187820407 06741227225812076672904007192423793033097213236418409395610299597129179982829000 95391473824378027790511120309545825328887211461701334403859396540478061993332245 47317803407340902512130217279595753863158148810392952475410943880555098382627633 12760671812617102201135618180077540022751673414416921642497317562136312858828197 80057888324545345815224349372681334339977105125320814783450671398350383329013139 45986481820272322043341930929011907832896569222878337497354301561722829115627329 46881485328192210075237362682764315268573549322302801810144964900901552924863833 88856648930022509743436012008143651536253691994467097111269519667257800618912154 40222487564601554632812091945824653557432047644212650790655208208337976071465127 50832048716527157747232588727576112835759213255393444628943325810502863358366929 18285668947362235082502949640657986308096143416968304675951743553132243626642071 97608459024263017473392225291248366316428006552870975051997504913009859468071013 60233644016440017918861085323076499171437205446782359721176046515320016308533631 93515896458906817223728123103202718979179512727996560536940321112428465909945563 80215461316106267521633805664394318881268199494005537068697621855231858921100963 44101293353573391845966819753983428469682288946007635203168892200202193131836975 75569620611157743058263055358620156378912460312206729339926173783796251509999354 03648731423208873977968908908369996292995391977217796533421249291978383751460062 05496734166283348734101109777053589806649813601139557158432830871394058253527405 60810115039079416880791972129331483030726386786314110384431282159949368243429981 88719768637604496342597524256886188688978980888315865076262604856465004322896856 14925506396881140440042950389424587238223354310107869151732833360477926272776568 60761777056168740502577437499837758301438561354272738385897741335269491654839297 21519554793578923866762502745370104660909382449626626935321303744538892479216161 18888970207791044856319951482663080287954954645358386630734442375331971227915886 17072896520901498483054359832007713266534072906620167757064096901837712013068232 45333477966660525325490873601961480378241566071271650383582257289215708209369510 99589013285949072430618332575520120809000717502202294974280182344541371191629844 99147222541965946822214682606449618392542496709031040075814888579716722463228870 16438403908463856731164308169537326790303114583680575021119639905615169154708510 45970054209857179731801556474140617233414584711126854792989244300139146828910367 91792169786165824890073220335913767065276765213071439853027609884780562169946596 55461379174985659739227379416726495377801992098355427866179123126699374730777730 56932443016683933301155451554265686493749212868704912175424596783113296924849246 67442619990339728256748734602011504422287804661243201830161082321839086547710423 98228531316559685688005226571474428823317539456543881928624432662503345388199590 08510521138312449186180262443219554043398572284134125440941177172215686708629174 21240531106205228429861992736294062088347548536451281232796090972139537753600230 76765694208219943034648783348544492713539450224591334374664937701655605763384697 06291872574542650587941463017663976045747431108155674709165270874812526715991379 32405273046136939611698925898083119063225107779285620719994594877006118010022961 32304588294558440952496611158342804908643860880796440557763691857743754025896855 92725251456340438521782589059955395462745138545445291676104296926797089358005623 45019185714890304184957674008193599732187119574963570959678251710962647520688908 06407651445893132870767454169607107931692704285168093413311046353506242209810363 21677191042078616218421376393819462569728678141363638962012397691046541895680619 73231484142245500716172158513213020306841760872158927020988791089380810459033972 76547326416916845445627600759561367103584575649094430692452532085003091068783157 56151984756756919128478465469255866511155791346127242533608363513134218390517715 45112284644551360160135132289485432715047608393075561009087860966638706122786902 74831819331606701484957163004705262228238406266818448788374548131994380387613830 12885988526420199228618820849958864088852135250145761539648264745102590253074317 29568996364996157075518558371659353671254485150893629045677366300355624573747791 00987992499146967224041481601289530944015488942613783140087804311431741858071826 18514905113874483135843906722894940825828602165028892722838742643278616869038196 05301558944594518087351972460082215293439808282541261282571572093509853828007385 60472910941184006084485235377833503306861977724501886364070344973366473100602018 12879288699186182441845396899477725948216913713364747045317297980924584436112961 89975956962409718455640205114325895918447249209429303016514887130798021023790655 36525154780298059407529440513145807551537794861635879901158192019808879694967187 44822415683646353432616024263293476163445816389016380512389418452397342184149688 92623984896486420934098166814947711551770095626690298501015135375998012725012419 71119871526593747484778935488777815192931171431167444773882941064615028751327709 47450476392287489066298984154025935083403514203513616881924823899802770666691634 21334243120545073593886166876911881857761181357713324839652098820859823912986063 86822804754362408956522921410859852037330544625953261340234864689275060526893755 14840329854208699122105259700562857670770256769530097897004640892000985210698029 54196998021380532957981594782899344432454915653278452238405512404452082264354206 56313310702940722371552770504263482073984454889589248861397657079145414427653584 57295132971909194769441191096679747426267559095383203916967349426136003226307742 86841050400613510521944137781580950057145268460098103521092490400279580507364369 61021241137739717164869525493114805040126568351268829598413983222676377804500626 50724173175739521979689075482519932925964980162706866565803017887740561516715973 19273204793762473755058550528396602945669925221736008740812120142090710419375985 71721431338017425141582491824710905084715977249417049320254165239323233258851588 89333709713631089257153141776197832603375010902628406641580137135935652927808845 63059517700814439941146742918503607488523666547448699280832305168157116029118363 74147958492100860528981469547750812338896943152861021202736747049903930417035171 34212692348670056662750622905863691188222890317051030540688209697087554532936943 40639812976964780318254516421783473477164710584232385945801830527562139101869976 04305844068665712346869679456044155742100039179758348979935882751881524675930878 92815924349219754538766830568466842077540982178124705335452319479739895332017598 86402810588255576980043971205383124594289573776960018574973352499650135093689259 58021863811725906506436882127156815751021712900765992750370228283963962915973251 17341858672102349731776596945428362551937155600914368032931196284254662840314244 43706484323903749064108113007928489557672434812000903098884572709077508736388732 99642555050473812528975962934822878917619920725138309388288292510416837622758204 08191893360365387528411678570372098971883298692192781662967584458017491180911966 30481874341550677908639488314892415043004767045279712834822115222028370628573142 44107823792513645086677566622804977211397140621664116324756784216612961477109018 82609467737768640617672148429389497667138012278894130902655351109611834701256519 75408070953840609168639369066737866272094294342642604029021583173450037274625889 92622049877121178405563348492490326003508569099382392777297498413565614830788262 36332236838070982234601227424137903647345173592521575475716093427093519290172395 49214264906911152715233381091240428121028937384881673589539345089306977155229891 99698903885883275409044300321986834003470271220020159699371690650330547577095398 74858067002449104550489006172718916803139452803616563394157133463722255047754746 07560550241087643821216888489169403712589019484906853797222445620094838194915327 24502276218589169507405794983759821006604481996519360110261576947176202571702048 68491461689406840414083358756211831921083800563214456201894150594578002531874747 19116048406779977654148306221790693308538751292989830095802775541454350587689849 44179136535891620098725222049055183554603706533183176716110738009786625247488691 47607766447014719307447630241166033567176556487444057799053199627163297200910944 92492164560306188277729477507647774464525863289191591074442523200829182095180210 83700353881330983215894608680127954224752071924134648334963915094813097541433244 20929993075148107791900234612812233016179942993061880053341455063393213933964686 16164169552202164479954172431711657444713641977332048993650747678441499295480730 25856442942381787641506492878361767978677158510784235702640213388018875601989234 05686842321558562850864552525837701062053222424498799062526348401077432248817255 86022333020763999338541520153438477254429178951306370503204449177977523708719582 77976799686113626532291118629631164685159934660693460557545956063155830033697634 00027668515129384363888609082837614115773200352756515874590656702543943793110483 85713132944906049265823631089495350900826731544972263966480886180415739778884728 92174618974189721700770009862449653759012727015227634510874906948012210684952063 00251901165596358055242918020558690425968526104741283451846673693858002770025296 53563667216198836724282269339503259303909945831686655422346548570208755046175205 21853721567282679903418135520602999895366470106557900532129541336924472492212436 32452304289518846177912233806967423398069488727058750338922839509513520912310925 81590069603951563677360671090505662996035718764232479207528361608055976977787564 76767210521222327184821484446631261487584226092608875764331731023263768864822594 69121103236773755812213347055680595800831012748167396201958359802396741448986727 68458698193767837571679367232130815861910459950589709910646869194634480385741438 29629547131372173669836184558144505748676124322451519943362182916191468026091121 79300186478805006135160314435007618921344160248809174105123229035717920549792797 09245024799408426961588184426161637800447594782122408732041244211691998055726491 18243661921835714762891425805771871743688000324113008704819373962295017143090098 47692723749887593863994253059533160789161881086350598244457894279934651491595288 48697574880258233535716778648268280511408854297327881977657369660057277001625924 04301688659946862983717270595809808730901820120931003430058796552694788049809205 48430546761103465474806729067439976361259243463771999584386281239198547020241488 00768808188480878923915913694632931132768493297772016466417275872591223547844808 13433328050087758855264686119576962172239308693795757165821852416204341972383989 93273480342926234072233815510220910126294924974242327169884202329730326016179057 56731112354658902982983131151236076067739689981538122869996420146098525797936912 46016346088762321286205634215901479188632194659637483482564291616278532948239313 22944023104327728876813955021334826638868745325928158785450389099156194963247885 50350902893909737189880039990261320158726786378730956781096253110080544894188579 83565902063680699643165033912029944327726770869305240718416592070096139286401966 72575008701221814973313369580960036975176495135004028592624920339811101495322753 36218445007443315624345324842179861083462613458975912348399707518542232816771872 15956827243245910829019886390369784542622566912542747056097567984857136623679023 87847816120147798293908051315025817452377352951016529693456278612224115078358775 53733483727644398380820006672147400344663227769189369676128789834889420946881023 08427036452854504966759697318836044496702853190637396916357980928865719935397723 49548678718041640141528148944378503629107151780528585758398771114547424015641647 71941163913549354667555935926088492005463846854030280809364172505836533680934072 25310820844723570226809826951426162451204040711501448747856199922814664565893938 48802864382231384985232845236066704580511367966375103924816333617327454727577563 68109773445392758275605974251607054686896577945305216023159398657809748015154149 87097778078705357058008472376892422189750312758527140173117621279898744958406199 84391336568029772120875193498850449971391428515803232482302134063031258607262454 16377652345055220510863182853596585207081733927095664450114040551065790550374177 80393351658360904543047721422281816832539613634982525215232257690920254216409657 45261806605177790159290288424059999888275369195754011695469615227040128085757976 61547221929256559639918209488946426575122887663303021337463674492174493516371047 25732980832812726468187759356584218383594702792013663907689741738962252575782663 99080979264701140758036785059938188718456009469583327077512618128201539104177395 09182441375619999378192403624695582359241714787027794484431087519018074141102903 70706052085162975798361754251041642244867577350756338018895379263183389855955956 52785722792615552449473936366553390452865621546428834316228292112329045184221253 28881014158840616199391950422300598983499665694635801868167170748188232158486477 34386780911564660755175385552224428524049468033692299989300783900020690121517740 69642857393019691050098827852305379763794025796895329511243616677891058555721338 17890899454539479159273749586002682378444868720372434888346168562900978505324970 36933361942439802882364323553808208003875741710969289725499878566253048867033095 15051845212694498925159639207942145260650851605232561486193828248983800081508535 15646427617008320964831179444019717801492133453359033366723767192297220699707660 55482452247416927774637522135201716231722137632445699154022395494158227418930589 91174693177377651873585003231801443288391637424379585469569122177409894861151556 40466095650945381155209218637115186845625432750478705300069984231401801694211091 05925493596116719457630962328831271268328501760321771680400249657674186927113215 57327004993570994232441638708924242758440765121557267603792476534180898431267694 11103131659514294793776706988812496434219332874043904855382221608370889075982773 90184204138197811025854537088586701450623578513960109987476052535450100439353062 07243970997644514679099338144899464460978095773195360493873495002686056455569322 42296918156302939224876064708734311663842054424896287602136502469918930401125131 03835085621908060270866604873585849001704200923929789193938125116798421788115209 25913043557232163566089560351438388393901895316627435560997001569978028923636234 9895374653428746875 第100000项的长度：20899 -------------------------------- Process exited after 43.28 seconds with return value 0 请按任意键继续. . .

计算数列第10万项的源代码如下：

#include #include #include #include #include #include using namespace std; string strAdd(string a, string b) { unsigned short j=0,k=0; string c; size_t n = b.size(); if (a.size()0;i--){ k=(a[i-1]-'0')+(b[i-1]-'0')+j; if (k>9){ c+=(k-10)+'0'; j=1; } else{ c+=k+'0'; j=0; } } reverse(c.begin(),c.end()); if (j==1) c='1'+c; return c; } string fib1(long n) //定义递推法 { string a = "1"; string b = "1"; string c; for (auto i=3; i

【本文地址】

C++ 计算斐波那契数列第100万项的精确整数值

C++ 计算斐波那契数列第100万项的精确整数值

今日新闻

推荐新闻