分享

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

 新用户21391806 2021-11-07

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

  1. string strAdd(string a, string b)
  2. {
  3. unsigned short j=0,k=0;
  4. string c;
  5. size_t n = b.size();
  6. if (a.size()<n) a='0'+a;
  7. for (size_t i=n;i>0;i--){
  8. k=(a[i-1]-'0')+(b[i-1]-'0')+j;
  9. if (k>9){
  10. c+=(k-10)+'0';
  11. j=1;
  12. }
  13. else{
  14. c+=k+'0';
  15. j=0;
  16. }
  17. }
  18. reverse(c.begin(),c.end());
  19. if (j==1) c='1'+c;
  20. return c;
  21. }

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

  1. 25974069347221724166155034021275915414880485386517696584724770703952534543511273
  2. 68626555677283671674475463758722307443211163839947387509103096569738218830449305
  3. 22876385313349213530267927895670105127657827163560807305053220024323311438398651
  4. 61378272381247774537783372999162146340500546698603908627509966393664092118901252
  5. 71960172105060300350586894028558103675117658251368377438684936413457338834365158
  6. 77542537191241050033219599133006220436303521375652542182399869084855637408017925
  7. 17616293917549634585586163007628199160811098365263529954406942842065710460449038
  8. 05647136346033000520852277707554446794723709030979019014860432846819857961015951
  9. 00185060826491923458731339915013391993236310230186417253647713626647508013398243
  10. 12317034314529641817900511879573167668349799016820118499077566864568450662873924
  11. 85603914047605199550066288826345877189410680370091879365001733011710028310473947
  12. 45625609144493282137485557386408057981302826664027035429441210491999580313187680
  13. 58991865134251759599115205631553377039969410355182752749199598022575079020377981
  14. 03089922984996304496255814045517000250299764322193462165366210841876745428298261
  15. 39823447836658158804081900330738293950008213200937471548513102722081730543226486
  16. 69496309879147143629255542526240439996153269798768075106468190687921182991679644
  17. 09178271868561702918102212679267401362650499784968843680975254700131004574186406
  18. 44829948587255174474669565187912691699324456481767332225714931496776334584662383
  19. 03338202397024368594782876418757885729107101337003000942293335972927791914092128
  20. 04901545976262791057055248158884051779418192905216769576608748815567860128818354
  21. 35429230739781015478570132843861272862017665395344499300198006295389369855007232
  22. 86651317181135886613537472684585432548981137176605194616937916884425342594781263
  23. 10388952047956594380715301911253964847112638900713362856910155145342332944128435
  24. 72209962867461194209516610023097407099655319005081586699114454426478828726428450
  25. 17253320486483194578920399848938236367456182203750973485668474338872490493370316
  26. 33826571760729778891798913667325190623247118037280173921572390822769228077292456
  27. 66275053833750069260772105936194212689203025674435653780083183063759333450235025
  28. 69729065152853271943677560156660399164048825639676930792905029514886934137991251
  29. 74856667074717514938979038653338139534684837808612673755438382110844897653836848
  30. 31825883633991731045585090566384620250146313118310874290772926221594302042915947
  31. 40306101839816855066950261973761508571761199475875722129872053120607918649803615
  32. 96092339594104118635168854883911918517906151156275293615849000872150192226511785
  33. 31508925102752804515123860379218469212153382928713692432152733271415747882959026
  34. 01571954853164447945467502858402360002383447905203451080332820138038807089807348
  35. 32620122795263360677366987578332625485944906021917368867786241120562109836985019
  36. 72901771578011204045864915393511578349954610063663574544850824188827906753135995
  37. 05192062229760153765297973085881648731173082370598284894044874039320535929359764
  38. 54165560795472477862029969232956138971989467942218727360512336559521133108778758
  39. 22887959758032045960847902450638519417431261637751045992110248687949634170686209
  40. 29088930685252348056925998333775103901013166178123051145719327066291671254465121
  41. 51746802548190358351688971707570677865618800822034683632101813026232996027599403
  42. 57999777404624495211453158837035790448329315000724617341735580556783215345434117
  43. 00202585608091662941986374015145695722728369219632295111877625307534025947814482
  44. 04657460288485500062806934811398276016855584079542162057543557291510641537592939
  45. 02288435612079264370556006236798654438246437394697247194599655579550583803482559
  46. 78396827760847315302517889517186307227611036305093600742622617173630586132915440
  47. 24695432904616258691774630578507674937487992329181750163484068813465534370997589
  48. 35360740517290941269765759329515681862474712763646883655175701835341727466260730
  49. 65104511957628663499228486787805910851189856535554349587616640164475880286336297
  50. 04046289097067736256584300235314749461233912068632146637087844699210427541569410
  51. 91224656857120471724113337848981676409692498163342117685715031167104006817530319
  52. 21154156119580425706586931272762137106974722260296555246110537155545324997508432
  53. 75200199214301910505362996007042963297805103066650638786268157658772683745128976
  54. 85079636637105938091122542883583919412115477375998130192165095214013330607098731
  55. 37329265181692268450634439540567298120315463923249817937804691037934221694952291
  56. 00793029949237507299325063050942813902793084134473061411643355614764093104425918
  57. 48136393054236937897652052645634764831827263337151211203062923388928648794920973
  58. 78478618848682608046473195392008403983080088038690495574197562192939221108257663
  59. 97681361044490024720948340326796768837621396744075713887292863079821849314343879
  60. 77808873795889684094614341592713175783651145782893558185990292353438888884658745
  61. 21308381377794436361197628390368945957601203165022798579015453447473527069728514
  62. 54599861422902737291131463782045516225447535356773622793648545035710208644541208
  63. 98423503890877022303984938021473480968743333622544915011741175157070456105089527
  64. 40002063804979679604026178186644812485472696308234733772455433905198413087697812
  65. 76565916764229022948181763075710255793365008152286383634493138089971785087070863
  66. 63220586901893837776606300606675773242727292924742129526500070664672273000995612
  67. 41914091389846752249557907293984956087504566942177715511073466304566039441362358
  68. 88443676215273928597072287937355966723924613827468703217858459948257514745406436
  69. 46099705931612059684156047323439665245723165031779283386059038836041769142873273
  70. 57039868033426046700717173635730911229813069032861371225979370966057751729645282
  71. 63757434075792282180744352908669606854021718597891166333863858589736209114248432
  72. 17864503947919542420819162608857106911043399480147301310086984886643072121676247
  73. 31196181907378207665829682807960794822595490363282665780069948568253005364366748
  74. 22534603705134503603152154296943991866236857638062351209884448741138600171173647
  75. 63212602996140856192559970756682786677873237741944446227539990929104469771647615
  76. 11186723272386792081333673061819448493966071233452718565202536436219641987827529
  77. 78813060080313141817069314468221189275784978281094367751540710106350553798003842
  78. 21904550848223938699329692665922111274269813306230007346562849809363669304944680
  79. 16285537126334126203784919194986000972008367278766507868863069334189952257683143
  80. 90832484886340318940194161036979843833346608676709431643653538430912157815543512
  81. 85207772085809890209958644960247949197068723076568710923438071950982481447315781
  82. 37800806393584187566550985013218828528401849814076907385073695353777118803885289
  83. 35347600930338598691608289335421147722936561907276264603726027239320991187820407
  84. 06741227225812076672904007192423793033097213236418409395610299597129179982829000
  85. 95391473824378027790511120309545825328887211461701334403859396540478061993332245
  86. 47317803407340902512130217279595753863158148810392952475410943880555098382627633
  87. 12760671812617102201135618180077540022751673414416921642497317562136312858828197
  88. 80057888324545345815224349372681334339977105125320814783450671398350383329013139
  89. 45986481820272322043341930929011907832896569222878337497354301561722829115627329
  90. 46881485328192210075237362682764315268573549322302801810144964900901552924863833
  91. 88856648930022509743436012008143651536253691994467097111269519667257800618912154
  92. 40222487564601554632812091945824653557432047644212650790655208208337976071465127
  93. 50832048716527157747232588727576112835759213255393444628943325810502863358366929
  94. 18285668947362235082502949640657986308096143416968304675951743553132243626642071
  95. 97608459024263017473392225291248366316428006552870975051997504913009859468071013
  96. 60233644016440017918861085323076499171437205446782359721176046515320016308533631
  97. 93515896458906817223728123103202718979179512727996560536940321112428465909945563
  98. 80215461316106267521633805664394318881268199494005537068697621855231858921100963
  99. 44101293353573391845966819753983428469682288946007635203168892200202193131836975
  100. 75569620611157743058263055358620156378912460312206729339926173783796251509999354
  101. 03648731423208873977968908908369996292995391977217796533421249291978383751460062
  102. 05496734166283348734101109777053589806649813601139557158432830871394058253527405
  103. 60810115039079416880791972129331483030726386786314110384431282159949368243429981
  104. 88719768637604496342597524256886188688978980888315865076262604856465004322896856
  105. 14925506396881140440042950389424587238223354310107869151732833360477926272776568
  106. 60761777056168740502577437499837758301438561354272738385897741335269491654839297
  107. 21519554793578923866762502745370104660909382449626626935321303744538892479216161
  108. 18888970207791044856319951482663080287954954645358386630734442375331971227915886
  109. 17072896520901498483054359832007713266534072906620167757064096901837712013068232
  110. 45333477966660525325490873601961480378241566071271650383582257289215708209369510
  111. 99589013285949072430618332575520120809000717502202294974280182344541371191629844
  112. 99147222541965946822214682606449618392542496709031040075814888579716722463228870
  113. 16438403908463856731164308169537326790303114583680575021119639905615169154708510
  114. 45970054209857179731801556474140617233414584711126854792989244300139146828910367
  115. 91792169786165824890073220335913767065276765213071439853027609884780562169946596
  116. 55461379174985659739227379416726495377801992098355427866179123126699374730777730
  117. 56932443016683933301155451554265686493749212868704912175424596783113296924849246
  118. 67442619990339728256748734602011504422287804661243201830161082321839086547710423
  119. 98228531316559685688005226571474428823317539456543881928624432662503345388199590
  120. 08510521138312449186180262443219554043398572284134125440941177172215686708629174
  121. 21240531106205228429861992736294062088347548536451281232796090972139537753600230
  122. 76765694208219943034648783348544492713539450224591334374664937701655605763384697
  123. 06291872574542650587941463017663976045747431108155674709165270874812526715991379
  124. 32405273046136939611698925898083119063225107779285620719994594877006118010022961
  125. 32304588294558440952496611158342804908643860880796440557763691857743754025896855
  126. 92725251456340438521782589059955395462745138545445291676104296926797089358005623
  127. 45019185714890304184957674008193599732187119574963570959678251710962647520688908
  128. 06407651445893132870767454169607107931692704285168093413311046353506242209810363
  129. 21677191042078616218421376393819462569728678141363638962012397691046541895680619
  130. 73231484142245500716172158513213020306841760872158927020988791089380810459033972
  131. 76547326416916845445627600759561367103584575649094430692452532085003091068783157
  132. 56151984756756919128478465469255866511155791346127242533608363513134218390517715
  133. 45112284644551360160135132289485432715047608393075561009087860966638706122786902
  134. 74831819331606701484957163004705262228238406266818448788374548131994380387613830
  135. 12885988526420199228618820849958864088852135250145761539648264745102590253074317
  136. 29568996364996157075518558371659353671254485150893629045677366300355624573747791
  137. 00987992499146967224041481601289530944015488942613783140087804311431741858071826
  138. 18514905113874483135843906722894940825828602165028892722838742643278616869038196
  139. 05301558944594518087351972460082215293439808282541261282571572093509853828007385
  140. 60472910941184006084485235377833503306861977724501886364070344973366473100602018
  141. 12879288699186182441845396899477725948216913713364747045317297980924584436112961
  142. 89975956962409718455640205114325895918447249209429303016514887130798021023790655
  143. 36525154780298059407529440513145807551537794861635879901158192019808879694967187
  144. 44822415683646353432616024263293476163445816389016380512389418452397342184149688
  145. 92623984896486420934098166814947711551770095626690298501015135375998012725012419
  146. 71119871526593747484778935488777815192931171431167444773882941064615028751327709
  147. 47450476392287489066298984154025935083403514203513616881924823899802770666691634
  148. 21334243120545073593886166876911881857761181357713324839652098820859823912986063
  149. 86822804754362408956522921410859852037330544625953261340234864689275060526893755
  150. 14840329854208699122105259700562857670770256769530097897004640892000985210698029
  151. 54196998021380532957981594782899344432454915653278452238405512404452082264354206
  152. 56313310702940722371552770504263482073984454889589248861397657079145414427653584
  153. 57295132971909194769441191096679747426267559095383203916967349426136003226307742
  154. 86841050400613510521944137781580950057145268460098103521092490400279580507364369
  155. 61021241137739717164869525493114805040126568351268829598413983222676377804500626
  156. 50724173175739521979689075482519932925964980162706866565803017887740561516715973
  157. 19273204793762473755058550528396602945669925221736008740812120142090710419375985
  158. 71721431338017425141582491824710905084715977249417049320254165239323233258851588
  159. 89333709713631089257153141776197832603375010902628406641580137135935652927808845
  160. 63059517700814439941146742918503607488523666547448699280832305168157116029118363
  161. 74147958492100860528981469547750812338896943152861021202736747049903930417035171
  162. 34212692348670056662750622905863691188222890317051030540688209697087554532936943
  163. 40639812976964780318254516421783473477164710584232385945801830527562139101869976
  164. 04305844068665712346869679456044155742100039179758348979935882751881524675930878
  165. 92815924349219754538766830568466842077540982178124705335452319479739895332017598
  166. 86402810588255576980043971205383124594289573776960018574973352499650135093689259
  167. 58021863811725906506436882127156815751021712900765992750370228283963962915973251
  168. 17341858672102349731776596945428362551937155600914368032931196284254662840314244
  169. 43706484323903749064108113007928489557672434812000903098884572709077508736388732
  170. 99642555050473812528975962934822878917619920725138309388288292510416837622758204
  171. 08191893360365387528411678570372098971883298692192781662967584458017491180911966
  172. 30481874341550677908639488314892415043004767045279712834822115222028370628573142
  173. 44107823792513645086677566622804977211397140621664116324756784216612961477109018
  174. 82609467737768640617672148429389497667138012278894130902655351109611834701256519
  175. 75408070953840609168639369066737866272094294342642604029021583173450037274625889
  176. 92622049877121178405563348492490326003508569099382392777297498413565614830788262
  177. 36332236838070982234601227424137903647345173592521575475716093427093519290172395
  178. 49214264906911152715233381091240428121028937384881673589539345089306977155229891
  179. 99698903885883275409044300321986834003470271220020159699371690650330547577095398
  180. 74858067002449104550489006172718916803139452803616563394157133463722255047754746
  181. 07560550241087643821216888489169403712589019484906853797222445620094838194915327
  182. 24502276218589169507405794983759821006604481996519360110261576947176202571702048
  183. 68491461689406840414083358756211831921083800563214456201894150594578002531874747
  184. 19116048406779977654148306221790693308538751292989830095802775541454350587689849
  185. 44179136535891620098725222049055183554603706533183176716110738009786625247488691
  186. 47607766447014719307447630241166033567176556487444057799053199627163297200910944
  187. 92492164560306188277729477507647774464525863289191591074442523200829182095180210
  188. 83700353881330983215894608680127954224752071924134648334963915094813097541433244
  189. 20929993075148107791900234612812233016179942993061880053341455063393213933964686
  190. 16164169552202164479954172431711657444713641977332048993650747678441499295480730
  191. 25856442942381787641506492878361767978677158510784235702640213388018875601989234
  192. 05686842321558562850864552525837701062053222424498799062526348401077432248817255
  193. 86022333020763999338541520153438477254429178951306370503204449177977523708719582
  194. 77976799686113626532291118629631164685159934660693460557545956063155830033697634
  195. 00027668515129384363888609082837614115773200352756515874590656702543943793110483
  196. 85713132944906049265823631089495350900826731544972263966480886180415739778884728
  197. 92174618974189721700770009862449653759012727015227634510874906948012210684952063
  198. 00251901165596358055242918020558690425968526104741283451846673693858002770025296
  199. 53563667216198836724282269339503259303909945831686655422346548570208755046175205
  200. 21853721567282679903418135520602999895366470106557900532129541336924472492212436
  201. 32452304289518846177912233806967423398069488727058750338922839509513520912310925
  202. 81590069603951563677360671090505662996035718764232479207528361608055976977787564
  203. 76767210521222327184821484446631261487584226092608875764331731023263768864822594
  204. 69121103236773755812213347055680595800831012748167396201958359802396741448986727
  205. 68458698193767837571679367232130815861910459950589709910646869194634480385741438
  206. 29629547131372173669836184558144505748676124322451519943362182916191468026091121
  207. 79300186478805006135160314435007618921344160248809174105123229035717920549792797
  208. 09245024799408426961588184426161637800447594782122408732041244211691998055726491
  209. 18243661921835714762891425805771871743688000324113008704819373962295017143090098
  210. 47692723749887593863994253059533160789161881086350598244457894279934651491595288
  211. 48697574880258233535716778648268280511408854297327881977657369660057277001625924
  212. 04301688659946862983717270595809808730901820120931003430058796552694788049809205
  213. 48430546761103465474806729067439976361259243463771999584386281239198547020241488
  214. 00768808188480878923915913694632931132768493297772016466417275872591223547844808
  215. 13433328050087758855264686119576962172239308693795757165821852416204341972383989
  216. 93273480342926234072233815510220910126294924974242327169884202329730326016179057
  217. 56731112354658902982983131151236076067739689981538122869996420146098525797936912
  218. 46016346088762321286205634215901479188632194659637483482564291616278532948239313
  219. 22944023104327728876813955021334826638868745325928158785450389099156194963247885
  220. 50350902893909737189880039990261320158726786378730956781096253110080544894188579
  221. 83565902063680699643165033912029944327726770869305240718416592070096139286401966
  222. 72575008701221814973313369580960036975176495135004028592624920339811101495322753
  223. 36218445007443315624345324842179861083462613458975912348399707518542232816771872
  224. 15956827243245910829019886390369784542622566912542747056097567984857136623679023
  225. 87847816120147798293908051315025817452377352951016529693456278612224115078358775
  226. 53733483727644398380820006672147400344663227769189369676128789834889420946881023
  227. 08427036452854504966759697318836044496702853190637396916357980928865719935397723
  228. 49548678718041640141528148944378503629107151780528585758398771114547424015641647
  229. 71941163913549354667555935926088492005463846854030280809364172505836533680934072
  230. 25310820844723570226809826951426162451204040711501448747856199922814664565893938
  231. 48802864382231384985232845236066704580511367966375103924816333617327454727577563
  232. 68109773445392758275605974251607054686896577945305216023159398657809748015154149
  233. 87097778078705357058008472376892422189750312758527140173117621279898744958406199
  234. 84391336568029772120875193498850449971391428515803232482302134063031258607262454
  235. 16377652345055220510863182853596585207081733927095664450114040551065790550374177
  236. 80393351658360904543047721422281816832539613634982525215232257690920254216409657
  237. 45261806605177790159290288424059999888275369195754011695469615227040128085757976
  238. 61547221929256559639918209488946426575122887663303021337463674492174493516371047
  239. 25732980832812726468187759356584218383594702792013663907689741738962252575782663
  240. 99080979264701140758036785059938188718456009469583327077512618128201539104177395
  241. 09182441375619999378192403624695582359241714787027794484431087519018074141102903
  242. 70706052085162975798361754251041642244867577350756338018895379263183389855955956
  243. 52785722792615552449473936366553390452865621546428834316228292112329045184221253
  244. 28881014158840616199391950422300598983499665694635801868167170748188232158486477
  245. 34386780911564660755175385552224428524049468033692299989300783900020690121517740
  246. 69642857393019691050098827852305379763794025796895329511243616677891058555721338
  247. 17890899454539479159273749586002682378444868720372434888346168562900978505324970
  248. 36933361942439802882364323553808208003875741710969289725499878566253048867033095
  249. 15051845212694498925159639207942145260650851605232561486193828248983800081508535
  250. 15646427617008320964831179444019717801492133453359033366723767192297220699707660
  251. 55482452247416927774637522135201716231722137632445699154022395494158227418930589
  252. 91174693177377651873585003231801443288391637424379585469569122177409894861151556
  253. 40466095650945381155209218637115186845625432750478705300069984231401801694211091
  254. 05925493596116719457630962328831271268328501760321771680400249657674186927113215
  255. 57327004993570994232441638708924242758440765121557267603792476534180898431267694
  256. 11103131659514294793776706988812496434219332874043904855382221608370889075982773
  257. 90184204138197811025854537088586701450623578513960109987476052535450100439353062
  258. 07243970997644514679099338144899464460978095773195360493873495002686056455569322
  259. 42296918156302939224876064708734311663842054424896287602136502469918930401125131
  260. 03835085621908060270866604873585849001704200923929789193938125116798421788115209
  261. 25913043557232163566089560351438388393901895316627435560997001569978028923636234
  262. 9895374653428746875
  263. 100000项的长度:20899
  264. --------------------------------
  265. Process exited after 43.28 seconds with return value 0
  266. 请按任意键继续. . .

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

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <sstream>
  6. #include <fstream>
  7. using namespace std;
  8. string strAdd(string a, string b)
  9. {
  10. unsigned short j=0,k=0;
  11. string c;
  12. size_t n = b.size();
  13. if (a.size()<n) a='0'+a;
  14. for (size_t i=n;i>0;i--){
  15. k=(a[i-1]-'0')+(b[i-1]-'0')+j;
  16. if (k>9){
  17. c+=(k-10)+'0';
  18. j=1;
  19. }
  20. else{
  21. c+=k+'0';
  22. j=0;
  23. }
  24. }
  25. reverse(c.begin(),c.end());
  26. if (j==1) c='1'+c;
  27. return c;
  28. }
  29. string fib1(long n) //定义递推法
  30. {
  31. string a = '1';
  32. string b = '1';
  33. string c;
  34. for (auto i=3; i<=n; ++i){
  35. c = strAdd(a,b);
  36. a = b;
  37. b = c;
  38. }
  39. return c;
  40. }
  41. string fib2(long n) //递归法太耗时间
  42. {
  43. string c;
  44. if (n <= 2)
  45. c = '1';
  46. else
  47. c = strAdd(fib2(n-1), fib2(n-2));
  48. return c;
  49. }
  50. string fib3(long n) //用容器时间差不多,太耗内存空间
  51. {
  52. string c;
  53. vector<string>arr;
  54. arr.push_back('1');
  55. arr.push_back('1');
  56. for (int i = 2; i < n; i++)
  57. arr.push_back(strAdd(arr.at(i-2),arr.at(i-1)));
  58. return arr.back();
  59. }
  60. int main(void)
  61. {
  62. string c;
  63. stringstream s;
  64. int i=100000;
  65. c = fib1(i);
  66. s << c << endl << endl << '第' << i
  67. <<'项的长度:'<< c.size() << endl;
  68. cout << s.str();
  69. ofstream out_file('Fibonacci.txt');
  70. if (out_file){
  71. out_file << s.str();
  72. out_file.close();
  73. }
  74. return 0;
  75. }

