一个很有趣的编程题

碰巧和一个朋友聊到一个趣题

如何最好最快的方法求阶乘，也就是从1一直乘到n,

怎么样试试吧。




==================================================================================
一个很偶然的机会，谈到一个很有趣的编程题，阶乘的算法，阶乘是从1一直乘到n,刚听
到这个题，觉得很简单，用递归算法就可以搞定了，不过当来写这个代码的时候，才发觉
，原来自己想的过于简单，由于n是不确定的，所以这个数值可能非常的大，远远大于
我们的基本数据类型。那么怎样来表示这个数据结构了，一下就去思考这个方面的问题，
如果是这样想的，那你就是中圈套了，数据结构是根本就解决不了的，只有在算法上做文
章，那么应该是如何的算法了，其实就是最简单的9*9乘法口诀了，就可以搞定了。

觉得很过瘾，特记下来，算法是个很有趣的研究。一个清晰和简洁的算法大有耳目一新的感
觉。
==================================================================================

评论

16 楼 brilliant2008 2009-04-17  

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);
	}

}

15 楼 kunee 2009-04-07  

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

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

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

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

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

14 楼 yingwuhahahaha 2009-04-07  

xhanxhanxhan 写道

贴一个自己以前搞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;
}

郁闷，没看懂这个循环

13 楼 xhanxhanxhan 2009-04-06  

贴一个自己以前搞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;
}

12 楼 night_stalker 2009-04-04  

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

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

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

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

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

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

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

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

11 楼 sunnycare 2009-04-04  

这个优化是一个方面，还有一个方面就是大整数相乘的快速算法。
比如说：
将一个大整数记为（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步乘法。快了很多。

10 楼 whaosoft 2009-04-03  

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

9 楼 kimmking 2009-04-03  

bonny 写道

阶乘计算是有公式的（近似）

即使这个公式的运算量也是非常的客观。

运算量跟阶乘比 几乎可以忽略~~

kimmking 写道

lshmouse 写道

kimmking 写道

qi是该质数的指数，可以用logpi(N)方法求得


这个是不对的

这个是有确定算法的

int q=0;
while(n>0){
   q+=n/p;
   n=n/p;
}

这个可以~~

如果不要求精确值，阶乘用【Stirling】最简单~~

8 楼 bonny 2009-04-03  

阶乘计算是有公式的（近似）

即使这个公式的运算量也是非常的客观。

7 楼 圆圆爸爸 2009-04-03  

具体的程序编码的伪代码是怎样的了

6 楼 kimmking 2009-04-03  

lshmouse 写道

kimmking 写道

qi是该质数的指数，可以用logpi(N)方法求得


这个是不对的

这个是有确定算法的

int q=0;
while(n>0){
   q+=n/p;
   n=n/p;
}

这个可以~~

如果不要求精确值，阶乘用Stirling最简单~~

5 楼 lshmouse 2009-04-03  

kimmking 写道

qi是该质数的指数，可以用logpi(N)方法求得


这个是不对的

这个是有确定算法的

int q=0;
while(n>0){
   q+=n/p;
   n=n/p;
}

4 楼 圆圆爸爸 2009-04-02  

确实，最后是加法和乘法。

3 楼 kimmking 2009-04-02  

qi是该质数的指数，可以用logpi(N)方法求得


这个是不对的

2 楼 lshmouse 2009-04-02  

我的想法：
（1）最快的方法就是打一个表，然后去查询。就是有点不实际。
（2）1＊2＊3＊....*n = X,那么X＝(p1^q1)*(p2^q2)*....*(pk^qk)

k是小于X的质数的个数，pi是第i个质数，

qi是该质数的指数，可以用logpi(N)方法求得

pi^qi可以使用快速幂，复杂度是log2(qi)

回比直接算要快

1 楼 kimmking 2009-04-02  

圆圆爸爸 写道

碰巧和一个朋友聊到一个趣题

如何最好最快的方法求阶乘，也就是从1一直乘到n,

怎么样试试吧。




==================================================================================
一个很偶然的机会，谈到一个很有趣的编程题，阶乘的算法，阶乘是从1一直乘到n,刚听
到这个题，觉得很简单，用递归算法就可以搞定了，不过当来写这个代码的时候，才发觉
，原来自己想的过于简单，由于n是不确定的，所以这个数值可能非常的大，远远大于
我们的基本数据类型。那么怎样来表示这个数据结构了，一下就去思考这个方面的问题，
如果是这样想的，那你就是中圈套了，数据结构是根本就解决不了的，只有在算法上做文
章，那么应该是如何的算法了，其实就是最简单的9*9乘法口诀了，就可以搞定了。

觉得很过瘾，特记下来，算法是个很有趣的研究。一个清晰和简洁的算法大有耳目一新的感
觉。
==================================================================================

lz很强悍啊，
-------------------
文章: 0
积分: 70
来自: 深圳