Найдите сумму цифр в 100 факториале в C без использования массива

Для решения задачи эйлера проекта 20 найти сумму цифр в 100! Я запускаю следующую программу, она работает для факториала небольших чисел, но не для 100. Какой тип данных я должен использовать или нужно использовать массив для хранения цифр?

int rec(int); void main() { int f=1,i=1,z,s=0,r,n; while(i<=100) { f=f*i; f=rec(f); i++; } n=f; while(n!=0) { r=n%10; n=n/10; s=s+r; } printf("\n%d",s); } int rec(int t) { if(t%10==0) { t=t/10; rec(t); } return t; } 

Вы должны искать переполнение, распечатать значение после каждой итерации.

Заметим, что rec(t); ничего не делает, поскольку он не использует возвращаемое значение … вы хотите t = rec(t); ,

int определенно слишком короткий, попробуйте long long … если это все еще переполнено, вам нужна другая структура данных .. например: Библиотека GMP.

Примечание. Использование некоторого «правильного» языка для задания может дать вам некоторое представление о диапазоне, который вы должны поддерживать … например, с помощью python:

 >>> import math >>> math.factorial(100) 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L 

Приблизительный факториал 100 может быть рассчитан с использованием double типа. Вы также можете использовать формулу Стирлинга , указав, что

 n! ≈ sqrt(2*M_PI*n) * pow(n/exp(0),n) 

Если вы вставляете цифры, вы получите n! ≈ 9 * 10 157 . Это означает, что ваш тип должен содержать 158 десятичных цифр или, что то же самое, ~ log 2 (9 * 10 157 ) = 525 бит или 66 8-битных байтов.

Нет фундаментального числового типа в C достаточно большой. Самое большое, что вам гарантировано, – 64 бит (если вы используете unsigned long long ).

Итак, если вы хотите вычислить n! в C вам нужно либо построить длинное арифметическое умножение вручную, либо использовать специальную библиотеку, которая может это сделать для вас.

Для этой относительно простой задачи вы можете фактически реализовать длительное умножение и использовать его для получения факториального значения путем повторного умножения.

В следующей программе я использовал алгоритм умножения на месте, который изменяет один из множителей в процессе и в конечном итоге заменяет его на продукт. Алгоритм может быть получен непосредственно из долгого умножения, известного из школы.

