一个很有趣的编程题

这是个什么公司啊 你面的是初级程序员吗??

这个优化是一个方面，还有一个方面就是大整数相乘的快速算法。
比如说：
将一个大整数记为（a*10^n+b)*(c*10^n+d)=ac*10^(2n)+db+(ad+bc)*10^n，这样算要4步乘法。（b和d都小于10^n）
你也可以这样算：（a*10^n+b)*(c*10^n+d)=ac*10^(2n)+db+((d-c)(a-b)+ac+bd)*10^n  ,这样只要3步乘法。快了很多。

各种优化算法都写在书上，也没什么好讨论的……

用haskell就很简单，内建无限长整数支持，编译成可执行文件速度也非常快。

我的机器上算60000的阶乘也就几秒钟，和输出结果耗的时间差不多(好长的数字啊)。

factorial 0 = 1
factorial n = n * (factorial (n-1))
main = print (factorial 60000)

最后……其实还有更简单的：

main = print (product [1..60000])

实际应用上，算更大的数的阶乘时，我们往往不需要这么多有效数字，用Stirling公式算出位数就够了。
还有一种情况是算余数的，麻烦点，乘几步求余一次。这两种情况往往都用不着 BigInteger..

速度往往也是没必要的，一般这个东西只算一遍……

贴一个自己以前搞ACM时候收藏的代码
求1000！ 数据无限大，只要不超过存储空间就行。哈哈。

#include<stdio.h>
long s[1000]={1,1},n=20,t=2,a=1,b=0;
int main()
{
        for(;a<=*s||(++t<=n?(b=0,a=1):0);(*s==a++&&b)?(*s)++:0)
                b+=s[a]*t,s[a]=b%10000,b/=10000;
        for(printf("%d",s[*s]);--*s>0;)printf("%04d",s[*s]);
        return 0;
}

郁闷，没看懂这个循环

哈哈，偶当年这个题目是这样做的。

因为N可能很大，大到计算机基本单元无法存储。

第一部要解决在内存中的问题，用了个字符串数组存几位到几位。

第二步肯定是用加法来做，乘法实在太慢了

第三步，因为在字符串中处理，核心算的那步有一个求余，计算很慢，直接用汇编嵌入计算。。

public class TestMain {
/*
 * 计算从a到b的连续乘积
 * */
	public static int play(int a, int b) {
		if (a <= b && a > 0 && b > 0) {
			if (b < a) {
				return 1;
			} else {
				return b * play(a, b - 1);
			}
		} else {
			return 1;
		}
	}

	public static void main(String[] args) {
		int a = play(1, 5);
		System.out.println("结果是："+a);
	}

}