再用上述代码计算出第100001项,然后把两项的值替换掉string a,b的初始值“1”,最后耗时133秒,计算得到数列第20万项的值:

  1. 1508568355798893899263687894817313444184841656165868974021430081400787583936394812351619099573209347
  2. 1171781051796266302937774866189506849346804997282989249330595609531388039656501674951902073416282675
  3. 6867545612008745257856504784958722654132733678007112355970827359478161833369482766422435366232436736
  4. 8765313770978639661659359613120993580646300798217138405565931635846450773386124385241345993441744392
  5. 6921039675036360272864675639374407908082412318246291986517133289505130691422859640541931718590209286
  6. 4657505644409580586985935014523432239364338088655492633909256243409937019018753645668544126349769853
  7. 6331091496661102820839146477082237137545109143876337141802589434129485563112104064222852676691941806
  8. 9072433195848445930784362588088491909572194728708365539666263098137255830767958717493568606834420525
  9. 3208461634110429083194983843184527937104990436134713980142091989825375399040246389540803668684805681
  10. 9034643125463964320496174521308753631883969528360171544667360666666511788652493139976527620833746328
  11. 8537773131251108750756205096068672482133243054818126655239593578836887709032159318387668321645414703
  12. 3023746122154093794982052151698045687273205557091125530628911396555723027029436962873702608592396417
  13. 7412734450829524210770560635045961741215694709873642782745658717701317758148293110721581393158365556
  14. 2846111188339452737408562216970417356954474367646357836770047579714349363918537229775630512391906292
  15. 1992572456841770553982543845613393612400590320047716831102369797422740950912120878865732398898031024
  16. 4294835226452063441793521138634806889871743927164147084606451880582629116741730263796074632026047730
  17. 3289023345521932215347151804409026447421183429858973401256005212609284636977483396468020797603532714
  18. 7203207960677350302533100100040188921911087448390329131010268832448900183911343227547774280391774027
  19. 5723502404453113290999855514871952975811069439150997067076682513409146213552200823143843831196386561
  20. 4327695985652085123960764363853506121004650277976974669012431467655262543108545665271997195753751331
  21. 9830060230650333905587150714880561804234808490008791223754722535962792124101197982611601551453915132
  22. 3325665372889977440272456233864042374727546419630470211504765023392057752128954432243507319981091035
  23. ... ... ... 略 ... ... ...
  24. 61926126352359630329214201957704677119789193142654798777312450935031089429802652246259408175853125
  25. 200000项的长度:41798
  26. --------------------------------
  27. Process exited after 133.9 seconds with return value 0
  28. 请按任意键继续. . .

