اشکال این کد چیه؟

[raaaaz]

در [n,1]برنامه­ای بنویسید که عدد n را از کاربر گرفته و تعداد کاراکترهای مورد نیاز نوشتن اعداد nتا1 را محاسبه نموده و در خروجی چاپ نماید.

من کد رو اینجوری نوشتم اما نمیدونم چرا کامل نیست؟؟؟؟؟!!!!
int main()
{long double sum=0;
long double a;
cin>>a;
long double h=a;long double x;
int d=0;
int e=0;
long double t[100000]={0};
while(h>0){
x=h;
while(1)
{
h/=10;
d++;
if(h<1){t[e]=d;h=x;d=0;e++;break;}
}h--;
}
for(int c=0;c<e;c++)
sum+=t[c];
cout<<sum;
delete t;

getch();
return 0;}

[Salar Ashgi]

اگر اونطور که من برداشت کردم باشه ، کدتون رو خیلی پیچیده کردید !
طبق گفته شما مثلا واسه n=12 خواهد شد :
1تا 9 = 9
+
10=2
11=2
12=2
9+6= 15
کد (مثال) نمونه :


#include <iostream>
#include <conio>
#include <math>
int len(int n){
return 1+floor(log10(n));}
//------------------------
int Find(int n){
int sum=0;
for(int i=1;i<=n;i++)
sum+=len(i);
return sum;}
//-----------------------
int main(){
int n;
cout<<"Enter n :\n";
cin>>n;
cout<<Find(n)<<endl;
getch();
}


http://salarcpp.persiangig.com/new_folder_4/2/pic.png

موفق باشید ./

[raaaaz]

خیلی ممنون!چه کد جمع و جوری !
فقط من یه اشتباهی تو سوال کردم: برنامه باید تا 1000000000000000 جواب بده....

[beginner1010]

واسه اینکه تایم اوت نشه می تونید از داینامیک پروگرمینگ (dynamic programming)
استفاده کنید این کد منه با پیچیدگیه O (d * 2 * 9) l
یا همون (O (d که d تعداد رقمه پس حداکثر 4608 عملیات انجام میشه
از define ها استفاده نکردم که گیج نشید !
اینم کدمه :

]




#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <map>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <functional>
#include <cstdio>
#include <ctime>

using namespace std ;

#define eps 1e-10
#define ll long long
#define ld long double
#define ull unsigned long long
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REV(i,k,n) for(int i=k;i>=n;i--)
#define SZ(x) ((int)x.size())
#define INF (1 << 29)
#define DB(x) { cerr << #x << " = " << x << endl ; }
#define all(x) x.begin(),x.end()

long long dp [22][2] ;
int split [22] ;
int L , lenght ;

long long rec (int pos,int big) {
if (pos == lenght) return 1 ;
if (~dp [pos][big]) return dp [pos][big] ;
long long &res = dp [pos][big] = 0 ;
if (lenght == L) {
int limit = 9 ;
if (big || pos == 0) limit = split [pos] ;
long long aux = 1 ;
for (int I = (pos == 0 ? 1 : 0) ; I <= limit ; I ++) {
int nextBig = 0 ;
if (I == limit && (big || pos == 0)) nextBig = 1 ;
aux = rec (pos + 1,nextBig) ;
res += aux ;
}
}else {
long long aux = 1 ;
for (int i = (pos == 0 ? 1 : 0) ; i <= 9 ; i ++) {
aux = rec (pos + 1,big) ;
res += aux ;
}
}
return res ;
}

int main () {
freopen ("in.in","r",stdin) ;
long long n , x , ans = 0 ;
cin >> n ;
x = n ;
L = 0 ;
do {split [L ++] = x % 10 ; x /= 10 ;}while (x) ;
reverse (split,split + L) ;
for (int k = 1 ; k <= L ; k ++) {
lenght = k ;
memset (dp,-1,sizeof (dp)) ;
ans += rec (0,0) * (long long)k ;
}
printf ("%lld\n",ans) ;
}


راستی این توی visual studio اجرا میشه نه توربو سی

[beginner1010]

من یک الگوریتم دیگه هم به ذهنم رسید
که با حداکثر 18 عملیات جواب رو پیدا می کنه :متفکر:




#include <iostream>
using namespace std ;
int main () {
freopen ("in.in","r",stdin) ;
long long n , x , ans = 0 ;
cin >> n ;
x = n ;
int L = 0 ;
do {L ++ ; x /= 10 ;}while (x) ;
long long pre = 1 , last = 0 ;
for (int k = 1 ; k <= L ; k ++) {
pre = last ;
if (k == L) last = n ;
else last = last * 10 + 9 ;
ans += (last - pre) * k ;
}
printf ("%lld\n",ans) ;
}

[Salar Ashgi]

فقط من یه اشتباهی تو سوال کردم: برنامه باید تا 1000000000000000 جواب بده....

تو این حالت باید از کلاس اعداد بزرگ استفاده کنید ./ (البته این معمول ترین راه هستش وگرنه میشه بطریقی با آرایه ها
هم کارو انجام داد)


از define ها استفاده نکردم که گیج نشید !

کد صحیح هر فردی برای خودش محترم است ولی این کدی که شما نوشته اید با این همه فایل کتابخانه ای و ...
برای این دوستمون که احتمالا در ابتدای راه هستن کمی مبهم و گیج کننده خواهد بود .

موفق باشید ./

[beginner1010]

تو این حالت باید از کلاس اعداد بزرگ استفاده کنید ./ (البته این معمول ترین راه هستش وگرنه میشه بطریقی با آرایه ها
هم کارو انجام داد)
موفق باشید ./

فکر نمی کنم نیازی باشه 1000000000000000 توی long long جا میشه

[Salar Ashgi]

فکر نمی کنم نیازی باشه 1000000000000000 توی long long جا میشه


بعید میدونم ، ولی اگر باز ممکن هم باشد ، به احتمال بسیار زیاد محاسبات اشتباه خواهد بود ؛
راه ذکر شده انعطاف و کارایی بالایی دارد ./

[beginner1010]

بعید میدونم ، ولی اگر باز ممکن هم باشد ، به احتمال بسیار زیاد محاسبات اشتباه خواهد بود ؛
راه ذکر شده انعطاف و کارایی بالایی دارد ./ مشکلی بابت محاسبات نخواهد بود
منظورتون از راه ذکر شده این
"تو این حالت باید از کلاس اعداد بزرگ استفاده کنید ./ (البته این معمول ترین راه هستش وگرنه میشه بطریقی با آرایه ها
هم کارو انجام داد)" هستش ؟

