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

تاپیک خوبیه ! همه ی اون چیزایی که ilius.gnu درباره ی انتخاب نوع داده ی بهتر درسته ولی به نظرم اون تغییر مبناش درست نیست !!! فکر کنم تغییر مبنا کمکی به بهبود زمانی برنامه نمیکنه.

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

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

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

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