代码如下: 

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <sstream>
  5. #include <fstream>
  6. using namespace std;
  7. string strAdd(string a, string b)
  8. {
  9. unsigned short j=0,k=0;
  10. string c;
  11. size_t n = b.size();
  12. if (a.size()<n) a='0'+a;
  13. for (size_t i=n;i>0;i--){
  14. k=(a[i-1]-'0')+(b[i-1]-'0')+j;
  15. if (k>9){
  16. c+=(k-10)+'0';
  17. j=1;
  18. }
  19. else{
  20. c+=k+'0';
  21. j=0;
  22. }
  23. }
  24. reverse(c.begin(),c.end());
  25. if (j==1) c='1'+c;
  26. return c;
  27. }
  28. string fib100k(long n)
  29. {
  30. string a = '\
  31. 25974069347221724166155034021275915414880485386517696584724770703952534543511273\
  32. 68626555677283671674475463758722307443211163839947387509103096569738218830449305\
  33. 22876385313349213530267927895670105127657827163560807305053220024323311438398651\
  34. 61378272381247774537783372999162146340500546698603908627509966393664092118901252\
  35. 71960172105060300350586894028558103675117658251368377438684936413457338834365158\
  36. 77542537191241050033219599133006220436303521375652542182399869084855637408017925\
  37. 17616293917549634585586163007628199160811098365263529954406942842065710460449038\
  38. 05647136346033000520852277707554446794723709030979019014860432846819857961015951\
  39. 00185060826491923458731339915013391993236310230186417253647713626647508013398243\
  40. 12317034314529641817900511879573167668349799016820118499077566864568450662873924\
  41. 85603914047605199550066288826345877189410680370091879365001733011710028310473947\
  42. 45625609144493282137485557386408057981302826664027035429441210491999580313187680\
  43. 58991865134251759599115205631553377039969410355182752749199598022575079020377981\
  44. 03089922984996304496255814045517000250299764322193462165366210841876745428298261\
  45. 39823447836658158804081900330738293950008213200937471548513102722081730543226486\
  46. 69496309879147143629255542526240439996153269798768075106468190687921182991679644\
  47. 09178271868561702918102212679267401362650499784968843680975254700131004574186406\
  48. 44829948587255174474669565187912691699324456481767332225714931496776334584662383\
  49. 03338202397024368594782876418757885729107101337003000942293335972927791914092128\
  50. 04901545976262791057055248158884051779418192905216769576608748815567860128818354\
  51. 35429230739781015478570132843861272862017665395344499300198006295389369855007232\
  52. 86651317181135886613537472684585432548981137176605194616937916884425342594781263\
  53. 10388952047956594380715301911253964847112638900713362856910155145342332944128435\
  54. 72209962867461194209516610023097407099655319005081586699114454426478828726428450\
  55. 17253320486483194578920399848938236367456182203750973485668474338872490493370316\
  56. 33826571760729778891798913667325190623247118037280173921572390822769228077292456\
  57. 66275053833750069260772105936194212689203025674435653780083183063759333450235025\
  58. 69729065152853271943677560156660399164048825639676930792905029514886934137991251\
  59. 74856667074717514938979038653338139534684837808612673755438382110844897653836848\
  60. 31825883633991731045585090566384620250146313118310874290772926221594302042915947\
  61. 40306101839816855066950261973761508571761199475875722129872053120607918649803615\
  62. 96092339594104118635168854883911918517906151156275293615849000872150192226511785\
  63. 31508925102752804515123860379218469212153382928713692432152733271415747882959026\
  64. 01571954853164447945467502858402360002383447905203451080332820138038807089807348\
  65. 32620122795263360677366987578332625485944906021917368867786241120562109836985019\
  66. 72901771578011204045864915393511578349954610063663574544850824188827906753135995\
  67. 05192062229760153765297973085881648731173082370598284894044874039320535929359764\
  68. 54165560795472477862029969232956138971989467942218727360512336559521133108778758\
  69. 22887959758032045960847902450638519417431261637751045992110248687949634170686209\
  70. 29088930685252348056925998333775103901013166178123051145719327066291671254465121\
  71. 51746802548190358351688971707570677865618800822034683632101813026232996027599403\
  72. 57999777404624495211453158837035790448329315000724617341735580556783215345434117\
  73. 00202585608091662941986374015145695722728369219632295111877625307534025947814482\
  74. 04657460288485500062806934811398276016855584079542162057543557291510641537592939\
  75. 02288435612079264370556006236798654438246437394697247194599655579550583803482559\
  76. 78396827760847315302517889517186307227611036305093600742622617173630586132915440\
  77. 24695432904616258691774630578507674937487992329181750163484068813465534370997589\
  78. 35360740517290941269765759329515681862474712763646883655175701835341727466260730\
  79. 65104511957628663499228486787805910851189856535554349587616640164475880286336297\
  80. 04046289097067736256584300235314749461233912068632146637087844699210427541569410\
  81. 91224656857120471724113337848981676409692498163342117685715031167104006817530319\
  82. 21154156119580425706586931272762137106974722260296555246110537155545324997508432\
  83. 75200199214301910505362996007042963297805103066650638786268157658772683745128976\
  84. 85079636637105938091122542883583919412115477375998130192165095214013330607098731\
  85. 37329265181692268450634439540567298120315463923249817937804691037934221694952291\
  86. 00793029949237507299325063050942813902793084134473061411643355614764093104425918\
  87. 48136393054236937897652052645634764831827263337151211203062923388928648794920973\
  88. 78478618848682608046473195392008403983080088038690495574197562192939221108257663\
  89. 97681361044490024720948340326796768837621396744075713887292863079821849314343879\
  90. 77808873795889684094614341592713175783651145782893558185990292353438888884658745\
  91. 21308381377794436361197628390368945957601203165022798579015453447473527069728514\
  92. 54599861422902737291131463782045516225447535356773622793648545035710208644541208\
  93. 98423503890877022303984938021473480968743333622544915011741175157070456105089527\
  94. 40002063804979679604026178186644812485472696308234733772455433905198413087697812\
  95. 76565916764229022948181763075710255793365008152286383634493138089971785087070863\
  96. 63220586901893837776606300606675773242727292924742129526500070664672273000995612\
  97. 41914091389846752249557907293984956087504566942177715511073466304566039441362358\
  98. 88443676215273928597072287937355966723924613827468703217858459948257514745406436\
  99. 46099705931612059684156047323439665245723165031779283386059038836041769142873273\
  100. 57039868033426046700717173635730911229813069032861371225979370966057751729645282\
  101. 63757434075792282180744352908669606854021718597891166333863858589736209114248432\
  102. 17864503947919542420819162608857106911043399480147301310086984886643072121676247\
  103. 31196181907378207665829682807960794822595490363282665780069948568253005364366748\
  104. 22534603705134503603152154296943991866236857638062351209884448741138600171173647\
  105. 63212602996140856192559970756682786677873237741944446227539990929104469771647615\
  106. 11186723272386792081333673061819448493966071233452718565202536436219641987827529\
  107. 78813060080313141817069314468221189275784978281094367751540710106350553798003842\
  108. 21904550848223938699329692665922111274269813306230007346562849809363669304944680\
  109. 16285537126334126203784919194986000972008367278766507868863069334189952257683143\
  110. 90832484886340318940194161036979843833346608676709431643653538430912157815543512\
  111. 85207772085809890209958644960247949197068723076568710923438071950982481447315781\
  112. 37800806393584187566550985013218828528401849814076907385073695353777118803885289\
  113. 35347600930338598691608289335421147722936561907276264603726027239320991187820407\
  114. 06741227225812076672904007192423793033097213236418409395610299597129179982829000\
  115. 95391473824378027790511120309545825328887211461701334403859396540478061993332245\
  116. 47317803407340902512130217279595753863158148810392952475410943880555098382627633\
  117. 12760671812617102201135618180077540022751673414416921642497317562136312858828197\
  118. 80057888324545345815224349372681334339977105125320814783450671398350383329013139\
  119. 45986481820272322043341930929011907832896569222878337497354301561722829115627329\
  120. 46881485328192210075237362682764315268573549322302801810144964900901552924863833\
  121. 88856648930022509743436012008143651536253691994467097111269519667257800618912154\
  122. 40222487564601554632812091945824653557432047644212650790655208208337976071465127\
  123. 50832048716527157747232588727576112835759213255393444628943325810502863358366929\
  124. 18285668947362235082502949640657986308096143416968304675951743553132243626642071\
  125. 97608459024263017473392225291248366316428006552870975051997504913009859468071013\
  126. 60233644016440017918861085323076499171437205446782359721176046515320016308533631\
  127. 93515896458906817223728123103202718979179512727996560536940321112428465909945563\
  128. 80215461316106267521633805664394318881268199494005537068697621855231858921100963\
  129. 44101293353573391845966819753983428469682288946007635203168892200202193131836975\
  130. 75569620611157743058263055358620156378912460312206729339926173783796251509999354\
  131. 03648731423208873977968908908369996292995391977217796533421249291978383751460062\
  132. 05496734166283348734101109777053589806649813601139557158432830871394058253527405\
  133. 60810115039079416880791972129331483030726386786314110384431282159949368243429981\
  134. 88719768637604496342597524256886188688978980888315865076262604856465004322896856\
  135. 14925506396881140440042950389424587238223354310107869151732833360477926272776568\
  136. 60761777056168740502577437499837758301438561354272738385897741335269491654839297\
  137. 21519554793578923866762502745370104660909382449626626935321303744538892479216161\
  138. 18888970207791044856319951482663080287954954645358386630734442375331971227915886\
  139. 17072896520901498483054359832007713266534072906620167757064096901837712013068232\
  140. 45333477966660525325490873601961480378241566071271650383582257289215708209369510\
  141. 99589013285949072430618332575520120809000717502202294974280182344541371191629844\
  142. 99147222541965946822214682606449618392542496709031040075814888579716722463228870\
  143. 16438403908463856731164308169537326790303114583680575021119639905615169154708510\
  144. 45970054209857179731801556474140617233414584711126854792989244300139146828910367\
  145. 91792169786165824890073220335913767065276765213071439853027609884780562169946596\
  146. 55461379174985659739227379416726495377801992098355427866179123126699374730777730\
  147. 56932443016683933301155451554265686493749212868704912175424596783113296924849246\
  148. 67442619990339728256748734602011504422287804661243201830161082321839086547710423\
  149. 98228531316559685688005226571474428823317539456543881928624432662503345388199590\
  150. 08510521138312449186180262443219554043398572284134125440941177172215686708629174\
  151. 21240531106205228429861992736294062088347548536451281232796090972139537753600230\
  152. 76765694208219943034648783348544492713539450224591334374664937701655605763384697\
  153. 06291872574542650587941463017663976045747431108155674709165270874812526715991379\
  154. 32405273046136939611698925898083119063225107779285620719994594877006118010022961\
  155. 32304588294558440952496611158342804908643860880796440557763691857743754025896855\
  156. 92725251456340438521782589059955395462745138545445291676104296926797089358005623\
  157. 45019185714890304184957674008193599732187119574963570959678251710962647520688908\
  158. 06407651445893132870767454169607107931692704285168093413311046353506242209810363\
  159. 21677191042078616218421376393819462569728678141363638962012397691046541895680619\
  160. 73231484142245500716172158513213020306841760872158927020988791089380810459033972\
  161. 76547326416916845445627600759561367103584575649094430692452532085003091068783157\
  162. 56151984756756919128478465469255866511155791346127242533608363513134218390517715\
  163. 45112284644551360160135132289485432715047608393075561009087860966638706122786902\
  164. 74831819331606701484957163004705262228238406266818448788374548131994380387613830\
  165. 12885988526420199228618820849958864088852135250145761539648264745102590253074317\
  166. 29568996364996157075518558371659353671254485150893629045677366300355624573747791\
  167. 00987992499146967224041481601289530944015488942613783140087804311431741858071826\
  168. 18514905113874483135843906722894940825828602165028892722838742643278616869038196\
  169. 05301558944594518087351972460082215293439808282541261282571572093509853828007385\
  170. 60472910941184006084485235377833503306861977724501886364070344973366473100602018\
  171. 12879288699186182441845396899477725948216913713364747045317297980924584436112961\
  172. 89975956962409718455640205114325895918447249209429303016514887130798021023790655\
  173. 36525154780298059407529440513145807551537794861635879901158192019808879694967187\
  174. 44822415683646353432616024263293476163445816389016380512389418452397342184149688\
  175. 92623984896486420934098166814947711551770095626690298501015135375998012725012419\
  176. 71119871526593747484778935488777815192931171431167444773882941064615028751327709\
  177. 47450476392287489066298984154025935083403514203513616881924823899802770666691634\
  178. 21334243120545073593886166876911881857761181357713324839652098820859823912986063\
  179. 86822804754362408956522921410859852037330544625953261340234864689275060526893755\
  180. 14840329854208699122105259700562857670770256769530097897004640892000985210698029\
  181. 54196998021380532957981594782899344432454915653278452238405512404452082264354206\
  182. 56313310702940722371552770504263482073984454889589248861397657079145414427653584\
  183. 57295132971909194769441191096679747426267559095383203916967349426136003226307742\
  184. 86841050400613510521944137781580950057145268460098103521092490400279580507364369\
  185. 61021241137739717164869525493114805040126568351268829598413983222676377804500626\
  186. 50724173175739521979689075482519932925964980162706866565803017887740561516715973\
  187. 19273204793762473755058550528396602945669925221736008740812120142090710419375985\
  188. 71721431338017425141582491824710905084715977249417049320254165239323233258851588\
  189. 89333709713631089257153141776197832603375010902628406641580137135935652927808845\
  190. 63059517700814439941146742918503607488523666547448699280832305168157116029118363\
  191. 74147958492100860528981469547750812338896943152861021202736747049903930417035171\
  192. 34212692348670056662750622905863691188222890317051030540688209697087554532936943\
  193. 40639812976964780318254516421783473477164710584232385945801830527562139101869976\
  194. 04305844068665712346869679456044155742100039179758348979935882751881524675930878\
  195. 92815924349219754538766830568466842077540982178124705335452319479739895332017598\
  196. 86402810588255576980043971205383124594289573776960018574973352499650135093689259\
  197. 58021863811725906506436882127156815751021712900765992750370228283963962915973251\
  198. 17341858672102349731776596945428362551937155600914368032931196284254662840314244\
  199. 43706484323903749064108113007928489557672434812000903098884572709077508736388732\
  200. 99642555050473812528975962934822878917619920725138309388288292510416837622758204\
  201. 08191893360365387528411678570372098971883298692192781662967584458017491180911966\
  202. 30481874341550677908639488314892415043004767045279712834822115222028370628573142\
  203. 44107823792513645086677566622804977211397140621664116324756784216612961477109018\
  204. 82609467737768640617672148429389497667138012278894130902655351109611834701256519\
  205. 75408070953840609168639369066737866272094294342642604029021583173450037274625889\
  206. 92622049877121178405563348492490326003508569099382392777297498413565614830788262\
  207. 36332236838070982234601227424137903647345173592521575475716093427093519290172395\
  208. 49214264906911152715233381091240428121028937384881673589539345089306977155229891\
  209. 99698903885883275409044300321986834003470271220020159699371690650330547577095398\
  210. 74858067002449104550489006172718916803139452803616563394157133463722255047754746\
  211. 07560550241087643821216888489169403712589019484906853797222445620094838194915327\
  212. 24502276218589169507405794983759821006604481996519360110261576947176202571702048\
  213. 68491461689406840414083358756211831921083800563214456201894150594578002531874747\
  214. 19116048406779977654148306221790693308538751292989830095802775541454350587689849\
  215. 44179136535891620098725222049055183554603706533183176716110738009786625247488691\
  216. 47607766447014719307447630241166033567176556487444057799053199627163297200910944\
  217. 92492164560306188277729477507647774464525863289191591074442523200829182095180210\
  218. 83700353881330983215894608680127954224752071924134648334963915094813097541433244\
  219. 20929993075148107791900234612812233016179942993061880053341455063393213933964686\
  220. 16164169552202164479954172431711657444713641977332048993650747678441499295480730\
  221. 25856442942381787641506492878361767978677158510784235702640213388018875601989234\
  222. 05686842321558562850864552525837701062053222424498799062526348401077432248817255\
  223. 86022333020763999338541520153438477254429178951306370503204449177977523708719582\
  224. 77976799686113626532291118629631164685159934660693460557545956063155830033697634\
  225. 00027668515129384363888609082837614115773200352756515874590656702543943793110483\
  226. 85713132944906049265823631089495350900826731544972263966480886180415739778884728\
  227. 92174618974189721700770009862449653759012727015227634510874906948012210684952063\
  228. 00251901165596358055242918020558690425968526104741283451846673693858002770025296\
  229. 53563667216198836724282269339503259303909945831686655422346548570208755046175205\
  230. 21853721567282679903418135520602999895366470106557900532129541336924472492212436\
  231. 32452304289518846177912233806967423398069488727058750338922839509513520912310925\
  232. 81590069603951563677360671090505662996035718764232479207528361608055976977787564\
  233. 76767210521222327184821484446631261487584226092608875764331731023263768864822594\
  234. 69121103236773755812213347055680595800831012748167396201958359802396741448986727\
  235. 68458698193767837571679367232130815861910459950589709910646869194634480385741438\
  236. 29629547131372173669836184558144505748676124322451519943362182916191468026091121\
  237. 79300186478805006135160314435007618921344160248809174105123229035717920549792797\
  238. 09245024799408426961588184426161637800447594782122408732041244211691998055726491\
  239. 18243661921835714762891425805771871743688000324113008704819373962295017143090098\
  240. 47692723749887593863994253059533160789161881086350598244457894279934651491595288\
  241. 48697574880258233535716778648268280511408854297327881977657369660057277001625924\
  242. 04301688659946862983717270595809808730901820120931003430058796552694788049809205\
  243. 48430546761103465474806729067439976361259243463771999584386281239198547020241488\
  244. 00768808188480878923915913694632931132768493297772016466417275872591223547844808\
  245. 13433328050087758855264686119576962172239308693795757165821852416204341972383989\
  246. 93273480342926234072233815510220910126294924974242327169884202329730326016179057\
  247. 56731112354658902982983131151236076067739689981538122869996420146098525797936912\
  248. 46016346088762321286205634215901479188632194659637483482564291616278532948239313\
  249. 22944023104327728876813955021334826638868745325928158785450389099156194963247885\
  250. 50350902893909737189880039990261320158726786378730956781096253110080544894188579\
  251. 83565902063680699643165033912029944327726770869305240718416592070096139286401966\
  252. 72575008701221814973313369580960036975176495135004028592624920339811101495322753\
  253. 36218445007443315624345324842179861083462613458975912348399707518542232816771872\
  254. 15956827243245910829019886390369784542622566912542747056097567984857136623679023\
  255. 87847816120147798293908051315025817452377352951016529693456278612224115078358775\
  256. 53733483727644398380820006672147400344663227769189369676128789834889420946881023\
  257. 08427036452854504966759697318836044496702853190637396916357980928865719935397723\
  258. 49548678718041640141528148944378503629107151780528585758398771114547424015641647\
  259. 71941163913549354667555935926088492005463846854030280809364172505836533680934072\
  260. 25310820844723570226809826951426162451204040711501448747856199922814664565893938\
  261. 48802864382231384985232845236066704580511367966375103924816333617327454727577563\
  262. 68109773445392758275605974251607054686896577945305216023159398657809748015154149\
  263. 87097778078705357058008472376892422189750312758527140173117621279898744958406199\
  264. 84391336568029772120875193498850449971391428515803232482302134063031258607262454\
  265. 16377652345055220510863182853596585207081733927095664450114040551065790550374177\
  266. 80393351658360904543047721422281816832539613634982525215232257690920254216409657\
  267. 45261806605177790159290288424059999888275369195754011695469615227040128085757976\
  268. 61547221929256559639918209488946426575122887663303021337463674492174493516371047\
  269. 25732980832812726468187759356584218383594702792013663907689741738962252575782663\
  270. 99080979264701140758036785059938188718456009469583327077512618128201539104177395\
  271. 09182441375619999378192403624695582359241714787027794484431087519018074141102903\
  272. 70706052085162975798361754251041642244867577350756338018895379263183389855955956\
  273. 52785722792615552449473936366553390452865621546428834316228292112329045184221253\
  274. 28881014158840616199391950422300598983499665694635801868167170748188232158486477\
  275. 34386780911564660755175385552224428524049468033692299989300783900020690121517740\
  276. 69642857393019691050098827852305379763794025796895329511243616677891058555721338\
  277. 17890899454539479159273749586002682378444868720372434888346168562900978505324970\
  278. 36933361942439802882364323553808208003875741710969289725499878566253048867033095\
  279. 15051845212694498925159639207942145260650851605232561486193828248983800081508535\
  280. 15646427617008320964831179444019717801492133453359033366723767192297220699707660\
  281. 55482452247416927774637522135201716231722137632445699154022395494158227418930589\
  282. 91174693177377651873585003231801443288391637424379585469569122177409894861151556\
  283. 40466095650945381155209218637115186845625432750478705300069984231401801694211091\
  284. 05925493596116719457630962328831271268328501760321771680400249657674186927113215\
  285. 57327004993570994232441638708924242758440765121557267603792476534180898431267694\
  286. 11103131659514294793776706988812496434219332874043904855382221608370889075982773\
  287. 90184204138197811025854537088586701450623578513960109987476052535450100439353062\
  288. 07243970997644514679099338144899464460978095773195360493873495002686056455569322\
  289. 42296918156302939224876064708734311663842054424896287602136502469918930401125131\
  290. 03835085621908060270866604873585849001704200923929789193938125116798421788115209\
  291. 25913043557232163566089560351438388393901895316627435560997001569978028923636234\
  292. 9895374653428746875';
  293. string b = '\
  294. 42026927029951543863190051012939151317739157026322345033047160871983357314572762\
  295. 26633938477267013660962533661702858329186641162298822215333733574147268614522205\
  296. 17796036021657629209679553065650253799831449502633050062071908889898464361959992\
  297. 64762361083185050237498647038594910246866212417306827361157235516477242575475023\
  298. 52412468746074851053353923438703547870019701586274514903943581778012410826464461\
  299. 82327292482674936228295400423592366266785816674032376953223354081043426666167973\
  300. 88659593046520172457610944955660711670543016908957146048840136794913945664938446\
  301. 46298912078940644595782507997928878739392985610180101343882600283820398139200927\
  302. 16351212296992483983946353362236959988059362454831495591998273144066460686038967\
  303. 47678466307142387985200612209483601958428286948941149568879944075331886216247060\
  304. 43127847588617179645038305434988777154546903665027721615391983839969917881343981\
  305. 41944368809250111481819798402261166104607318032292355376603758649849997454020469\
  306. 37917930479632224861390601474136372303392534432566084857015647848910533979262896\
  307. 64177821919706286664135844377802876352562122389353466102826235289263234488363199\
  308. 40415928656082972859882120514749356839216074406481815370670988971910860608364879\
  309. 55340049728172954655841960826021563040719014933250487378970396127053999994584598\
  310. 84586324576356850465902800682163360223018811383011208727253121314804106183630746\
  311. 33391723478815558419942200436973479456746429373159029901632147691027604795314573\
  312. 71335306209333700132749628766660240923781444622479118612427736288472117262538601\
  313. 03658427961076487163331347200528488644744897867222184279861410512996912357518380\
  314. 42022652299635148999201592961336958599228492147284059675182485820608337037517587\
  315. 06963474517424844808950896189553107994754733303323880745512298961051117039180748\
  316. 19309463129676526583523254006198015481044159254418528609134434118408385912583154\
  317. 97972011173508254288351994205020708970629131932370593611869970876740521536649684\
  318. 57182466406036383021770532848514425324974546309994975775831045210121951158146067\
  319. 85903295807850171689359081326188293931649613908497264994236206250488864434829436\
  320. 29519523285183855092352888948498775138102232008825516003364164591409282318882848\
  321. 54537807547517930489076000255121414706370664025018725479522771414250506214317261\
  322. 33512376491993264368219026824677798278050012296677681338164667973991346578705512\
  323. 74534394694404597077719187995407395427605915813079285212741656832828295621599317\
  324. 46905895821846222133111237435283709695276973766592642097014304602626280895117497\
  325. 84920754475292453555824485037081169662961361437456685569229108353804447871639780\
  326. 20232084023609370922254140477009691282049160576777366973036653649883492364824728\
  327. 35676387541329435959180975529726337169707457248356090428023225272687222700646793\
  328. 84555006784008088065427716480324882491803961614497071569285030997191355977454006\
  329. 78466656398246586364144439671724823401802624396178170648336037171760595399177104\
  330. 54961305646287727491308779554338932431913693952814138123950135908078982276584882\
  331. 63250802618524850762756185439484575939335126157545942937679620715509540065149312\
  332. 86556444370865543977167354218105455845369761896615555180417133010674271473743311\
  333. 86161116668001347423577154956442088220552625312076302475402749012976651613308330\
  334. 84658587180009012735858860387323290477368590430709381480698925172403629520614399\
  335. 57593715175787053504534026486718715408551576929967042586501209349749945808407148\
  336. 38200915888065735389239137040243506196571510983480529860982551109754928853361155\
  337. 45257393042442696791158576341900753200960006019671663122779964553274124613827002\
  338. 84220765144312721590741133408003489040762584919284658858041286916386515479642977\
  339. 63251242652433570903732799940906080289143242002162784031375696887933193271792815\
  340. 13651857484816495100553151506872893457040698364864908926339042055054701374510871\
  341. 32493449799940863749770127971602810605646534257761336751184475785823961876512808\
  342. 94724868512789750831935081098377719941036701024841296638857887680535961230332515\
  343. 79123980971589651437698106274532939294318318049638382537268302829198532880152940\
  344. 71433723208632110406164435835438266486491721843821029351742455374550575809075335\
  345. 58820252056024537843175435538531994250810021714312797654628419286910387394477602\
  346. 77789370517385306279744047722489086714748028855582994177874607142469064610509456\
  347. 25202212825832995025564260229990592904684159579116792151285886032829684995127155\
  348. 34465088782963276118039067356332662241230936875737466342521351706796949812896179\
  349. 44100773168818654945023743438512318640838968116604957523873700674044602618648483\
  350. 42534348017257039340592723838919220589031998906185198421038308216416528610206873\
  351. 86947447622822706715620808975672807761093212837007765365923625213701756104920104\
  352. 90647926435022313362357037672820456385127428485063107497131400081807697966418670\
  353. 92086270751758290904938302420460333404925465658358444295296337088776545265587606\
  354. 60624469378326102878234267050061871258419093201617639875665134869271540100850836\
  355. 47269535513915816758710288791204561224527095476616464634423436358506846144301437\
  356. 37965771779082950287449625309471674027094862405581741465010467062797651780375495\
  357. 58990882669374665017899340941580175877931297764268912428095816679869262328136255\
  358. 76760050205090619888399123409239688442164270550778132287725184933490420599495679\
  359. 26460565911025776082501419307787196588096224965245820155681523746669946396754909\
  360. 27159042795674347394047138884034570033397714655556949471950710357752508118665325\
  361. 75065892797554153301608090613307672021657715401873436452152566925919864525536834\
  362. 56823553070598162130085504904574946212500558610031219155224527412244517230546007\
  363. 64895687440378116371204889424814424573838812216469939212301308229376562195148119\
  364. 87478059283006119165854697271444230766548407257874820601218362249866393721509747\
  365. 52653753967735395851984476957732214244609798081017294862506075465564785057434857\
  366. 46737609236566345826554956945008049466256006830033039697919727289785487728986917\
  367. 00233344838111143624421997248348373393817914540838366741137930672543630607318584\
  368. 21388931047329746129464330913406615122087253374620231774863799904011403703504128\
  369. 61126902647363933972738179243157455031071860290464651684896649914849558362752102\
  370. 78398095989067353453771747035442365355445747127447923214040603969451728451202645\
  371. 05187739366087820740427979492937157133826232579378916797946108593141509568348629\
  372. 61624018757558941301204073786717124377291884875201219129108103267491540960406487\
  373. 54248927534521962074102425291913766944369032132103550933382245399558387757904745\
  374. 51175896508802785493729953647184656663763691900135139867974638850946840528454914\
  375. 07564794860564579206494296178297419619461097036293045309134667162384421488201894\
  376. 49581503029766353579703388699920365905324047373120549655643341862622777074389646\
  377. 42317957967457795634132283078491602681354845462336294905591488533788039843697491\
  378. 80713360895800201231109916145561278971286295284582090679521943269768969977521270\
  379. 42336429246818734853834742889330980560103357922288676566480206614652444443461774\
  380. 01172126439820562310243124840816832768854775304579417636166590305855258136611924\
  381. 90196991628024964540860533212750628406233981730540193987593512157119873066361784\
  382. 10283089779146732418239902330676994111916249584184821290161741884890744574259103\
  383. 28510676894545629386475573889945635494325985390253311832043111393820576601242222\
  384. 31752954406599632778548648529847420831796113142908575604057107282129589064023059\
  385. 31907418946110255773607562277250486349227222087557966804673075308805002278223894\
  386. 68361402870663902607934434443468629455639610312381813698122879437078536838850659\
  387. 91350269806133309340949617935630946271998532016131931538651084527217868141405865\
  388. 72232010017459153962501788701203805098164119780148853692024087086122573636233064\
  389. 50225196123397499236664073545189104486279946218881558204238658003080110689009723\
  390. 86870554525521108299650591612453434151610083544316269170638441165491024969938807\
  391. 62448490819042269804160074405392450174036209847483710949092804116773547479425117\
  392. 69672357617318954766059698481314304490693914473657202511253091340235031657959272\
  393. 71071402047457921813126432679801662762135397873186867845166464090437394613410583\
  394. 41866130194515206728071388017201750465345177683567166246451096874716792230890148\
  395. 54973165171542671913470177900964650371385571369061497989488994188845729728287595\
  396. 44639035990951487082060585723385141586276742411497951540241559999383864723301215\
  397. 96245377182900950030617269384713599791193454044355416529598060101173170994161856\
  398. 36155026578712336935553259632328638430930540914525165204987654129894537133171429\
  399. 73795506682394318732826782930749552668645632087437685400955163673119855585200028\
  400. 73697087726788222240830142818294228089082545681401285437906803150262330031355435\
  401. 70841106156839051943858493032597840600258361327454785141649585558622625225336032\
  402. 16747669816204218273393852065937390968852527871454061426726582621775736550483282\
  403. 67368597269217457845651924361951505134294767813855422501312640796469744649758696\
  404. 32268016274093312319995315408701199104881239311172712335296437902042142058375699\
  405. 48496127668188943766970732405110648037171462582288856768332108587026035298465103\
  406. 70844972539194851074168242379857338076991793231848897846533495471513960873594311\
  407. 48393232317497136900767515061983191875262963294069878067300582894318636140853643\
  408. 35451825136217333664699343258603359016092928350443561955601519525359038386696329\
  409. 31421195319086416029491768186604338108617856893658652762599159576463089057484057\
  410. 01242187456118336915674440027198999385943524260688231230651990539334501570243909\
  411. 32025557083058294784881683034322962702271781103413203729868628557061538361925527\
  412. 48513974514717282608166467373122237687789655395096239211535388318181125900905930\
  413. 70376552101723383095658510347162234372147094523951238317789818036805766053708172\
  414. 39599449395445110073949600866063140073697268098603531480280356391792592955140355\
  415. 56750901346225565651200500040388964695765286839375894326641359638758981952190977\
  416. 23309263619292928688427150600953821721493379274424742114989752222918515704297822\
  417. 77193409751093199688272829280004463814753806133897251199573509599044511222734399\
  418. 71539673040298002820751768235827912095052102735663217352194962362184727464644960\
  419. 22614998175190835220330634202159205072059879503523922819586916515854244992947454\
  420. 81066050501176252069723509637020197526019852606773842218965246052998549299953387\
  421. 55313295340940138314907468467139499677720572636120372107374342868057717426582051\
  422. 29408096995956353191128273999009796053960798443752311650773471977780957043388364\
  423. 52702396442943094663156239040132517321657829215338301025580139371525988563293477\
  424. 55255719232808344589151922043864806081186297548489573356845798244178775602686253\
  425. 78421607331592631511700654666479296482728874240118029558447112869542529777925384\
  426. 16064059274273135088608366963956793552430262618868857520064817604977259611300739\
  427. 22590764478449738830065772275665777414636443696093953753681025203011970464541713\
  428. 41193397573510378873839276937556550684521053667831828394540040197553472129245038\
  429. 33360038173856789212817138027497902255432743261724438443835191659279500017136825\
  430. 36758546723469033733698464059513247716076530428565235979898018682260049948150428\
  431. 79710747667645929446038640988204665343974190422108476050665162566607895047007370\
  432. 03648782684878109437041237808208672032110279836373360905865438186029749287811554\
  433. 84266146415144583159391700957591524192858746462325799289808212663991897979203096\
  434. 51377003004333255996575709580488051628031829131789228353961180609648076058832439\
  435. 88338519278712663084374366551964511408009362478522630426303332530214226362339535\
  436. 58646545567952000386740056413841503316500443196882791862089512040487190834318318\
  437. 72080561388048272209950449676983025946244664338734008755934808078312171484872268\
  438. 53377022052608080382561296537121309281428683267320245473419184095432657707518460\
  439. 27970701058154304742603541295214529990635988000113171975043316669542398374118000\
  440. 58621274994165791632889639236400118340323406940428738845184765282641012203360562\
  441. 43231216355689759863697496475965028711885857843551016875046246365393245524901540\
  442. 32140569865547304245954636331164655521637183906414415309758712816906121425865963\
  443. 51957297792242219399863533387281631677532938288828538833763223323803664508949987\
  444. 47380600574088983607539281237219292218879353578281400690656347782028875078818132\
  445. 40782624394992260288324899145727374030782190991736334686587324734925180822573968\
  446. 05457081246116499538396552745369148734095263017756736493650310504001208373332350\
  447. 76971527125231473234337159823811549829020925243269810853721487178387223628469680\
  448. 85831693638384498765389697888945985515666277324765372113023407091352370001332816\
  449. 56929327690078147107864309790657844779317896054314320502445959789408721143382595\
  450. 72590506761140837775776669498790344984236168335654576420399106184536189357501017\
  451. 10017725620355769563378953758665795785319349166712506777600201116719824482067962\
  452. 13821363747999607838894747697685437117948202138934986118174082899084739771156621\
  453. 95757301667695316163900286164377443339879504659246496242213615825569797905454982\
  454. 20365919158604912020715635631040315538986628041330966376721410914045182032024057\
  455. 16711882043446479392874980381935293814505434327576436725219530094774825624593141\
  456. 79226051370176894023642476014898319812498818156593637676255006576938058747631406\
  457. 15448155779212535276526235730433689192685254054526262411911016156357795666960065\
  458. 90853227700270327518712187717125280345612683023510166754512475487713377371667955\
  459. 14204267034673510427911733846292378010277610416833716861842537265620375137328435\
  460. 33633565163220145118782869823125951421106201364541930300041723532889519178318955\
  461. 85653089961841403637276624261346298183236671851622761292906447484264267072022835\
  462. 16846142659205167622312078308287364956747531477318280956792509574551832086407200\
  463. 34073280476977250429065166775862662137940822216639672500136596904942830895605490\
  464. 95125596898792210177465881794877434523159035852603218330966709911258339348544848\
  465. 72478489899865551061633892866899967002254557252011924689633992453419305686282872\
  466. 66154554977591171677234870273109994284553066290629230944606505961324859550418277\
  467. 93867266851956463510407861783979941387203353282784319564570900789300894702792354\
  468. 81051844018217279975760679807456846030015081389234525021050449348741464717225649\
  469. 95367164821236866037139904194334377622398866638519217567726283183853832672567439\
  470. 80731998946648066449320332566724813016944238626026093859526218547382982965566416\
  471. 72390560973523741831071952650956837956707426467406838497344751696859357892196424\
  472. 16124979114398039590666990374976005078576331036100207225998255550662603112543323\
  473. 69339553635821828983112217091453159478031106795275744064049680687878041449978932\
  474. 31124540042356279079504960535323207987979466036248168633614842978382950383300964\
  475. 30888224575734937428832687311310335645328966004829358961398637161232521561088632\
  476. 56469920665387383737829382390201767226240379323264372364963657655017444240199111\
  477. 26611218540395116166122909793543509424966821481768867615199335393023759742682952\
  478. 07970549690201597108189357323757477303432824688714733897849865805712867879245604\
  479. 61867732757210410139280459460173494645119897670695402692632597708541191901569104\
  480. 59955522073512931381871614054990849095548454194349319173444305223764693922634033\
  481. 92646510051744603644570754463847534733966705557908398431759668907930084657438598\
  482. 56191266312471770395539000662450582533036177906455933427415574329754738243585168\
  483. 75582912889347240535707134454582229719337307582058971444728890897813407541481107\
  484. 31186122936859973310507122731462503393873897738479354688284953678332216656064611\
  485. 03660656659313231195501369485113843929121156157449854781600361895540962234461692\
  486. 79799494846566361483306991738295501446560634290373595759154695585272538607318024\
  487. 99652816768425443425889739073884352974610591022393415807247569583300801154557691\
  488. 63437623074819008751508360426714659037680679317715318450944455507821880437147901\
  489. 72540487375906234143811810917779958944528511109543124510076618842367399621924560\
  490. 77969511122779364407990415119514440661546965008576217977093190909583132987787434\
  491. 52216525503444540470276316971436876246962004325852200335643684869288291617928781\
  492. 91424334756547562872261243516643436919624897569681514147278887655349776980064808\
  493. 71154761766945959111922927429454384882497333914219571616022292224906364296597972\
  494. 09954719580002503674675489465028006455603137064421741963422783187804694280404749\
  495. 97992506784403449261707810186526891856005592894784356202305065620907983327840544\
  496. 09933754325466268996342381853087817159138132409688240004900823384875229448700461\
  497. 03538188341821701517877946850334629894168308089935790820340259698157101915212432\
  498. 25991422979939610174887978878302811921912387279223536232950340970470263845769505\
  499. 18160676657044486620981891268715888390683926816266566045504069411325517726301593\
  500. 00546811862531404117654625414748495420965521832926255083589672181163544183138871\
  501. 06850401706146847688741355892485349512361859014754597989781338167841349892570213\
  502. 73591925918938505117120958353354468195902418584460471378852709468342796348047587\
  503. 15657341569089644452539579525183759731421602968163841208815303609996699618863979\
  504. 50418069721702975326127703724221774423997578607522442757679906248991213404964748\
  505. 89285918528422833247118694861120447658840271122911279114792252504327153033684366\
  506. 57815017282187860553032029987958807921737926332546835292644208515314637982132209\
  507. 31207970351120946260710073027789120725667430842849492024054503917506431210785770\
  508. 65441187219944044713259661653295743027549410956701543326099389775148130009541828\
  509. 40265129893522776019998300410614171832108019578950379045932608127678813899473832\
  510. 42275125648493412865310710528686896486440352946198326392195175992621585678533081\
  511. 80854622517432057724041779265437756658172231185312218755767693801703046218276691\
  512. 46776225014475875461514451431825592306694306260373264656836355532616033171543753\
  513. 53243493742242509676699722095691829203992217797492440679265480059106156747895005\
  514. 42998017635444037775787063172034013555643683051468017023738859881563516237835944\
  515. 67435566276013514967430144042041517192887237464786738278197182703598388603661618\
  516. 73572627004933423492861172405062282751212754815542642284715217354971458024738147\
  517. 76450360970418983518376319628772221549149786891339743058279126510663209664415284\
  518. 38054008727568992633244723009447752915292844413484286782907212369432924242088360\
  519. 43639506055067587721243141027286052838756138481024065262572477129997756946435000\
  520. 56233401552208865282718695548243000376564479084893901000536841057522363280370838\
  521. 89749667549341111989628841343764816576275551624938581979987619059341059658877295\
  522. 37505921354802824063847997251499460206485037420745024330993731647827119117031718\
  523. 78502492156281762509092095744129027049665089185824440951849086836244861302746209\
  524. 63475379322631881671526110781260732811062011534497765815730498778677382754501731\
  525. 65896627327221710231020444689102004159483035267539082000099323700359160202697273\
  526. 58967287596800092431351089975959771739670737705545635339787762830709652643567870\
  527. 59183966640117154025620422828106006794410917965394168536500527272432453699734511\
  528. 55161758421415997019097554830734246349425709110977253628963700518310446086702859\
  529. 04915489785451861640485967121832187912603224446865674572002909630090732796419381\
  530. 08736830057700848854987632642420122577561135179211206970609858480637530014330320\
  531. 62979008560113174534602168985499355344812429007061967707035833467717189296096500\
  532. 46081906453813744649270388930650195618060462577300950622064469234834931163196871\
  533. 83946068823139940561499289688955368854442601597891759488522130483332037888265615\
  534. 58879638240876906542931930466777690810720489086401931338095243898717372372530055\
  535. 21747524415947922113766652805888438396054147567486987337167355166104543042899131\
  536. 99343082099165015964765620845632436308178171260221701634777556411144180359219308\
  537. 84712892557953936428778244536540481659503232237881780602859055827000867386848837\
  538. 50337714980917164444693060308390225962379946272713289768929936724536553233482465\
  539. 79421273402707056538851193621576265629886468443537082357184808424713839752577831\
  540. 01287855534457080267659017382060818735190509984996309659107934323668138539702028\
  541. 21394949406134489952453908830903545787795663963353463066176422602202105775621923\
  542. 78195749462971643681534921085707270631642732845357749851399463715941895372082676\
  543. 71471332050925700993356729526111636280008058244097546017085175764114440793957202\
  544. 15248444116421555957828748745424226011844865906715664110802868290518210612860404\
  545. 45475051143892254443914386819488133792825449371700396553390063464483310103727144\
  546. 67523577242603511656995157739676429135726375358735016704706133125274508475052133\
  547. 59793783861950188821929180325547521785176580032177426333023524832481849348447808\
  548. 43978821871354242752913348569007762571896695622806296616834700668021294259786170\
  549. 53012186479789473981352503000050801790270455187977935052946992108027883296491603\
  550. 85012184940049568696199707027524548531041667993720684674742262714439058761479088\
  551. 89584182416037374890870011281786063162415194429057278667097563530351860359404758\
  552. 76975995200481698513044618610349811851333859033663164211875013087748158706762287\
  553. 49311300865732973446153743975659991079304994892588234011350360387511421993302025\
  554. 04777680857549981006888716078773295305011124146554797633463693155111583435711003\
  555. 8285979669707537501';
  556. string c=b;
  557. if (n==1) c=a;
  558. for (auto i=3; i<=n; ++i){
  559. c = strAdd(a,b);
  560. a = b;
  561. b = c;
  562. }
  563. return c;
  564. }
  565. int main(void)
  566. {
  567. string c;
  568. stringstream s;
  569. int j=100000;
  570. int i=100000+j;
  571. c = fib100k(j+1); //相当从第0项开始,所以多加1
  572. s << c << endl << endl << '第' << i
  573. <<'项的长度:'<< c.size() << endl;
  574. cout << s.str();
  575. ofstream out_file('Fibonacci.txt');
  576. if (out_file){
  577. out_file << s.str();
  578. out_file.close();
  579. }
  580. return 0;
  581. }

