نظر خواهی برنامه ی فاکتوریل اعداد بزرگ

[daneshjo IT]

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

اما میخواستم از دوستان متخصص نظر خواهی کنم که این کد از نظر بهینه بودن چه طور است؟ آیا میشه کد را بهینه تر هم کرد؟
ممنون



#include<iostream.h>
#include<conio.h>
intmain()
{
clrscr();
int a[1500];
int i,f,c=0;
longint n;
cout<<"enter the number"<<"\n";
cin>>n;
a[0]=0;
for (i = 2; i < 1500; i++)
a[i] = 0;
a[1] = 1;
for (f = 1; f <= n; f++)
{
for (i = 1; i <1500; i++)
a[i] = f * a[i];
for (i = 1; i <1500; i++)
{
if (a[i] > 9)
{
a[i + 1] = a[i + 1] + a[i] / 10;
a[i] = a[i] % 10;
}
}
}
for (i =1499 ; i >= 1; i--)
{
if(a[i]!=0)
{
c=i;
break;
}
}
cout<<"the fact of this number is:";
for(i=c;i>=1;i--)
cout<<a[i];
getch();
return 0;
}

[chnoor]

ممنون از برنامه ولی میشه یه کم در موردش توضیح بدید که چرا عدد را بر 10 تقسیم می کنید:متفکر:

[M.S.A.]

این برنامه ، تمرین ما بود
من آن را با جاوا نوشته ام

[ilius.gnu]

عیب بسیار بزگش اینه که هر رقم رو (که از 9 بیشتر نیست) در یک int ذخیره میکنه و خیلی فضا اشغال میکنه. در خالی که int به اندازه 32 بیت جا اشغال میکنه و میتونه از منفی 2 به توان 31 تا 2 به توان 31 رو ذخیره کنه(که خیلی عدد بزرگیه). بهتره از short int استفاده کنید که 16 بیت جا میگیره. اما بهتر از اون اینه که محاسبات رو در مبنای غیر 10 (و یک عدد خیلی بزرگ) انجام بدید و آخرش موقع چاپ به مبنای 10 تبدیل کنید. مثلا از نوع unsigned short int استفاده کنید که رنجش 0 تا 65535 هست. بعد محاسبات(برای بدست آوردن فاکتوریل) رو بجای مبنای 10 در مبنای 65536 حساب کنید و آخرش موقه چاپ به مبنای 10 تبدیل کنید (البته این ممکنه زمان کل محاسبه رو افزایش بده).
در ضمن اگه با ++C مینوشتید می‌تونستید بجای یک آرایهٔ معمولی از شیء vector استفاده کنید، البته زیاد در موردش اطلاع ندارم ولی فکر می‌کنم راحت‌تر و انعطاف‌پذیرتر بشه.

[danyali]

با تشكر بسيار
اما اين برنامه فاكتوريل رو تا اعداد چند رقمي حساب مي‌كنه ؟؟؟؟؟؟

[mohammadzarei]

با تشكر بسيار
اما اين برنامه فاكتوريل رو تا اعداد چند رقمي حساب مي‌كنه ؟؟؟؟؟؟
هر رقمی که دلمون بخواد؟

[qwerty11]

سلام بر دوستان گرامیییییی !!

