Ştiri:

Vă rugăm să citiţi Regulamentul de utilizare a forumului Scientia în secţiunea intitulată "Regulamentul de utilizare a forumului. CITEŞTE-L!".

Main Menu

100 factorial

Creat de automat, Martie 05, 2012, 11:29:27 PM

« precedentul - următorul »

0 Membri şi 1 Vizitator vizualizează acest subiect.

automat

Salut.
De curand am gasit o problema si anume : gasiti suma digitilor numarului 100 factorial.


#include<stdio.h>
#define k 1000

int main()
{
    unsigned m, n=15, tab[k], s=0, i, j, fact=1;
    for(i=1; i<=n; i++)
    fact*=i;                           // calculez factorialul numarului
    for(j=0; j<k; j++)
    {
        tab[k]=fact%10;           // in fiecare element al tabloului incepand cu elementul zero pun ultima cifra a factorialului calculat
        s+=tab[k];                   // in variabila s memorez suma digitilor factorialului calculat
        fact/=10;
    }
    printf("\n %d\n", s);
}

Pentru numere mici codul functioneaza, insa nu si pentru numere mari, de ex. 100.
Sfaturi ?  ???
multumesc.

mircea_p

#1
100 factorial este probabil prea mare pentru a fi stocat si manipulat ca intreg.
Ai idee cat de mare este numarul asta? Este de ordinul 10^158.
Cred ca trebuie sa gasesti o metoda care nu necesita calcularea si stocarea numarului ca atare.

automat

Deci sa inteleg ca ar fi trebuit sa-l stochez intr-un vector ?

tavy

#3
Tu ai declarat ,,fact" ca fiind de tip ,,unsigned", presupunând că compilatorul tău folosești 32 bit pentru int atunci cel mai mare ,,fact" va fi 4294967295, ceea ce este mult pre puțin. Poți merge ceva mai departe dacă compilatorul tău știe de tipul ,,long long" declarând ,,fact" ca ,,unsigned long long" caz în care poți ajunge la 18446744073709551615, oricum insuficient pentru 100!.
Poate problema trebuie abordată altfel decât să calculezi factorialul, deși nu văd acum cum.
Dacă totuși nu găsești altă soluție decât să calculezi factorialul atunci poate apelezi la o bibliotecă de genul http://gmplib.org/

Citat
GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface.

The main target applications for GMP are cryptography applications and research, Internet security applications, algebra systems, computational algebra research, etc.

GMP is carefully designed to be as fast as possible, both for small operands and for huge operands. The speed is achieved by using fullwords as the basic arithmetic type, by using fast algorithms, with highly optimised assembly code for the most common inner loops for a lot of CPUs, and by a general emphasis on speed.

mircea_p

Cum pentru a rezolva problema e suficient sa se cunosaca digitii rezultatului si nu numarul in sine, se pare ca o metoda ar fi sa calculezi produsul cu o rutina proprie, care stocheaza digitii rezultatului (si nu numarul in sine) cu o variabila de tip pointer.
Numarul de digiti ai lui 100! e sub 200 deci nu e o problema.
Aici e dat un cod pentru rutina de inmultire si apoi suma digitilor:
http://stackoverflow.com/questions/3837494/is-there-a-way-to-find-sum-of-digits-of-100
Vezi mai pe la mijloc, e un bloc de cod.

HarapAlb

Citat din: mircea_p din Martie 06, 2012, 12:04:15 AM
Cum pentru a rezolva problema e suficient sa se cunosaca digitii rezultatului si nu numarul in sine, se pare ca o metoda ar fi sa calculezi produsul cu o rutina proprie, care stocheaza digitii rezultatului (si nu numarul in sine) cu o variabila de tip pointer.
Rutina aia proprie e tot un mod de a calcula cu numar "infinit" de digiti. Interesant este sa calculezi fara sa stochezi numarul intreg.

mircea_p

Citat din: HarapAlb din Martie 06, 2012, 12:18:48 AM
Citat din: mircea_p din Martie 06, 2012, 12:04:15 AM
Cum pentru a rezolva problema e suficient sa se cunosaca digitii rezultatului si nu numarul in sine, se pare ca o metoda ar fi sa calculezi produsul cu o rutina proprie, care stocheaza digitii rezultatului (si nu numarul in sine) cu o variabila de tip pointer.
Rutina aia proprie e tot un mod de a calcula cu numar "infinit" de digiti. Interesant este sa calculezi fara sa stochezi numarul intreg.
Sper ca nu s-a inteles ca ar fi rutina mea.
Voiam sa spun ca nu e inclusa in limbaj ci trebuie sa o scrie cel ce vrea sa o foloseasca.