数列第20万项的值:

  1. 15085683557988938992636878948173134441848416561658689740214300814007875839363948
  2. 12351619099573209347117178105179626630293777486618950684934680499728298924933059
  3. 56095313880396565016749519020734162826756867545612008745257856504784958722654132
  4. 73367800711235597082735947816183336948276642243536623243673687653137709786396616
  5. 59359613120993580646300798217138405565931635846450773386124385241345993441......
  6. 注:以上这些数字一直到下一段数字之前的数字要到Fibonacci.txt文件中找,屏幕缓冲区不够用了
  7. ......
  8. 63063060268882950898006063863259047940080051640276478940808101356743637543087750
  9. 61614269302538535894126497826926386083483483162283914994717336952780631925488805
  10. 36661732689298627877894947660201648575477486296280991010257241763060252629026193
  11. 18757536005097877300614020421303520223315704282229291012841588236198124929328075
  12. 88378736971374512804563187769963003222174350234153412339956585201758283641188558
  13. 76514537810977185620306785770133110488715020268737105647858149645930446814560966
  14. 00244642164720023932468871153380653331045026576683147904465896537983620539736701
  15. 62914699498640025334993961304443857190945601399301341813825492661544633049530673
  16. 88280437282102408558513534771639434052739235375619617440444273242500228659589221
  17. 14022481177402919976428200856641367111625124767255343298215148680026395236694791
  18. 01963031291309349308684654823815911655931015257426495919607236093015539539618803
  19. 92483435775072480909312638016392700381143201630619253541178615601875860118998959
  20. 46151745076813946342347171264834439030790658733973565284695379905039599657764047
  21. 83404560686838485044523498355877298685127912626283269855399154966706170472077951
  22. 90294713756895529111860423587295431711661177392427979167315728471186440870368234
  23. 23988395459105134582899984418589270649765511667674460748262108357182608526071216
  24. 79140703760170538450827950976632491072629719509089924705711340871348025578925746
  25. 77222749425515629594235023797178412318247368734124991926842279808185369151870073
  26. 79053465561927638364752244641236000006961926777073926861715852728440625417407975
  27. 02684752172974748222181366666616888418956075505683679832621086352705007087812570
  28. 91905398133130665565726444444734220257454768694175011637202918599881581769231215
  29. 73321230867774025809210868816366172191287606908620785817044757251529913541481370
  30. 16309404347563628729034417095334900513629474110135844384255631577393334347949734
  31. 04316836193092139501500926978045539180666725805230828582281722610507717870772076
  32. 41970672530597293756497372182970063224124262644991577525170381433762354275462112
  33. 17122133261510526034104758400318322815540961773330948850269204321048665261812678
  34. 34110350858195312284472831756911082150045690426825151656110752809109786733872473
  35. 40430559277116853507814089140129479574783612864436811432524345861883044897453304
  36. 61348147594293727056251133058248640236217498111060638098513355909939643587558867
  37. 11354020347308876284595515203760376386851829199793400162838393611202358259053993
  38. 53977299754775553843070550037723507740933302690987267828000178182596815067485138
  39. 91879617519501387410862274375361014865812410659140896248554927900129914488214133
  40. 50128730917754801580736426821611315175912777527669877468990060258593590609978865
  41. 16010098865810862537551903719087947101452874252051039033423813795888466434728459
  42. 57048005505719462582978712051150687498053884474647193964018775496966543583238442
  43. 86383283474208241032617121614671823379423457394629887184446975549355109949576733
  44. 84940873040496253164731306468569189448513191726106117392216302413006916682805683
  45. 11957178789405929779641005661573127342443968474680320473212501184612329300575768
  46. 26212437237348718897522689560844248024622250789250951760959709981868617376641878
  47. 57359809046632002414986610543863385941075554734109382040936053208952421373123642
  48. 63144132388602264426443643806965592121609359332775062427547709589702506695425227
  49. 18147099411893996999524789974678037032980525474048911461525760717059829525696988
  50. 19840947600557784354926461670199796493977862797968325487496971530507555086685274
  51. 73608698655600843639574384388846525763780239021861026633142194297925286897714220
  52. 01429415796156243325940357371859123660536055782384148367005834985670820958270143
  53. 55655450826980441183661109944961179406594589830057953170983590408506029154650345
  54. 01695215687955337444036365859164879418205274105576337131253319899452429303896954
  55. 17374812677649123360297977686173868985905856782862139760003243975248921023314435
  56. 95179737752595216384902175200988078820164337166176359042219400316759026907268453
  57. 69495668829147104641130868961446439004208658473423759066523603772952777464323924
  58. 09972226773898020021400485175821434227788237636471479303364734335813524332670831
  59. 99042225904303880111656148602509488637475806861331552492471283047731959964090334
  60. 10148945420412352271434438339443553718777976301543946843557540685284071884959650
  61. 93775001839513688321615362246861217723211050937080054534564992549040572405556973
  62. 38716328067948009255788444761516538733847587462446472076796669132054328285719800
  63. 54638350252063885374806646042313683177988262058994702548823659720155511361124890
  64. 39069677107154161437209897146402617487126658600893008336249040732486942583024689
  65. 53345984443038767932393793676625816999652448498021997533552670218330359379294371
  66. 33142399448689751898932792181283122809259567580983466814580649040865980723670577
  67. 73932885760464438548480739829858786154906580262419089664483653218076121119288936
  68. 38791859669273632137010021053394822656163220355661606310637513293860438388562425
  69. 70608944601594320903630378882399823995748873699679184691375775635125955131314131
  70. 17915595873160373085315907898967276173401206495889335453212920262843178325286472
  71. 57848643945487420362295148090389716213353440535236324646721520395044687760018202
  72. 86726220503898121550140765085954248923212550760625750056281915107499858177469777
  73. 39199475874724490183186918910372306630651938235134733890495074757429420924492887
  74. 22078301220369257508436722560730373519381475634593646148944030826105707653582169
  75. 14909019734269114714262352265436691657482630341218015620360469144287219688718510
  76. 99904296623553098405213024102035444486299477768658352481369015753030369029551987
  77. 30248988187042512476791199801421063934019146790902071068765501948326692286039255
  78. 18812393257600983524652611271281863580458823913139995793212965904538959841608163
  79. 48787510722631816730099857463553719963120455039569570032982148016677570250631500
  80. 65749575035375709167366750578787110202545245842344769859155637270995006069976751
  81. 44402157146662010726505397280014779467963506188391340470136006658732984142494419
  82. 22222986168906498629350156213348243565861005137015747350040746720794360897104632
  83. 43887666432098779232234838040566528356788727748045213512984826082019936808333600
  84. 12609176206929661977977202722775268802923395540422802013115354123206772908755743
  85. 19449945136455871651736755475489062119607374771465446959619080295316385187239381
  86. 27497739424834534778689422640509718404297312575915803779683583129790024216555340
  87. 06004342876656537758405129633346761509365676774333721358572102024736779795616807
  88. 53246748294601736865925290779787324703860344260852652062753330055977550418600725
  89. 99570075814886359165475821368365858383801057198120916118221253470344586173614654
  90. 34400726754494003751711026923954914542866116448051991680056998046143989152564829
  91. 56548007152702883737919894061773294576329231438253929315805515480308968061774431
  92. 36298992730146881214397272219616919191556983530744639123426991223096138496801843
  93. 44585341905041652968384786373401610138320604003278373730402445772458628637883751
  94. 01665738385912684710260568039996830971547625229030246635927399914591185533095136
  95. 10993039362952837050420225636128435119917414081139158889409131942439465974217939
  96. 34988966426385962846824907392418213196728851909012988546629348603547538836348239
  97. 40168204752617751530242000575850250539902329844525651300932447595168562616913256
  98. 32964250300047795290823853238900947887335763368333603275221895721986731587507932
  99. 28011523103982492668583363566551052456206566999937759044280229221691655136229339
  100. 66704238927142844200019171099309947762479558881008423328812453341266604883374891
  101. 34099998753146467531902153946732279171225037307027584017997093297055643045356341
  102. 50154185669134173256232638168355678506336740744848848806688229056629200332073292
  103. 32436600167582132974759527323312792088261840778888810824358205629168087088452452
  104. 13494610355755249308296300516185592806507671823969845687300346574117332965602159
  105. 58151312115257888132163265509151796005894478322242050003187787462098704714758403
  106. 76861190015192288332550180733850707906532095537447803921280600790877860237850959
  107. 80258897480359983045834143185337232461624089722262828058238715797780748276943318
  108. 36308602435070955805041179975869373717970577241071814941250159069637777305012867
  109. 39829906600802584073230780499744902216918873368829387628581344620697477547555610
  110. 61124148049962199097283430499873811221525082623669624653054044617090638022320379
  111. 74428436575720413054377250726826298603813284937721322876009904633375883875435374
  112. 64417896679223669069365195002368044797955021664071873286485714025049386237555631
  113. 41765111864837225722389061557852075603314099606110109250737661022064395053307377
  114. 60531039362292457213740488803421596709656053989651043804138103197050680649078765
  115. 62838723078981847838599159519066909510759726209847252515464462278175665518817161
  116. 05717327447718528506515897864937505341426277677382591993206570898125977061431944
  117. 31295966806077419295636454047362760626695551310873194075374904151476290966683597
  118. 73095202174581748368910751316245632799248732236188680339300620418137994636059926
  119. 00013923549044251803297724959541136197709902037518558589111801340396142231176797
  120. 62462119702046501705602782081737823421834087937261163122969115268116621717263460
  121. 63930524834663708270225373938391089842254538112010523515294240639944257431537945
  122. 69564830501579886924080803609348106618007877792083774884778311060102379156288237
  123. 80658655021673117859058743381186835913124318981264383579504217082951951825660913
  124. 61965975946804455709510318717477788523091570077781257312564735276716749382017555
  125. 69508138715009912691543273448984096807682476492274639658244316117540914305744599
  126. 05581348696932432163654613105605773690195395483811594614570664118031205396465871
  127. 64078559637706726996336550216559224447570134657783623755464592247569572135728038
  128. 22572233846799855166984947762797942465172064734653540134039494201856606325342597
  129. 31205172173733444243567044331601760157259304843338270750723635577032657572107164
  130. 74017331260804897548948360984469330471127068798391591775623328312121568678342257
  131. 47940337479862921892682566159025292580858300951506536933824101590429889249903651
  132. 77809329638816913872829742453168432523926241424587600098571954146932579585123131
  133. 26757935010158342252953228333225928925546917858792089581720528588831911122275461
  134. 51748205536935801598875594212732824296668164009020774255872188519867837458189890
  135. 74229734788776989853154767042959932231534900232531504378206826752252542900210901
  136. 44661086278587828417439437127882550619497962795512555645728693902205403924161301
  137. 05050816562334386266952792715043923294763854444750765464502104456260383861521979
  138. 94879072842011890497579537195142603639607650869017560837950241460762700072332649
  139. 04561537289187555333946651487262992862353445884872903899256362192840464464457888
  140. 18678570320383718865393979661902610347567676866479687599897618560138607847935069
  141. 91890022604472220521359152608385369840850373227480519308708056335677161751690517
  142. 92728774040892632804591298181450412076452644633273200341521978218997359721363694
  143. 34443124721035787878554394693701749555135620202337614143167555805464051824732029
  144. 64583048581593327813747898386662835154540297452583906471922274025319837342268888
  145. 33981307884793198719661320669657930253936876773123462526766464109434299988067441
  146. 91973922533080314539961169743571846016169331752747937227202777398687010644964568
  147. 34293189294493885245640679782312167317800261047147271910339878095072678253746307
  148. 15928873538598518809555387090496655954148744692466144302237604829323582446172592
  149. 36596473752450129564038664181973674889483868212190871326375406826953846380438706
  150. 90078346051449711592593987535140280353605441459604399679020644128883768739354944
  151. 91377619686534281727822712268086656520820043220810636095124978807651506415467410
  152. 11199979557759520154540392619304368184743255011441005655683319810283148446830283
  153. 53387834709849335350634362505403290562789893372412573522793956853360035621060683
  154. 60505291363495342544728617836543983771188351479824610837564115441916807893339230
  155. 02287994177869628345374633107787346760374237241996441495323686969757657662597835
  156. 85297316973206810778698129460149003675494633232415366503591300424279464617124677
  157. 31396706946788170396900113127679820113848718891377404182010034628902961400041850
  158. 37961726461229777285500969718667513417396493713214000619787286422614436619649449
  159. 48697253357062353415621589529505080557474267684767863470311753566249084241432980
  160. 19185124748717768773763101671783861716061336381179066443228229052358302075907259
  161. 48876390898219380222753411298922853363075490426735900493308598633424606370647371
  162. 46502716295881606941973710913510928390456974594780320408948339133221712003045036
  163. 73882072270344188089460756669692220251073201948034132743321679542399148730835817
  164. 33397782475534144294364121270591350568147293910746954470689317570351347755172278
  165. 86976405292671889597238345343885534967922024432051183622341505724490711708911545
  166. 11906052155109155162779709819549297554054958943609524369571571319557603197322858
  167. 31152953522162842800235153570023458044985554543058503492078930862177062003838919
  168. 17342351383035319503637730325234452522426699579007898212473905018507468668558439
  169. 91857906159073330757847398280197715257362683148113174163291969052274522286928820
  170. 11996857664297899862243221074734821846917225648727841956233573313997622440984621
  171. 60272117499776302468736336511435913190757402371806829718971054196408585080128575
  172. 09926922965209778889380764490185570226025205181495580946679471946231922730711947
  173. 62555800852592405186747289712993414287221918590618305135368459314587616363281722
  174. 71557976615190647179226636711580689613082796997429396295035244285973834217299600
  175. 02918172473375656117097770397793051839204955959072709161183564629909982604665599
  176. 72804388236253313408354628382018094232815257770909094862785076998131531004203204
  177. 99591433302626685871619086918985341457493110245586530805423530572373428136188439
  178. 74702643552706546283439536578335099286818239867194705323002158727258480634800810
  179. 67172298682192782829443761272899970683077358029202572635055684626063755461280270
  180. 37866832057396532317905053739664239221199410111547957913002256576813232476658646
  181. 33385458723412178779241323891586379509047449256847786234783263663496624645507241
  182. 43521390634740534039061816738936583801611815909960910905823083217161534633943515
  183. 05178491824564791406832334554184971801993279295328782906346939919533276276021677
  184. 73698923789303027188811640999908991517777147594215166081379677997498608588614736
  185. 86006099340093932142033965313870431645809313315572048407764049760656201010054495
  186. 50014510239615378070378679263886818904640796496861879847562073656712344802365831
  187. 37859601711566871935760596541102118582254768729316690416330734929732206712552911
  188. 64026420755173410689589480235358042785777239444130547001770398465070018801604034
  189. 21159067577845994014033595486569964331813620785601527951636104703257006335171381
  190. 27625606315898116491079255207735934389646282142520695578332964053335695655702036
  191. 41669588768563851218381175154850877297653616475740172383057128752671979584573589
  192. 65592044029177464934748173141350591486050664684404284571337317635314735799705291
  193. 89868880795047234967487628732917374507104446947637145861742226974572812403986222
  194. 34408132273503634242155648871133395744657050938639866916714280960059726981101933
  195. 69257527572410851559847418596878601701209218346738822789867492760576828818076842
  196. 44848958952313593729199820342735471722218420672024201671108861401094289601404541
  197. 08616747174890579372473820655953642933804520588045482024246108284984862069210749
  198. 01679555351807076934105474247609864986100810865909242392605651365395496851959032
  199. 08100431263615384605587955915993892245578806347288774157615697652140686800759126
  200. 21238789825639637994122687748188407141627827835475185699069175421127783624222333
  201. 49678876317027558873868274361550791172640030907816685368310014362764067291979389
  202. 93775584815425752331244980298450804830924598476884649098119082204404690473237741
  203. 77039497813018405539411366900459728796328370526663682364735824451816520433406374
  204. 78366610795195982798063828625397616910502798241166920799501152693806128302682459
  205. 14476929043386341127902066798565170023170349944324836038809870067672625705690140
  206. 22494815236753209426787968182307692654451009535436412067564999895706434848879679
  207. 15245184378275830112487771642974426124993722493752119096403621265359713798007445
  208. 49107559583660269211151657743051658902079457388446123746781748014565976976048839
  209. 61836575114092361515967148471826157744963591514102011004486188126552427850098742
  210. 37973549574850578445656759631526525273512938191078609570169084016798015171772478
  211. 56527438025839221701638982734159394553304711950099507880543720646569818879038747
  212. 14555735773694171428843519882137766788936357807563681983015404302167913560547905
  213. 24789529738974039850258271364200354113150871982836996268674761177194227258507443
  214. 41024086362684032162760035033733882335990865933768719478882479570892225457675569
  215. 93868884124276779489103798613170431211919776932453997253408349348474056305928469
  216. 57182853903839819630054501124672714531880750538427549287021903451777629325356416
  217. 29793735740310572811223321975839274211265323056116418352575524384073494615819539
  218. 64251291286177626873641355786863589999763701175917768325226704916041748498390282
  219. 13979407299733885195737075315014526688259718393122684189568769973390260148889579
  220. 65236876043412560478308543025260707780900532389139961535171053888173313295475700
  221. 96930927452599529973111085725444036098131552673272922897822579140588219809348057
  222. 14437410339589694489123512461037672228779524454220074373594957929641880663548772
  223. 61373548262787488962965974967122962454717606507053928387506667087880355058979578
  224. 98572260623122302626417694151417637765913632683154956361579418591058632167169312
  225. 67446868978090417298036410605702182720394746690032246342577131454161489637228102
  226. 48267114175241221731514632685607507688849322393367030391450017818630468971232707
  227. 99279311443568298661273165638253755978360242808649991555126246184781103582432190
  228. 85224734062456714052502887603132869058356132138422707882297652777202664609959855
  229. 29365166947708724332740808886626678256490568501054824550943358328960920973095363
  230. 36729083137707176752558775495562901244645623804083100422916004123430544570271350
  231. 43894473858036542815259254757344136401683849723417114159187192401088008572981694
  232. 19174935529760758111258909764227184155112899021930497607881234857153277630747772
  233. 24366580933934567892536634546835998591562575720276312688516243734277814752987600
  234. 17929249089732744607550234417126814680281537934059988013819131080343586435864502
  235. 20951069509350125355134817547627969976338542905820363503754925936852799302420274
  236. 66424307603368324993982570582767121726035446481513768855348259223509510285301511
  237. 91534695682283922435992996263069870007556727745714167232280996441571686391178781
  238. 14272242161639236399377889453947689476525838550940473412240035558264149427067493
  239. 13232764068003035008166972852880312467865360124217324653798149584239847919070613
  240. 07242823991958088415085027646082607154621635550048279463316513973357824512636117
  241. 14762028385583654441183138030308768607592730893151891833758462110001667260350788
  242. 28578168198959637249301366232777532479767939646746798030459101228175214535631841
  243. 23076506951671346494524125158956629733869373025544669831034174977860766081246447
  244. 06831615997334778660038394162791559338971967418593529359029781987822153997853099
  245. 87331905351968194445803712006493970493858479246647649510582577174952903760556879
  246. 14584072529963130135950148170772005646927223463377300409913051235941103771832911
  247. 82566932146433117269899376111364220643503629661196491517873749781557901899783549
  248. 70000953198288032593981489960370531465319950030617636583771771162084611936027598
  249. 13826202368953337098883391183026794681729347662091845786857711282414596703566771
  250. 02811512514428474492069130880242557690693242955852774811330605454388674900752298
  251. 50049653086809685079380775339459558537968403053732301506360199554035783473851296
  252. 54075699550463107041176187979676737739279212807347902086924766058687416459933829
  253. 89267513820422554708576495393839333325551833031475218381008077369076852207183340
  254. 95513424620566535922323417155710126103675192747492337829276668594518288255731244
  255. 84731553544233351878200191468129755483891630143760683743538432726343833340830807
  256. 94551583248480865237680876028911028381875538961037104255329005796111783526742644
  257. 44557026781460972656035808276212031641532443726229309485947779008678598327758043
  258. 96543318450312387463112766976803855855515550740811012433175024835470152184506497
  259. 03858469585903155017592082105943221103529030282769822791427931098003279754286051
  260. 67273952134581614764788887742985857426310994145698683320568836256905342514883980
  261. 61919266452078496502566481081866785011409405962685159471016019695356881278605921
  262. 98311930359662773420761637005270605960904549558081877940350443701724725404996046
  263. 24860669762080766091397834452390286693135863208098322134761802112675169932302218
  264. 76563302172446109881295727602037727268745415928230692630156734388980665731105990
  265. 95152059516364642142841244964400257632087042283113541609579753766084793377201559
  266. 34862044057126102996470171408769397213305845945325606766613918988188499919182243
  267. 00721895809243571517475808093458320363476093851182053037518106129886891458495507
  268. 48057457907701739913532002681162649274694456719526518562114539690079315906982573
  269. 95188579151548153725085415058297157944654508333832462413982904911423296976009997
  270. 67355921326274696184593336850676230752253825999590755433081764975619674295879999
  271. 87054022207780370393752198480775531811441542082990950288209761769035150057364420
  272. 65130665339725182134413002171723033270469299539248831400193012243900859041458288
  273. 94633580760300276061627881984181909718811234280187478825475386951955562492808035
  274. 55584353342431591557579918648365030455868696814963017821396808597069303690704789
  275. 40581310305255304819956500097517482231380361293745575987641131742542471281209826
  276. 50781434942301780084705869279850466812063785929952483643868364641371154742367144
  277. 07855279832137983610856310973320009472676055929744423618276594342187090252289138
  278. 58481466331705883565425161832046352843601194292412400946900777689213467874896345
  279. 38784823909605428524814082751016870729682543568597512679217380891891997137349231
  280. 49719456692505182171911762503766964830362795115396692635817899893609137406732663
  281. 05746327670009127096861089977472975633036238036356561687634696036168637007503502
  282. 87335759421960118762039279556728441913468008990010362443313342376598911711153902
  283. 03860017523801025895409534450128633507951081898642632316928393550332380276336265
  284. 54680416354509158498345931723760076745339222167550733481317826346277345051413008
  285. 15249196879925051285275768361039594323756432195020383660344331836832045332956589
  286. 65603424085185577946570068592928984955534461925998422249496638367291750279959864
  287. 86451276034077915706474873641061795721087735269146050418469003292954603908529408
  288. 36640156082687778274431748681540844807567243228281407976343325089496555721107648
  289. 56735922195951983542863532053789465176801176476145904307611669181655274531762607
  290. 97488465451244525811018757765222249827314342381776874206356250030767750383292237
  291. 81110787786045200024057007364600281463220746636087103827759253863812330214511548
  292. 98973135879073889989551527483679528554063979518185375561730683368174848654163996
  293. 36822866352627737132983117379480210053832855796680799426132550147304181571237458
  294. 11025009092945478805123833670756315514245369758574430425970932505540656992756263
  295. 53574322186287559282059723208383808531011618825713740726934434742559093323706126
  296. 19600271253736879520386018790006089521740797718194538805328694723905247375245329
  297. 62250535388056248174791974174670604177525143475150764981822395310883039542382215
  298. 49351009970624402084900272950782638693852022231142741503929713071110792074068146
  299. 48517908159557252890478566387761646265366946268935926174736421253286602447694419
  300. 26145193100761099748619261263523596303292142019577046771197891931426547987773124
  301. 50935031089429802652246259408175853125
  302. 200000项的长度:41798
  303. --------------------------------
  304. Process exited after 133.8 seconds with return value 0
  305. 请按任意键继续. . .

直接用fib1()计算第20万项只用168秒,分两段算总时间反而多用了。后来把strAdd()修改成正向写结果字符串,虽然可以少掉倒序的步骤,但多了强制转char的动作反而更耗时。

  1. string strAdd(string a, string b)
  2. {
  3. unsigned short j=0,k=0;
  4. string c='';
  5. size_t n = b.size();
  6. if (a.size()<n) a='0'+a;
  7. for (size_t i=n;i>0;i--){
  8. k=(a[i-1]-'0')+(b[i-1]-'0')+j;
  9. if (k>9){
  10. c=char((k-10)+'0')+c;
  11. j=1;
  12. }
  13. else{
  14. c=char(k+'0')+c;
  15. j=0;
  16. }
  17. }
  18. if (j==1) c='1'+c;
  19. return c;
  20. }

有了以上的经验,把第20万零1项和第20万零2项放入两个文件,读取后算出第30万项及后2项;以此类类推,一直到计算出第100万项的值。耗时如下:

  1. 项数 耗时(单位s)
  2. 300k 300
  3. 400k 330
  4. 500k 400
  5. 600k 480
  6. 700k 570
  7. 800k 660
  8. 900k 750
  9. 1m 820

估计不分段直接算第100万项,大约需要1小时左右。最后算得第100万的值是一个208988位的整数,约等于1.9533e+208987 (才200多K离字串最大长度4个G还远着呢)

