Question

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!
ATENTIE!
E a treia oara cand postez intrebarea. Cei care nu stiu raspunsul sa nu se mai bage.

Answer 1

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

//mai intai adunam intervalul acela 1-9999 inmultit cu prima cifra
s=s+c*a[d];
//si acum trebuie sa adunam si numerele de la 1 pana la c
//daca de exemplu am 5678, 5*(1-999) ar presupune ca prima cifra e mereu 1
//dar de fapt poate sa fie de la 1 la c
s=s+p*(c-1)*c/2;
//al treilea termen trebuie sa adune cifra c pentru toate numerele din intervalul c0000-n
//deci pentru 5678 ar fi de la 5000 pana la 5678 ca sa numaram aparitiile lui 5
//in formula de mai jos am 1+ pentru ca trebuie sa adaug si termenul 0, adica 5000
s=s+c*(1+n%p);
//si acum am luat totul in calcul, facem din nou suma respectiva
s=s+suma_cifre(n%p);
//algoritmul se va termina atunci cand ajungi la sub 10 si se va activa returnul de mai sus
return s;
}

//-----------------------------------------------
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 s;
}


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;
}