Informatică, întrebare adresată de ionutg38, 9 ani în urmă

Poate cineva sa-mi dea un algoritm EFICIENT din punct de vedere al timpului de executie (eventual program C++) pentru a calcula suma cifrelor tuturo
numerelor de la 1 la n (unde n<=2.000.000.000). Am nevoie de el pentru rezolvarea unei probleme si algoritmul clasic (brut) consuma foarte mult timp.
Multumesc mult pentru ajutor!
Am cerut SUMA CIFRELOR tuturor numerelor de la 1 la n. De exemplu, daca n=15 avem de calculat suma cifrelor fiecarui numar de la 1 la 15, adica 1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+(1+2)+(1+3)+(1+4)+(1+5)=60.
ATENTIE!!!
Inainte de a va repezi sa raspundeti, cititi cu mare atentie cerinta. Nu raspundeti aiurea.
Prefer sa-mi raspunda blindseeker90 pentru ca el a inteles ce-am cerut. Am avut postata intrebarea si ieri, dar n-a mai avut cum sa-mi raspunda pentru ca jaketonery s-a grabit si mi-a dat un raspuns aiurea.


blindseeker90: Raspunsul corect este cel postat aici.
blindseeker90: Cel pe care l-ai pus acum 12 ore

Răspunsuri la întrebare

Răspuns de blindseeker90
3
#include <iostream>
#include <cmath>
#include <time.h>
using namespace std;

int nr_cifre(int n){
int nr=0;
while(n>0){
nr++;
n=n/10;
}
return nr;
}
double s=0;


double suma_cifre(int n){
int i,d,p,c,k=0;

if(n<10){
return n*(n+1)/2;
}
//numarul d reprezinta nr cifre-1, adica intervalul acela 1-999
d=nr_cifre(n)-1;
int a[12];
a[0]=0;
a[1]=45;
for(i=2;i<=d;i++){
a[i]=a[i-1]*10+45*ceil(pow(10,i-1));
}
p=ceil(pow(10,d));
//c este prima cifra din sir
c=n/p;
return c*a[d]+p*(c-1)*c/2+c*(1+n%p)+suma_cifre(n%p);

}
//-----------------------------------------------
int suma_cifre_nr(int n){
double s=0;
while(n>0){
s=s+n%10;
n=n/10;
}
return s;
}
//metoda de calcul brut clasica
double suma_cifre_calc_brut(int n){
int i;
double suma=0;
for(i=1;i<=n;i++){
suma=suma+suma_cifre_nr(i);
}
return suma;
}


int main(){

int n;
double time1,time2;
cin>>n;
clock_t start=clock();
cout<<"Suma cifre: "<<suma_cifre(n)<<endl;
clock_t end=clock();
time1=((double)(end-start)/CLOCKS_PER_SEC)*100000;
start=clock();
cout<<"Suma cifre brut: "<<suma_cifre_calc_brut(n)<<endl;
end=clock();
time2=((double)(end-start)/CLOCKS_PER_SEC)*100000;
cout<<"Timp 1: "<<time1<<" Time 2: "<<time2<<endl;
cout<<"Algoritmul 1 este de "<<time2/time1<<" mai rapid decat algoritm brut";

return 0;
}

ionutg38: Vad ca nu merge pentru 1990848512
blindseeker90: Da asta ma depaseste. Are legatura cu dimensiunea tipului de date si nu stiu cat ar trebui pus. Sunt adunari facute in double, ar trebui sa reziste si la acele valori. Nu stiu ce se intampla
ionutg38: Nu stiu daca asta e motivul, dar daca e asa, voi modifica sa lucrez cu numere mari.
ionutg38: Algoritmul e bun, merge. Multumesc mult! Aveam eu alte erori in programul in care-l utilizez. Inca odata, multumesc!
Alte întrebări interesante