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.
Răspunsuri la întrebare
Răspuns de
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;
}
#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;
}
Alte întrebări interesante
Limba română,
9 ani în urmă
Istorie,
9 ani în urmă
Ed. muzicală,
9 ani în urmă
Matematică,
9 ani în urmă
Geografie,
9 ani în urmă
Limba română,
9 ani în urmă
Matematică,
9 ani în urmă