这个数字大概有多大呢?

网上查了一下目前观测到的离地球最远的天体距离我们137亿光年,折合米数约为1.296e+26。而第100万项是1.9533e+208987,这个数加个单位米的话就是2.065e+208971光年;137亿光年才1.37e+10光年,不知多少倍了^-^

计算结果第10万项、第20万项、一直到第100万项的值都保存在文本文件中,数字实在太长只能打包上传,下载地址: 

https://download.csdn.net/download/boysoft2002/15611989

最后一步放出计算的代码:(第20~90万项的稍微改动几个文件名和一个常数即可)

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <sstream>
  5. #include <fstream>
  6. using namespace std;
  7. string strAdd(string a, string b)
  8. {
  9. unsigned short j=0,k=0;
  10. string c;
  11. size_t n = b.size();
  12. if (a.size()<n) a='0'+a;
  13. for (size_t i=n;i>0;i--){
  14. k=(a[i-1]-'0')+(b[i-1]-'0')+j;
  15. if (k>9){
  16. c+=(k-10)+'0';
  17. j=1;
  18. }
  19. else{
  20. c+=k+'0';
  21. j=0;
  22. }
  23. }
  24. reverse(c.begin(),c.end());
  25. if (j==1) c='1'+c;
  26. return c;
  27. }
  28. string Fibo(long n, string fn1, string fn2)
  29. {
  30. string a, b, c;
  31. ifstream in_file;
  32. in_file.open(fn1);
  33. if (in_file) getline(in_file,a);
  34. in_file.close();
  35. in_file.open(fn2);
  36. if (in_file) getline(in_file,b);
  37. in_file.close();
  38. c=b; if (n==1) c=a;
  39. for (auto i=3; i<=n; ++i){
  40. c = strAdd(a,b);
  41. a = b;
  42. b = c;
  43. }
  44. string t;
  45. t =strAdd(a,b);
  46. ofstream out_file1('Fn1M1.txt');
  47. if (out_file1){
  48. out_file1 << t;
  49. out_file1.close();
  50. }
  51. ofstream out_file2('Fn1M2.txt');
  52. if (out_file2){
  53. out_file2 << strAdd(c,t);
  54. out_file2.close();
  55. }
  56. return c;
  57. }
  58. int main(void)
  59. {
  60. string c;
  61. stringstream s;
  62. int i=100000;
  63. c=Fibo(i,'Fn900K1.txt','Fn900K2.txt');
  64. s << c << endl << endl << '第' << 1000000
  65. <<'项的长度:'<< c.size() << endl;
  66. cout << s.str();
  67. ofstream out_file('Fn1M.txt');
  68. if (out_file){
  69. out_file << s.str();
  70. out_file.close();
  71. }
  72. return 0;
  73. }

这是比较基础的笨办法,这里的strAdd()函数有改进空间,一定有更省时的办法。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约