Rutina din exemplu face inmultirea la fel cum se face pe hartie.
Nu stiu ce vrei sa spui cu numarul infinit de digiti. Nu trebuie sa stocheze altceva decat intregi intre 0 si 9 in "sirul" la care se refera pointerul (cu lungimea maxim 255) si niste valori intermediare intregi (cu valori sub 100) in variabilele intermediare (digit, carry, etc).  etc.

HarapAlb

Rutina respectiva face acelasi lucru ca si biblioteca respectiva de calcul cu precizie arbitrara. Asa pot sa definesc o clasa "ExtralargeInteger" compusa din cativa long unsigned int pe care sa definesc operatiile de adunare, inmultire si sa manevrez intern transportul catre bitii semnificativi.

Intrebarea este daca poti calcula suma fara sa inmagazinezi digitii numarului.

tavy

O idee ar fi să elimini din produs numerele care nu afectează suma cifrelor.
Spre exemplu se pot elimina perechile 50*2, 25*4, 20*5, 10*1.
Se pot înlocui 30 cu 3, 40 cu 4, etc.
Se pot găsi și alte moduri de a reduce valoarea produsului.
În felul acesta nu este exclus să se ajungă ca produsul rămas să se încadreze într-un ,,unsigned" sau măcar într-un ,,long double".

AlexandruLazar

Din pacate, asta e mai mult o problema de matematica, nu de programare. Solutia la care se gandea mircea_p pare a fi cea corecta, si aici gasesti cateva link-uri la niste proprietati matematice care te-ar putea ajuta sa accelerezi timpul de calcul.

mircea_p

Citat din: HarapAlb din Martie 06, 2012, 06:26:38 AM
Rutina respectiva face acelasi lucru ca si biblioteca respectiva de calcul cu precizie arbitrara. Asa pot sa definesc o clasa "ExtralargeInteger" compusa din cativa long unsigned int pe care sa definesc operatiile de adunare, inmultire si sa manevrez intern transportul catre bitii semnificativi.
Se poate, nu stiu ce face rutina respectiva.
Idea din programul mi s-a parut simpla si eleganta, de aceea am supus-o atentiei.

Citat din: HarapAlb din Martie 06, 2012, 06:26:38 AM
Intrebarea este daca poti calcula suma fara sa inmagazinezi digitii numarului.
Dina pacate se pare ca nu, dupa ce am vazut pe net, pana acum. E o problema discutata pe multe forumuri. Idea de a reduce numarul de termeni eliminand pe cei care dau zerouri pare ca e insuficienta, chiar daca interesanta.

zec

De obicei ideea matematica in aceste probleme combina teoria numerelor si inegalitati.
Daca N este numarul si SN suma cifrelor numarului N atunci avem[tex]N\equiv S_N(mod9)[/tex] si cum [tex]N\equiv 0(mod9)[/tex] rezulta ca suma cifrelor e multiplu de 9.Ca sa aflam mai exact trebuie sa vedem intre ce valori l-am putea incadra.Prima inegalitate este sa aflam cate cifre are numarul 100! pentru acest calcul se poate folosi logaritmul zecimal
.Calculam lg(100!)=lg1+lg2+...+lg100 calculatorul poate usor sa faca suma aceasta.Rezultatul in parte intreaga reprezinta numerele de cifre adica [lg(100!)]=numarul de cifre.
Dupa ce sa calculat numarul de cifre care il are 100! ca sa facem calculele mai cu acuratete numaram cate zerouri avem.Aceasta problema se face mai usor ibcercand sa vedem cati de 5 apar ca factori primi in 100! si numaram cati de 5 apar in compunearea numerelor de la 1 la 100.
Numarul e dat de suma [100/5]+[100/52] care inseamna 24 de zerouri.
Deci avem [tex]m-24\le S_N\le 9(m-24)[/tex] .Deci SN e un multiplu de 9 cuprins intre aceste valori.De aici lucrurile se complica ,aceasta e prima forma de evaluare dar pentru a avea mai exact ar trebui sa cautam informatii despre ce fel de cifre apar in scrierea zecimala.Din pacate aceasta nu e o rezolvare completa si e doar o evaluare a acestei sume.

Electron

Citat din: zec din Martie 07, 2012, 12:17:17 PM
Daca N este numarul si SN suma cifrelor numarului N atunci avem[tex]N\equiv S_N(mod9)[/tex] si cum [tex]N\equiv 0(mod9)[/tex] rezulta ca suma cifrelor e multiplu de 9.
Ce inseamna asta: "[tex]N\equiv S_N(mod9)[/tex] "? Si cum ai ajuns la [tex]N\equiv 0(mod9)[/tex] ?

e-
Don't believe everything you think.

zec

E vorba de relatie de congruenta . a [tex]\equiv b[/tex] mod c daca c|a-b.N e congruent cu 0 caci e multiplu de 9.Prima congruenta e una cunoscuta.

Electron

Ok, am inteles. Merci pentru precizari.


e-
Don't believe everything you think.