C++版本大数阶乘原理讲解及代码实现

C++版本大数阶乘原理讲解及代码实现

/*!
* Copyright (c) 2020,ZYF.
* All Rights Reserved.
*
* \file Factorial.cpp
* \brief 计算n阶乘末尾0的个数（暂不支持大数阶乘）
*
* \author ZYF
* \date 2020/7/10 17:15:24
* \version 1.0.0
*/

#include <iostream>
using namespace std;

/*!
* \brief 大数阶乘
* \param nNumber : int 大数
* \returns void :
* \throws <exception class>
* \remarks
* \see
*/
void BigFactorial(int nNumber)
{
	/*
	算法逻辑：
		大数阶乘，核心是如何将每个数的每位数与相对应的数组元素储存起来

		以50！为例：
			1*2=2,将2存到a[0]中，
			接下来是用a[0]*3   2*3=6，将6储存在a[0]中，
			接下来是用a[0]*4   6*4=24，是两位数，那么24%10==4存到a[0]中，24/10==2存到a[1]中，
			接下来是用a[0]*5   a[1]*5+num(如果前一位相乘结果位数是两位数，那么num就等于十位上的那个数字；如果是一位数，num==0)
				24*5=120，是三位数，那么120%10==0存到a[0]中，120/10%10==2存到a[1]中，120/100==1存到a[2]中，
			接下来是用a[0]*3；a[1]*6+num；a[2]*6+num；
   				120*6=720，那么720%10==0存到a[0]中，720/10%10==2存到a[1]中，720/100==7存到a[2]中，
	*/

	int nArr[20001];//存储每位所得到的数
	nArr[0] = 1;//从第一位开始
	int nTmp = 0;//每次计算的结果
	int nTmpNumber = 0;//临时结果
	int nDigit = 1;//每次计算的位数
	int i = 0;
	int j = 0;

	for (int i = 2; i < nNumber; i++)
	{
		nTmpNumber = 0;

		for (j = 0; j < nDigit; j++)
		{
			//将一个数的每一位数都分别乘以i
			nTmp = nArr[j] * i + nTmpNumber;

			//将一个数的每一位数利用数组进行存储
			nArr[j] = nTmp % 10;
			nTmpNumber = nTmp / 10;
		}

		while (nTmpNumber)
		{
			nArr[nDigit] = nTmpNumber % 10;
			nTmpNumber = nTmpNumber / 10;
			nDigit++;
		}
	}

	printf("\n%d! = ",nNumber);

	for (i = nDigit - 1; i >= 0; i--)
		printf("%d", nArr[i]);

	printf("\n");

}

int main(int argc, char* argv[])
{
	
	int nTest = 5;//N的阶乘
	nTest = 5;
	BigFactorial(nTest);
	
	nTest = 10;
	BigFactorial(nTest);

	nTest = 25;
	BigFactorial(nTest);

	nTest = 5000;
	BigFactorial(nTest);

	return 1;
}

[email protected]:~$ cd /ZYF/
[email protected]:/ZYF$ sudo touch Factorial.cpp
[sudo] password for zhangyanfeng: 
[email protected]:/ZYF$ sudo vim Factorial.cpp 
[email protected]:/ZYF$ sudo g++ -o FactorialDemo Factorial.cpp 
[email protected]:/ZYF$ ./FactorialDemo 

5! = 24

10! = 362880

25! = 620448401733239439360000

5000! = 84571558532110870444021284004671688107815733492532934976995648043627161054162164013817980957434127750741694933146013708917569721333676254726744217875455752625587807261169243212878089579739644797438594177924232253059366435510007984843936740629381452894575757958080950976832443045334385682193847382089913194347270589680044768076224128964046171534220900461234978951085661952356344808161064961985561865756811097239872909658242375251649760437834795580010042642519608727848925292154102271769319021735094117166784931045117807094887197669476635797606926601691726302041818301987130764002186609593148511348386183411034561040047215017198239527045751181580408673948624701383366242384899194311253481504292439797246617725199660571972971515749889192623057394177342009253684729635797981090938172278322643668834829761437246889622966241898072239309374553551123577365744053820962818491282068367195120855291632302635715180332214356508831396176671874545999120674274240094209887531258228497721067059899928460139994440983624020163811887828135010653000955106770179819589020310218297381400881423914467205248673626466043741857539839361331313950558084451653568312216675285156206525840537442214054936278870225720300465238129991834379472835275687298243941821968188902979071791820760835388391331566964414349821102550527829676234410520965393032528542018983878666532206020872106091823402911441916942870744389649337358693475180974453626682041572180731421761275323249949901482621415480336436117189105289034281855493846012539502269208834913589347165756452325916849735031475834588544835756621085971649023515102376901314884965514932160047717675698479249473752301403153545179664225726459107408980503277585025518168358348928093382706209469596892999230919108402799263471495260348007359238583988438152579089131252353408359907632226677462564702306830516261817583176727670332959445182588854130711428502347464761446526591624359583335938465937419384780200651114957811019961497412209446129239196991047931522441734773302834339861511538379580535031468415172959269067689367017193098145465264382100812857942619244901032412933893619773983424425480900804136984653248352026582045573337454061056941890505365099323554499929041339967385182138178816527480208699674318225291164456121272278823068863354353986870732856985658887282953923176398732277651115497541987400918950781569029806886904234912118807983253688939532364277494141065111915586639292199332429075512987094833941712477842954644573101436498086003237228438552090461534124228592353454940824723221444001948751729498550733029906432956169815029266014203338262684132576512523656773167396726421752142085503214669669557682959346485416082172152368256377661423019796427067681322130429417409374952199085494734701890310719953808073470677110210514336530063536481148798682972478466396286515836438664379788090173002722199619676798622199271196265600209946317719262426370760241009357528582133873120087461126686396975809799704940258660157868906573631335952576099106569277204026696053055967389278676999135009998741562949312308687786086276847575796369560577201994217739126597669542372624476557192730623026475586274729479485873882299805750394445599909036523097659790230385336422490271063694441998087071189977459984407012407963202217275247307956434476047569330134724902127006884637463067661642408760942199883845564207949510543483208778033944792261109874368967223960713179212405001818732879872034401476722670881018865814495303781900501544935168397882444931878432623270407629472495905707946417861906684382127140561115325944031311302153556161186690726224365912358577534600560490186424555770593683641652355695391128996077138255157474535608191831742346794220633046535612159625521849234700824036533374852561077055168795833521801548676149684150237023820584392067875256197350733017042573851064307357586504376514820373227410865794747172545074035711761327970270077388807920985651764036083835614729938777160519551679778402877949433093194702170521141246880413927413132025907146808716592294685455161126167902133475069851931903715129387944643655156000650118779060764107939511774102308614784165484488103259941747919953692241249325819622473602515978256960501018805783391953015879087438262275862885481027119926075128442905458868359449237519592814847829567798708313166943231371699807354611322270766673417509780082618396335266149808302067519461449377167849388343109659146150123701176316391905798532045125380687914662690133394590423046133739245584189555994867314894534694281785614282256777616538675475615458620822153502727895240122171608119203927811603152200467492773870445677160286991435625116289172586008495880813147371972401582920918051082785990017608942076951798065309619467633388100017090544742714278980492764061733708360567663505533612855697912201151171998343793357289830812714002899438849975784171946250855113502915041279823630147279496620498158768345130684378855353823319630686016927417553902059083027310346935010803047941208514349200217993688099769197095595581006326513697831311446201299945299744296160036354071540300596601775897448777543776883366606941744647901075528446588819154643827516474334784940843344600451376627155846078937780132493236506531698144881353404987915939443493497112599636629933122348799536096418833251492775932061034254985023845273523067504876331243466154330025904197750971293426372520477523992866973592302881665780412216566636178244265170736571293983201590421033392090339086122842461148601375443481431094643591515403519193528112762545830773502739742479114108470199845721195093992437239106270826427825287335380093085999362336110147573354133197605412594500400376569177229068873754291072260882893122673818572549655396389367296110190593736351742971994594616466584818955417055055984660978543926662950312662238549230077843858123356121580276690227413260136875253439977103028736253227463982420647093957351284242124979801110712804584869166252846207672683356343981670828082343548037190121334839669628669088849438287365645130876009572078115184483414360534129375090842325391749359079708156892930828076350229993054724224708176033398056029806645027892166533634186142773765309995474857225557883556950536265674363751820728428176356644147961611942840657061944288608369091836600566681741156627656994656752257236585427349032379473241447479226558188996802830881660814881078613508153425236509519426168694062277963139073194357712804550134847480064724370018953053504388380248277495655976685294174723362497076888802554504210014455863170619255824226232033554415590514522760048136884377090707424268380447275936802477051057721437993545138845486664789719015114167812375490031930436882999631095221509601610838463687389638346526286120709679958156661453527345818196154565471170869606452013494507419557092913552236361473484873478353972751614429171958297006740118598992758673820056688911617967610803527080747426603862258616191657522421476074960132053953568577671653147497311357173764403028609249931199152075953737063638473161293839916814369098721384433955227508532447931728997954184295626941825583492174326044164396286930849013146252536617915806202578672157728821446036961080074627202843245831829398403976829658002882862560180620421566661018047687145355883235449374682300719740000630218563140066216345483124936086595441014090091336779725260340597860229072895483371346502466075295576349807210514521104136874123223307951026508273860773556653441645464732849841286472617853753765330187938372336654347951495910598648481237398484072756385897073619607051266218489643053855243823251829177278735406930696073577425226673423393645290182999411089704251950374016944005134931750480786412209180614007887650403876620496185803936920494434259664325647598925425073271994379674885019824134737676747659930778406132568614909511814847069054805842321218269265536949904409202081915121469631020335440637516017844898950584406218768332317764716998786349029982879111471528316837095966340485704793090217505085092955458919046072189283308399559589427361268983199754481835288627474235708442148114424233373738430648098016076841184238524575088179652295781624739791273416160937525704899979488171135593891381808468106071188704928150335574790622785739722869445514428989378379218658875095348246981558550867669882464612015753522017989831225386807784229674043438677523564674071785163422573912690000273523979429080197328692384439535395186002111045039782600424604356166386866176089318590910433182371187840515956224590413071472582895680989294913000623099614411316072133476177914549292875085611163864459861017857561374907480265420054885663585071000690307338634422417645520788561957729145461395994257129915386870800806145688116349329675331699607991792848674036690830344057067562180822624892486580670792859330221896567376916025517740258631219845008903625092022654997202894087551462776200263855224935223322966705787111500621203689957798875654922770930341648322633536292782374000162569028868281347997086014554460751622322702218871122979264785950169276630586052716507072356967511703933389994450387103190761441567723028426056890010359047952193686639658519784324644716479278052509771371175091639674311801689572017349189141823625758645644410353501874373222002638725169044698789965902239856167572104701282553867509626121918852892685015520229466841827825708325636634452428756612592481629878399437505621273469775335696320468548646005431638480837537309165303872398137467378577343026768049097222196496400896544359899331742451434885808983356238964833126312060694766663533024243610556159191644059666122389032803882663110075932596043071536146224906117183193941994797611148710016655814368991950470718928870957936074425268901884614050799020572891647490935552202711383242461950457230410642799749134606825535300673927336461333110410312498226505785231172773700620169836184101536131653183055232743985738851670120971946454789857216052128125504268201560363021124757585242407884956366687886775441279160223161816838158864039035647148038109319198057923542355239054070810238745445944449688416088019750073882255537318604426602125006372417029015284210596101767439597210511550060789921231688567769373227502193688313461967615878869914002605853035591424125111170390262714805979517856695105066881971782280138889861686574801003110866517558779016048225707751745189027280167664988894269287365229639081200822969174046814585339548126265175726958133539653236300251223538455143058249832964340474576883271520199370220187882288935525637201414455704462988209712879251159361644257987159852441710777844232953044170073541295298299226757870752307478313835564447548967522824050668524501601460102694684554285466621269194360648048845390091618107865337820723876399767768807246359056487099072497934146831189613537703064214612895215571925725570456731448912861289819255503434531390847678588391681905450656331914506906285677925978801177307897364823422785925471387794696587170930055737887402959676765200411641770703414643257745042904441053193922992429576968025800901547450484921014867932163636592059203839262824999707684403539022072276112340203271548708506229733873998826188181673644014387287022395718556498698295410437445309221839919453887830480093580234720504206010377216067416968022962049270257652797234016360977676150040704289669748169830943742895771561914903099901001014157885768577682005575555491196226463988124835306429737263316347354882016812687391997903857662173824903573268511870691648517882278103293888075512533164315569187365981935950909670102094726754167830206770927920550697280327040926776868469342987128285832171369344974848956411022751833647294459558722594216060506186895623105547508091793798070961611661876253464718712619709312875241877074210561668921437815200677756323603970654751899713383340940689687672700683273665053280644834903895335628085663865496570376428068863876889095091353050683931838866426517086454014151807713047933645434260001837824410169037052302925587543519505770595727586342242505905888664751582014581800340711752759722496056292618788878383390025867263009057032707862573717285487459221889220247120975487972659922379951193199321749809854233537053735067198259516641817910659281904728023212015699001075578556750029468824424755581545426829329480897967517897535084658909379870844068333992273339795305995716159179811172810077701416627466615367953376492736198471043945448366347025529237822476097176623113895577620351941795536429928868063584888617034060738442827524238877728397901672067861291807472368587405742151664393321509222752215272508785722863248578150804216446724002461876947462444074853806767715985735714587886833657410752674818387636926452226348186855623583778328489502708695689208109891075966911232670763173688338410903739783886835077332780067151353120652872753581344325324066175685109031441623449276250302533969337177441802628972326512092203902674362917049997635325985028429002942041238638074734276069532686205941044482957006037655021269489248251741587467817019151544863347013377018841752307232888088751172032125167418260114832413054734188377733592914110148944942827400393633043190876139703199896672271504264421226376954385328388479070282446709349292298348602695173207467635306520911480585094455872057785237877179939131375356603437374797752777525194548795212562652689329535882735945236986679014933164088335597961320840787423333267339256513869819469678231173800971206502443848306853704473863207353098209540546704308028633667774593681088659393536807214636487067244973086764719624708833502921668156233332371756346796124839850915570692535607807987511560551988591441056208755133395879367621868223791895153244038243507018727797093056615738474132502464736878047117527245664931432236742815761532232435903577594560368314403927816880053807490076238559434062897974363006263998422312781660603457602522128412401071848055655478783605278343544027225196955386796129412752604521777071987519015817757816358360439153606676393721024097421522174979682313748031990604127819627798652219107773652816802432166208105194907850315280746577817347389673280946924541712008178322156444388681035958910031069536593371064019500381116283982918224836300212451125482246314275471739438874826164405476768763188127714277582667518472466088090697446609448133756826666609579799051044293769594762713616799128906601044510264031053553779082554065855734165498008234415332622556727630468709536332624237817372998276047256355055189212242362668410958360323844069382552076380105602468794719654092299962902264923639131705646408931654016412986936050311302254564416762312638451301989040244533320645211879249403941533716079257395110223037994609817010351753061357151600132084813378834124060769357172051474126870519917377017735930800893037558041788587030643463350022747606293206928485897815264445626752659983928267300405725457853617512007322754121492715103015817596419944532026094581565149381635090390481114758262622634123464638319734794317674621633783393731540830139102589530477226963153393516072952401057812044548906348861099680572609770173911552305730065216188232137714139778952409295700176860794621482554838392339490103422065816563040254777732684526298429418044003388127300962409407203347720458134325963282239640453721592264947910011513512913640950923808084602212474273479199135788176941195371902901003448303549203470286198194523101875666944000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000