Эта программа вычисляет факториалы целых чисел от 1 до 100 включительно:

 #include  #include  #include  #include  typedef unsigned char uint8; typedef unsigned short uint16; #if UINT_MAX >= 0xFFFFFFFF typedef unsigned uint32; #else typedef unsigned long uint32; #endif typedef unsigned uint; void MulInPlace(uint8* dst/* n bytes */, const uint8* src/* n bytes */, uint n) { uint c1, c2; if (n >= 0xFFFF) abort(); for (c1 = n - 1; c1 != ~0u; c1--) { uint16 s = 0; uint32 p = 0; // p must be able to store ceil(log2(n))+2*8 bits for (c2 = c1; c2 != ~0u; c2--) { p += dst[c2] * src[c1 - c2]; } dst[c1] = (uint8)(p & 0xFF); for (c2 = c1 + 1; c2 < n; c2++) { p >>= 8; s += dst[c2] + (uint8)(p & 0xFF); dst[c2] = (uint8)(s & 0xFF); s >>= 8; } } } int ByteDivInPlace(uint8* dst/* n bytes */, uint n, uint8 divisor, uint8* remainder) { uint rem = 0; int nonzero = 0; while (n) { rem += dst[n - 1]; nonzero |= (dst[n - 1] = rem / divisor); rem = (rem % divisor) << 8; n--; } if (remainder != NULL) *remainder = (uint8)(rem >> 8); return nonzero; // 1 if the quotient is non-zero, 0 otherwise } void IncInPlace(uint8* dst/* n bytes */, uint n) { uint c = 1; while (n-- && c) { c += *dst; *dst++ = c & 0xFF; c >>= 8; } } void DestroyingDecimalPrint(uint8* dst, uint n) { uint8 r; if (ByteDivInPlace(dst, n, 10, &r)) DestroyingDecimalPrint(dst, n); printf("%d", r); } int main(void) { int i; uint8 factorial[66]; uint8 factor[sizeof(factorial)]; uint8 tmp[sizeof(factorial)]; // factor = 1 memset(factor, 0, sizeof(factor)); factor[0] = 1; // factorial = 1 memcpy(factorial, factor, sizeof(factorial)); for (i = 1; i <= 100; i++) { // factorial *= factor MulInPlace(factorial, factor, sizeof(factorial)); // tmp = factorial memcpy(tmp, factorial, sizeof(factorial)); // print i and tmp printf("%i! = ", i); DestroyingDecimalPrint(tmp, sizeof(tmp)); printf("\n"); // factor += 1 IncInPlace(factor, sizeof(factor)); } return 0; } , #include  #include  #include  #include  typedef unsigned char uint8; typedef unsigned short uint16; #if UINT_MAX >= 0xFFFFFFFF typedef unsigned uint32; #else typedef unsigned long uint32; #endif typedef unsigned uint; void MulInPlace(uint8* dst/* n bytes */, const uint8* src/* n bytes */, uint n) { uint c1, c2; if (n >= 0xFFFF) abort(); for (c1 = n - 1; c1 != ~0u; c1--) { uint16 s = 0; uint32 p = 0; // p must be able to store ceil(log2(n))+2*8 bits for (c2 = c1; c2 != ~0u; c2--) { p += dst[c2] * src[c1 - c2]; } dst[c1] = (uint8)(p & 0xFF); for (c2 = c1 + 1; c2 < n; c2++) { p >>= 8; s += dst[c2] + (uint8)(p & 0xFF); dst[c2] = (uint8)(s & 0xFF); s >>= 8; } } } int ByteDivInPlace(uint8* dst/* n bytes */, uint n, uint8 divisor, uint8* remainder) { uint rem = 0; int nonzero = 0; while (n) { rem += dst[n - 1]; nonzero |= (dst[n - 1] = rem / divisor); rem = (rem % divisor) << 8; n--; } if (remainder != NULL) *remainder = (uint8)(rem >> 8); return nonzero; // 1 if the quotient is non-zero, 0 otherwise } void IncInPlace(uint8* dst/* n bytes */, uint n) { uint c = 1; while (n-- && c) { c += *dst; *dst++ = c & 0xFF; c >>= 8; } } void DestroyingDecimalPrint(uint8* dst, uint n) { uint8 r; if (ByteDivInPlace(dst, n, 10, &r)) DestroyingDecimalPrint(dst, n); printf("%d", r); } int main(void) { int i; uint8 factorial[66]; uint8 factor[sizeof(factorial)]; uint8 tmp[sizeof(factorial)]; // factor = 1 memset(factor, 0, sizeof(factor)); factor[0] = 1; // factorial = 1 memcpy(factorial, factor, sizeof(factorial)); for (i = 1; i <= 100; i++) { // factorial *= factor MulInPlace(factorial, factor, sizeof(factorial)); // tmp = factorial memcpy(tmp, factorial, sizeof(factorial)); // print i and tmp printf("%i! = ", i); DestroyingDecimalPrint(tmp, sizeof(tmp)); printf("\n"); // factor += 1 IncInPlace(factor, sizeof(factor)); } return 0; } 

Выход ( идеал ):

 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800 11! = 39916800 12! = 479001600 13! = 6227020800 14! = 87178291200 15! = 1307674368000 16! = 20922789888000 17! = 355687428096000 18! = 6402373705728000 19! = 121645100408832000 20! = 2432902008176640000 21! = 51090942171709440000 22! = 1124000727777607680000 23! = 25852016738884976640000 24! = 620448401733239439360000 25! = 15511210043330985984000000 26! = 403291461126605635584000000 27! = 10888869450418352160768000000 28! = 304888344611713860501504000000 29! = 8841761993739701954543616000000 30! = 265252859812191058636308480000000 31! = 8222838654177922817725562880000000 32! = 263130836933693530167218012160000000 33! = 8683317618811886495518194401280000000 34! = 295232799039604140847618609643520000000 35! = 10333147966386144929666651337523200000000 36! = 371993326789901217467999448150835200000000 37! = 13763753091226345046315979581580902400000000 38! = 523022617466601111760007224100074291200000000 39! = 20397882081197443358640281739902897356800000000 40! = 815915283247897734345611269596115894272000000000 41! = 33452526613163807108170062053440751665152000000000 42! = 1405006117752879898543142606244511569936384000000000 43! = 60415263063373835637355132068513997507264512000000000 44! = 2658271574788448768043625811014615890319638528000000000 45! = 119622220865480194561963161495657715064383733760000000000 46! = 5502622159812088949850305428800254892961651752960000000000 47! = 258623241511168180642964355153611979969197632389120000000000 48! = 12413915592536072670862289047373375038521486354677760000000000 49! = 608281864034267560872252163321295376887552831379210240000000000 50! = 30414093201713378043612608166064768844377641568960512000000000000 51! = 1551118753287382280224243016469303211063259720016986112000000000000 52! = 80658175170943878571660636856403766975289505440883277824000000000000 53! = 4274883284060025564298013753389399649690343788366813724672000000000000 54! = 230843697339241380472092742683027581083278564571807941132288000000000000 55! = 12696403353658275925965100847566516959580321051449436762275840000000000000 56! = 710998587804863451854045647463724949736497978881168458687447040000000000000 57! = 40526919504877216755680601905432322134980384796226602145184481280000000000000 58! = 2350561331282878571829474910515074683828862318181142924420699914240000000000000 59! = 138683118545689835737939019720389406345902876772687432540821294940160000000000000 60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000 61! = 507580213877224798800856812176625227226004528988036003099405939480985600000000000000 62! = 31469973260387937525653122354950764088012280797258232192163168247821107200000000000000 63! = 1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000 64! = 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000 65! = 8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000 66! = 544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000 67! = 36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000 68! = 2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000 69! = 171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000 70! = 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000 71! = 850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000 72! = 61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000 73! = 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000 74! = 330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000 75! = 24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000 76! = 1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000 77! = 145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000 78! = 11324281178206297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000 79! = 894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000 80! = 71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000 81! = 5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000 82! = 475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000 83! = 39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000 84! = 3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000 85! = 281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000 86! = 24227095383672732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000 87! = 2107757298379527717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000 88! = 185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000 89! = 16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000 90! = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000 91! = 135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000 92! = 12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000 93! = 1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000 94! = 108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000 95! = 10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000 96! = 991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000 97! = 96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000 98! = 9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000 99! = 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 
  private static void problem20() { string muliplent = "100"; for (int i = 99; i > 1; i--) { muliplent = getproduct(muliplent, i); } int sum = 0; char[] result=muliplent.ToCharArray(); int count = muliplent.ToCharArray().Count(); for (int j = 0; j < count; j++) { sum = sum + (result[j] - '0'); } Console.WriteLine("sum is {0}", sum); Console.ReadLine(); } private static string getproduct(string multiplent, int multiplier) { StringBuilder str = new StringBuilder(); int product = 0; int remainder = 0; int dividend = 0; char[] c = multiplent.ToCharArray(); for (int i = c.Count() - 1; i >= 0; i--) { product = (((c[i] - '0') * multiplier) + dividend); remainder = product % 10; dividend = product / 10; if (i != 0) { str.Insert(0, remainder); } } str.Insert(0, product); return str.ToString(); }