فاکتوریل یک عدد خیلی بزرگ

[parnian~parnian]

سلام
من یک برنامه به زبان java object oriented نوشتم ولی کامپایلر ی که باید accept کنه داور acm است . مشکل من این جا است :برنامه من درسته !!! ولی acm خطای rang answer میده .این برنامه محاسبه تعداد رقم های فاکتوریل عددیه که کاربر وارد میکنه داخل سوال نوشته عدد باید بین 1و 10 به توان 7 باشه ولی همون جوری که دوستان میدونن نهایت یک عدد بزرگ میتونه از نوع longباشه که اونم نمیتونه فاکتوریل عددی مثل 10 به توان 7 رو حساب کنن .اگه کسی راه حلی داره ممنون میشم اگه بهم بگین .

[HuNTeR@bn]

سوال های این تیپی معمولا جوابشون اونی نیست که به نظر میاد
مثلا مطئنا اینجا نباید فاکتوریل رو حساب کنی بعد تعداد رقم هاشو بشمری
با کلاس BigInteger می تونی یه همچین اعدادی رو نگه داری ولی خوب مطمئنا با این اعداد به این بزرگی time limit با out of memory خواهد شد
پس به یه الگوریتم فکر کن که تعداد رقم هارو بشمره نه جواب فاکتوریل رو

[parnian~parnian]

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

[HuNTeR@bn]

اینجارو یه نگاه بنداز:
http://en.wikipedia.org/wiki/Factorial

The logarithm of the factorial can be used to calculate the number of digits in a given base the factorial of a given number will take.

[excelable]

سلام
من برای اینکه اثبات کنم برنامه ی اکسل همچنان بی نظیر و پر قدرت ترینه، چند ساعت وقت گذاشتم و با استفاده از ویژوال بیسیک در اکسل2007، برنامه ای نوشتم که بتونه فاکتوریل اعداد بزرگ رو محاسبه کنه.
این برنامه تنها یک محدودیت داره: فقط می تونه فاکتوریل اعدادی رو محاسبه کنه که تعداد رقم های جواب نهایی فاکتوریل آن عدد، کوچک تر از شانزده هزار باشه(16000). یعنی اگر جواب نهایی فاکتوریل، یه عدد شانزده هزار رقمی باشه(یا کمتر)، می تونه اون فاکتوریل رو محاسبه کنه.
فکر کنم همین قدرش هم برای سوت کشیدن مخ کافی باشه! اما تو فکرم که برنامه رو ارتقا بدم تا جواب های یک ملیون رقمی رو هم پیدا کنه.
یک نکته ی دیگه هم اینکه اگر عدد بزرگ باشه، برای محاسبه ی جواب باید مدتی صبر کنید که بستگی به بزرگی عددتون داره؛ ولی مطمئن باشید که اکسل جواب رومحاسبه می کنه.
سعی می کنم یه کمی اصلاحات روش انجام بدم و بعد بگذارمش روی وبلاگم.
اگه زودتر خواستید اون رو، یه ایمیل بزنید تا بفرستم خدمتتون.
http://www.excelable.blogfa.com/
excelable@gmail.com

[rezaTavak]

سلام

یه همچنین چیزی خیلی طول میکشه.

کدی که من نوشتم اما بهینه نشده است:



import java.math.BigInteger;

public class Factorial1 {
public static void main(String[] args) {
String i = args[0];
System.out.println(i+"!=" + factorial(new BigInteger(i)));

}

public static BigInteger factorial(BigInteger n) {
BigInteger bigN = new BigInteger(String.valueOf(n));
for( int i = new Integer(n.toString()).intValue() - 1 ; i > 1 ; i--)
bigN = bigN.multiply(new BigInteger(new Integer(i).toString()));

return bigN;
}
}


البته تابع بازگشتی فقط تا ۹۷۰۵ جواب میده و بیشتر از اون باید با حلقه باشد. اینم فاکتوریل ۴۰۰۰۰ در فایل ضمیمه.

ماشین حساب kcalc هم هر عددی را میتونه محاسبه کنه مثلا آخرین چیزی که شما می‌خواهید ده میلیون است که 1.20242340052e+65657059 میشه. یعنی ۶۵ میلیون رقم داره. البته محاسبه اش ۲۰ ثانیه طول کشید.