2005年7月17日星期日

求大数的阶乘

昨天看到博客园的一篇文章《10000的阶乘的算法(大数的阶乘)》,自己也想了一下,写了一个 C# 版的。程序也比原文的要简单。

原文中,数组大小 M = log10^1+log10^2+log10^3...+log10^n,好像不对。我觉得应该是 M = log10(1) + log10(2) + ... + log10(n),log10(1) 表示以10为底数、1为真数的对数。可能我们表达的是一个意思,只是写法不同而已(不过我还是觉得10^3 = 1000,log10^3 = 3,这样明显不对嘛)。

程序:

using System;

namespace Factorial
{
class Class1
{
[STAThread]
static void Main(string[] args)
{
int n, M, carry = 0, t1;
double t2 = 0;
bool display = false;
int[] result;

Console.Write("Input the number you want to factorial: ");
n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("");

for (int i = 1; i <= n; i++)
t2 += Math.Log(i, 10);
M = (int)Math.Ceiling(t2);

result = new int[M];
result[0] = 1;

for (int i = 1; i <= n; i++)
for (int j = 0; j < M; j++)
{
t1 = result[j] * i + carry;
result[j] = t1 % 10;
carry = (t1 - result[j]) / 10;
}

Console.WriteLine("The result is: ");
for (int i = M - 1; i >= 0; i--)
{
if (result[i] != 0 && !display)
display = true;
if (display)
Console.Write(result[i]);
}

Console.ReadLine();
}
}
}

用 Windows XP 自带的计算器验算了一下,1000! 应该是没问题的,但算 10000! 确实算不出来,要等很久。原文的那个程序也是要等很久,而 Windows 自带计算器只等了 1 秒钟左右。我想,要不然是 Calc 省略了后面的位数,要不然是 Calc 有更好的算法。

小程序,轻松一下。:-)

没有评论: