IT şi electronică > Programare
100 factorial
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:
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:
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.
--- Terminare citat ---
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.
Navigare
[#] Pagina următoare
Du-te la versiunea completă