[Salar Ashgi]

مشکلی بابت محاسبات نخواهد بود
لطفا" تست نکرده ، مطلبی ذکر نکنید !

کد زیر برای محاسبه فاکتوریل یک عدد را داشته باشید :


#include <iostream>
#include <conio>
typedef unsigned long int Uint;
//---------------
Uint fact(Uint n){
Uint f=1;
for(Uint i=1;i<=n;i++)
f*=i;
return f;}
//---------------
int main(){
for(Uint i=1;i<=30;i++)
cout<<i<<" : "<<fact(i)<<endl;
getch();
}
با این کد ما فاکتوریل اعداد از 1 تا 30 را میخواهیم چاپ کنیم با در نظر گرفتن این نکته که از نوع داده ای بی علامت(ظرفیت بزرگ) استفاده نموده ایم !
خروجی کد :
65828
همانطور که دیده میشود در محاسبه !13 اشتباه رخ داده هست (حالا دلیل این اشتباه هم واضح هست)
چراکه نتیجه واقعی !13 برابر است با 6227020800 .



منظورتون از راه ذکر شده این هستش
بله ./

[beginner1010]

آقای محترم من اکثر پست ها و جوابهای شما رو که نگاه می کردم یه جوری برخورد می کنید انگار با همه دعوا دارید ( شاید برداشت من غلطه! )

من گفتم "long long " نه " unsigned long" !!!

و یه توضیح که خیلی ها می دونن : long long تا 2^64 جواب میده پس 10^15 توش جا میشه
خب در مورد اینکه گفتید راه حلتون انعطاف و کارایی بالایی داره ، چرا یک بار برنامتون و برنامه ی منو اجرا نمی کنید تا نتیجه رو ببینید
برنامه ی من با( O( logn
اما برنامه شما با( O ( n پس اینجوری که شما می گید برنامه انعطاف پذیره اگر هر عملی هم بگیم یک میکرو ثانیه طول بکشه برنامه شما هم فقط 10 عمل انجام بده 300 سال طول می کشه اما برنامه ای که من گذاشتم کمتر از 1 میلی ثانیه جواب خواهد داد .