تاپیک خوبیه ! همه ی اون چیزایی که ilius.gnu (http://barnamenevis.org/forum/member.php?u=71470) درباره ی انتخاب نوع داده ی بهتر درسته ولی به نظرم اون تغییر مبناش درست نیست !!! فکر کنم تغییر مبنا کمکی به بهبود زمانی برنامه نمیکنه.

یکی از دوستان هم با کلاس BigInteger جاوا نوشته بودن که وقتی که n یه کم بزرگ بشه نمیتونه کارایی زیادی داشته باشه !! و در ضمن در موقع تحویل دادن به استاد هم به نظرم باید برگشت بخوره !!

راه حلی که من دارم :

یه کلاس BigNumber تعریف کن و متد ضرب دو تا عدد Big رو براش پیاده سازی کن !! البته جوری پیاده سازی کن که دیگه مجبور نباشی متد جمع دوتا BigInteger رو بنویسی ! تقریبا مشابه همون کاری که خودت انجام دادی. ضرب دو عدد n رقمی و m رقمی پیچیدگی زمانی m*n داره (البته راههای سریعتری هم هست). حالا اگه ما بخوایم از عدد 1 شروع کنیم و بخوایم اعداد رو یکی یکی تو هم ضرب کنیم هر دفعه عدد حاصل بزرگتر میشه و باید برای این عدد بزرگ ضرب بعدی رو انجام بدیم. اگه بیایم تمام اعداد بین 1 تا n رو توی یه صف اولویت یا همون PriorityQueue بریزیم و مقاسیه ی اعداد بین طولهاشون باشه و هر بار دوتا از اعداد که طول کمتری دارن رو انتخاب کنیم و تو هم ضربشون کنیم و حاصل رو به صف اولویت اضافه کنیم ، اینجوری تعداد اعمال خیلی کمتری انجام میدیم !! البته چون n خیلی زیاد نمیتونه باشه میشه به جای صف اولویت از یه آرایه استفاده کرد و هربار آرایه رو بر حسب طول اعداد داخلش مرتب کرد.

من خودم با این روش بالا برنامه ای با جاوا برای اعداد Big نوشتم که فاکتوریل عدد !1234 رو توی 0.1 ثانیه ، عدد !4000 رو توی 1.3 ثانیه و عدد 9999! که یه عدد 35656 رقمیه رو توی کمتر از 20 ثانیه حساب میکنه !!

[safir_na]

سلام..
می دونم که جاش نیست این سوالو بپرسم..
ولی اگه معرفت به خرج بدین و جواب بدین خیلی حال دادین..
می شه برنامه رو کامل توضیح بدین؟؟این برنامه رو استادم گفته بنویسم..ولی منطقشو نمی فهمم..اون حلقه هارو نمی فهمم چی کار می کنن دقیقا..

مرسی..
از کسی هم که برنامه رو نوشته تشکر می کنم..:بوس:

[mohsensaghafi]

ممنون از برنامه ولی میشه یه کم در موردش توضیح بدید که چرا عدد را بر 10 تقسیم می کنید:متفکر:

سلام دوست عزیز.
این دوستمون دارن هر رقم از حاصل فکتوریل رو تو یه خونه از حافظه نگه می دارن. بعد از اینکه ضرب انجام شد و چون دارن ضرب رو دستی انجام می دن، در واقع دارن 10 بر یکی رو که ما در ضرب دستی به رقم بعد منتقل می کنیم رو منتقل می کنن.

[mohsensaghafi]

عیب بسیار بزگش اینه که هر رقم رو (که از 9 بیشتر نیست) در یک int ذخیره میکنه و خیلی فضا اشغال میکنه. در خالی که int به اندازه 32 بیت جا اشغال میکنه و میتونه از منفی 2 به توان 31 تا 2 به توان 31 رو ذخیره کنه(که خیلی عدد بزرگیه). بهتره از short int استفاده کنید که 16 بیت جا میگیره. اما بهتر از اون اینه که محاسبات رو در مبنای غیر 10 (و یک عدد خیلی بزرگ) انجام بدید و آخرش موقع چاپ به مبنای 10 تبدیل کنید. مثلا از نوع unsigned short int استفاده کنید که رنجش 0 تا 65535 هست. بعد محاسبات(برای بدست آوردن فاکتوریل) رو بجای مبنای 10 در مبنای 65536 حساب کنید و آخرش موقه چاپ به مبنای 10 تبدیل کنید (البته این ممکنه زمان کل محاسبه رو افزایش بده).
در ضمن اگه با ++C مینوشتید می‌تونستید بجای یک آرایهٔ معمولی از شیء vector استفاده کنید، البته زیاد در موردش اطلاع ندارم ولی فکر می‌کنم راحت‌تر و انعطاف‌پذیرتر بشه.

سلام دوست عزیز.
من هم با تغییر نوع متغیر موافقم. تغییر مبنا هم ایده جالبی هستش اما من با اون مبنایی که گفتید مخالفم. چون در این برنامه اون مبنا محاسبات رو پیچیده تر می کنه برای تغییر مبنا. من مبنای 10000 رو پیشنهاد می کنم. چون هم در اون رنجی که شما گفتید جا می شود و یک مزیت بسیار بزرگی که دارد و این کاهش رنج عدد (از 10000 تا 65535) رو جبران می کنه اینه که نیازی به تغییر مبنا هم نداره. این طوری می تونید بازه جواب فاکتوریل رو تا 4 برابر ارقام قبلی افزایش بدید.
ولی ایده تغییر مبنا ایده خیلی جالبی بود. خیلی لذت بردم. دستتون درد نکنه.

[mohsensaghafi]

هر رقمی که دلمون بخواد؟

سلام دوست عزیز.
با این برنامه ما خیلی محدودیت داریم هنوز. این برنامه ماکزیمم عددی رو که قادره براش فاکتوریل رو حساب کنه 632 هست. یعنی عدد 633 هم یک رقم کم میاره. تازه این در حالی هست که شما از خونه صفر آرایه هم استفاده کنی. حالا وقت اون رسیده که این محدودیت رو کم کنی.

[mohsensaghafi]

سلام بر دوستان گرامیییییی !!

تاپیک خوبیه ! همه ی اون چیزایی که ilius.gnu (http://barnamenevis.org/forum/member.php?u=71470) درباره ی انتخاب نوع داده ی بهتر درسته ولی به نظرم اون تغییر مبناش درست نیست !!! فکر کنم تغییر مبنا کمکی به بهبود زمانی برنامه نمیکنه.

یکی از دوستان هم با کلاس BigInteger جاوا نوشته بودن که وقتی که n یه کم بزرگ بشه نمیتونه کارایی زیادی داشته باشه !! و در ضمن در موقع تحویل دادن به استاد هم به نظرم باید برگشت بخوره !!

راه حلی که من دارم :

یه کلاس BigNumber تعریف کن و متد ضرب دو تا عدد Big رو براش پیاده سازی کن !! البته جوری پیاده سازی کن که دیگه مجبور نباشی متد جمع دوتا BigInteger رو بنویسی ! تقریبا مشابه همون کاری که خودت انجام دادی. ضرب دو عدد n رقمی و m رقمی پیچیدگی زمانی m*n داره (البته راههای سریعتری هم هست). حالا اگه ما بخوایم از عدد 1 شروع کنیم و بخوایم اعداد رو یکی یکی تو هم ضرب کنیم هر دفعه عدد حاصل بزرگتر میشه و باید برای این عدد بزرگ ضرب بعدی رو انجام بدیم. اگه بیایم تمام اعداد بین 1 تا n رو توی یه صف اولویت یا همون PriorityQueue بریزیم و مقاسیه ی اعداد بین طولهاشون باشه و هر بار دوتا از اعداد که طول کمتری دارن رو انتخاب کنیم و تو هم ضربشون کنیم و حاصل رو به صف اولویت اضافه کنیم ، اینجوری تعداد اعمال خیلی کمتری انجام میدیم !! البته چون n خیلی زیاد نمیتونه باشه میشه به جای صف اولویت از یه آرایه استفاده کرد و هربار آرایه رو بر حسب طول اعداد داخلش مرتب کرد.

من خودم با این روش بالا برنامه ای با جاوا برای اعداد Big نوشتم که فاکتوریل عدد !1234 رو توی 0.1 ثانیه ، عدد !4000 رو توی 1.3 ثانیه و عدد 9999! که یه عدد 35656 رقمیه رو توی کمتر از 20 ثانیه حساب میکنه !!

سلام دوست عزیز.
این هم روش خیلی جالبی بود. ممنونم. ولی به نظر می رسه که یه جایی باز هم تعداد رقم کار رو برای نگهداری در صف مشکل کنه؟! این طور نیست؟!!!!!!

[mohsensaghafi]

سلام..
می دونم که جاش نیست این سوالو بپرسم..
ولی اگه معرفت به خرج بدین و جواب بدین خیلی حال دادین..
می شه برنامه رو کامل توضیح بدین؟؟این برنامه رو استادم گفته بنویسم..ولی منطقشو نمی فهمم..اون حلقه هارو نمی فهمم چی کار می کنن دقیقا..

مرسی..
از کسی هم که برنامه رو نوشته تشکر می کنم..:بوس:

سلام دوست عزیز.
برای اینکه این روش رو درست متوجه بشی یک بار دیگه با دقت یه عدد 4 رقمی رو تو یه عدد 4 رقمی دیگه ضرب کن و به دقت مراحلی رو که تو محاسبه دست دنبال می کنی بررسی کن. حتما به جواب سوالت خواهی رسید.
موفق و سر بلند

[nima898]

عیب بسیار بزگش اینه که هر رقم رو (که از 9 بیشتر نیست) در یک int ذخیره میکنه و خیلی فضا اشغال میکنه. در خالی که int به اندازه 32 بیت جا اشغال میکنه و میتونه از منفی 2 به توان 31 تا 2 به توان 31 رو ذخیره کنه(که خیلی عدد بزرگیه). بهتره از short int استفاده کنید که 16 بیت جا میگیره
اگه از متغیر byte استفاده بشه حجم کمتری رو اشغال میکنه(یک بایت برای هر رقم)

هزار فاکتوریل رو با برنامه ای که نوشتم محاسبه کردم یه عدد 2568 رقمی که میشه:
40238726007709377354370243392300398571937486421071
46325437999104299385123986290205920442084869694048
00479988610197196058631666872994808558901323829669
94459099742450408707375991882362772718873251977950
59509952761208749754624970436014182780946464962910
56393887437886487337119181045825783647849977012476
63288983595573543251318532395846307555740911426241
74743493475534286465766116677973966688202912073791
43853719588249808126867838374559731746136085379534
52422158659320192809087829730843139284440328123155
86110369768013573042161687476096758713483120254785
89320767169132448426236131412508780208000261683151
02734182797770478463586817016436502415369139828126
48102130927612448963599287051149649754199093422215
66832572080821333186116811553615836546984046708975
60290095053761647584772842188967964624494516076535
34081989013854424879849599533191017233555566021394
50399736280750137837615307127761926849034352625200
01588853514733161170210396817592151090778801939317
81141945452572238655414610628921879602238389714760
88506276862967146674697562911234082439208160153780
88989396451826324367161676217916890977991190375403
12746222899880051954444142820121873617459926429565
81746628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422614
39742869330616908979684825901254583271682264580665
26769958652682272807075781391858178889652208164348
34482599326604336766017699961283186078838615027946
59551311565520360939881806121385586003014356945272
24206344631797460594682573103790084024432438465657
24501440282188525247093519062092902313649327349756
55139587205596542287497740114133469627154228458623
77387538230483865688976461927383814900140767310446
64025989949022222176590433990188601856652648506179
97023561938970178600408118897299183110211712298459
01641921068884387121855646124960798722908519296819
37238864261483965738229112312502418664935314397013
74285319266498753372189406942814341185201580141233
44828015051399694290153483077644569099073152433278
28826986460278986432113908350621709500259738986355
42771967428222487575867657523442202075736305694988
25087968928162753848863396909959826280956121450994
87170124451646126037902930912088908694202851064018
21543994571568059418727489980942547421735824010636
77404595741785160829230135358081840096996372524230
56085590370062427124341690900415369010593398383577
79394109700277534720000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000000000000000
اینم فایلش :

[mhojjati]

لطفا یکی کمکم کنه....همین برنامه ولی ضربش جدا حساب میشه تفریقش جدا من نمیدونم باید چکار کنم؟؟؟؟؟:گریه::گریه::گریه: