指点 n! 阶乘。 随便散分！

Question

前两天在C#版看到一个计算1000！的帖子说的不错。所以自己写了也写一个java版的，借鉴并改造了一下。希望大家提出宝贵意见，指出改进方案！原贴忘了，不好意思!Bolg：http://blog.csdn.net/luojihaidao/archive/2009/04/13/4068536.aspx/**  
 * User: luoji  
 * Date: 2009-4-12  
 * Time: 10:01:06  
 */  
public class Factorial {   
    private final static int MAX_UPON = 100000000;   
    private final static int MAX_BIT = 8;   
  
    public static void main(String[] args) {   
        long a = System.currentTimeMillis();   
        System.out.println(Factorial.getValue(100));   
        long b = System.currentTimeMillis();   
        System.out.println(b - a);   
    }   
  
    public static String getValue(int n) {   
        long[] value = getArray(n);   
        StringBuffer buf = new StringBuffer();   
        int len = 0;   
        String sT;   
        for (int i = value.length - 2; i >= 0; i--) {   
            sT = String.valueOf(value[i]);   
            len = MAX_BIT - sT.length();   
            for (; len > 0 && i != value.length - 2; len--) {   
                buf.append("0");   
            }   
            buf.append(value[i]);   
        }   
        return buf.toString();   
    }   
  
    /***  
     * 用数组来记录数  
     * @param n  
     * @return  
     */  
    private static long[] getArray(int n) {   
        int len = (getBit(n) - 1) / MAX_BIT + 2;   
        long[] factorAarry = new long[len];   
        long c;   
        factorAarry[0] = 1;   
        int bit = 1, i;   
        for (; n > 1; n--) {   
            i = 0;   
            c = 0;   
            for (; i < bit; i++) {   
                long cV = n * factorAarry[i] + c;   
                factorAarry[i] = cV % MAX_UPON;   
                c = cV / MAX_UPON;   
            }   
            factorAarry[i] = c;   
            if (c > 0) {   
                bit++;   
            }   
        }   
        return factorAarry;   
    }   
  
    /***  
     *  得到n!的位数  
     * @param n  
     * @return  
     */  
    private static int getBit(int n) {   
        double result = 0;   
        for (int i = 1; i < n; i++) {   
            result += Math.log10(i);   
        }   
        result += 1.5;   
        return (int) Math.ceil(result);   
    }   
} 

Answer 1

测试结果：
请看Blog， 太长贴不出来。

Answer 2

public class JieChengWeiShuLing {
public static void main(String[] args){
System.out.println("请输入求阶乘的数：");//提示用户输入相应的数
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));//创建一个字符串暂存区对象br用于存放用户 输入的字符串
String s = null;//创建一String类的对象变量s并赋一空引用
try{
s = br.readLine(); //调用BufferedReader类中的实例方法readLine()来读取br所指的字符串并把引用赋给s
}
catch(IOException e){
e.printStackTrace();
System.out.println("出错了");
} //处理可能出现的异常
int parameter = Integer.parseInt(s);  //将字符串转换为整型数据
System.out.println(parameter+"!的结果是："+jieCheng(parameter));//输出阶乘的结果
System.out.println(parameter+"!的结果尾数中0的个数是："+weiShuLingGeShu(parameter));//输出阶乘结果尾数0的个数
}

public static int weiShuLingGeShu(int m) {//定义方法求尾数0的个数，返回值为int型
int count=0;
for(int i=1; i<=m; i++){
if(i%25 == 0)//如果100以内的某数含两个因子5，则结果会产生两个0，计数变量count加2
count+=2;
else if(i%5 == 0)//如果100以内的某数只含有一个因子5，则结果会产生一个0，计数变量count加1
count++;
}
return count;//返回求得的尾数0的个数
}

public static double jieCheng(int m){//定义方法求阶乘，返回值为double类型
if(m == 1)
return 1;//1的阶乘的结果是1
else
return m*jieCheng(m-1);//通过递归调用的方法求得阶乘的结果
}
}

Answer 3

想法不错， 不过对于阶乘，你不知道它有多少个0。所有int len = (getBit(n) - 1) / MAX_BIT + 2;   
        long[] factorAarry = new long[len];   这里的len已经是最小的了。  必须先new 这是已经占了内存了， 在判断是0不是0没有意义了吧。

Answer 4

public class Jc1000 {
public static void main(String[] args) {
BigInteger x = BigInteger.valueOf(1);
for (int i = 2; i <= 1000; i++) {
x = x.multiply(BigInteger.valueOf(i));
}
System.out.println(x);
}
}

Answer 5

本想飘过，但这个我做过，用C++写的，但思想是可以通用的，贴出来参考参考，我是采用模拟手算的方式来处理的，代码如下：
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int n;//阶乘数
void calc(char *p,int n);//计算阶乘数的函数
int getSize(int n);//计算阶乘的位数
void main(){
int size;
printf("n!? n=:");
scanf("%d",&n);
char *p;
size=getSize(n);//计算阶乘的位数
p=(char *)calloc(size,sizeof(char));//根据阶乘的位数分配空间
p[0]=1;//使字符数组初始化,最低位是1，其余全0
calc(p,n);//计算阶乘数的函数
for(int i=size-1;i>=0;i--)
printf("%d",p[i]);
}
int getSize(int n){
double size=1;
for(int i=1;i<=n;i++)//计算阶乘的位数,位数=log1+log2......+logn
size+=log10(i);
return (int)size;
}
void calc(char *p,int n){
double bitcount=1;//定义位数，开始为1位数
int add;
for(int i=2;i<=n;i++){
add=0;
bitcount=bitcount+log10(i);//得到当前位数
for(int j=0;j<bitcount;j++){
add+=i*p[j];//运算
p[j]=add%10;//低位放入数组
add=add/10;//高位参与下次运算
}
}
}

Answer 6

很恶心，居然在GOOGLE的浏览器上没有格式化，现在在IE下重贴上面的代码：
本想飘过，但这个我做过，用C++写的，但思想是可以通用的，贴出来参考参考，我是采用模拟手算的方式来处理的，代码如下： #include <stdio.h> 
#include <math.h> 
#include <stdlib.h> 
#include <string.h> 
int n;//阶乘数 
void calc(char *p,int n);//计算阶乘数的函数 
int getSize(int n);//计算阶乘的位数 
void main(){ 
int size; 
printf("n!? n=:"); 
scanf("%d",&n); 
char *p; 
size=getSize(n);//计算阶乘的位数 
p=(char *)calloc(size,sizeof(char));//根据阶乘的位数分配空间 
p[0]=1;//使字符数组初始化,最低位是1，其余全0 
calc(p,n);//计算阶乘数的函数 
for(int i=size-1;i>=0;i--) 
printf("%d",p[i]); 
} 
int getSize(int n){ 
double size=1; 
for(int i=1;i <=n;i++)//计算阶乘的位数,位数=log1+log2......+logn 
size+=log10(i); 
return (int)size; 
} 
void calc(char *p,int n){ 
double bitcount=1;//定义位数，开始为1位数 
int add; 
for(int i=2;i <=n;i++){ 
add=0; 
bitcount=bitcount+log10(i);//得到当前位数 
for(int j=0;j <bitcount;j++){ 
add+=i*p[j];//运算 
p[j]=add%10;//低位放入数组 
add=add/10;//高位参与下次运算 
} 
} 
} 

Answer 7

这样也行，不知道效率如何     BigDecimal bd = new BigDecimal(1);
     for(int i=1000;i>0;i--) 
     { 
     bd = bd.multiply(new BigDecimal(i));
     }
     System.out.println(bd);

Answer 8

只是个思路，没测试，觉得可以用list代替数组int n = 100000;
List<Byte> list = new ArrayList<Byte>();
list.add((byte)1);
byte u = 0; //进位用
for (int i=1; i<=n; i++) {
    for (int j=list.size()-1; j>=0; j--) {
        byte b = list.remove(j);
        b = (byte)(i*b + u);
        list.add(0, (byte)b%10);
        u = (byte)b/10;
    }
    while (u/10 > 0) {
        list.add(0, (byte)u%10);
        u /= 10;
    }
    if (u > 0) {
        list.add(u);
    }
}
System.out.println(Arrays.toString(list.toArray(new byte[0])));

Answer 9

失误，b和u不能用byte，改成long

Answer 10

debug下什么都知道拉
顶

Answer 11

经测试 BigIngeter，BigDecimal效率更高！ 
算法有待改进啊，还是写JDK的专家厉害！

Answer 12

用一个Map把每一次计算的结果保存起来，在下一次计算之前，调用递归方法前先进行查找，如果找到，就直接输出结果，
初始化Map时先存入一些较常见的，比如10！、100！等等。当要计算1000！，它要先计算999！，以此类推，当算到100！时，
查找Map，刚好有，递归就开始逐级返回！

Answer 13

看到楼主的程序，都觉得学这么长时间的Java都是白学了，有很多东西自己明明会用，但就是用不到一起去，看来技能有待加强。

Answer 14

性能没测试，没环境，也不知道结果是否正确
原来想用list来代替数组的，后来想了想，链表不如数组快
一是数组地址连续，二是数组在栈内存中，比链表的堆内存操作快public static byte[] getNMutiply(int n) {
    byte[] b = new byte[]{1};
    long u; //计算和进位用
    int p, q; //计算长度用
    for (int i=2; i<=n; i++) {
        p = 0;
        q = i;
        while (q%10 == 0) { //后面是0的数
            p++; //算出0的个数
            q /= 10; //去除0后的数
        }        for (int j=b.length-1; j>=0; j--) { //运算过程
            u = (q*b[j] + u); 
            b[j] = (byte)(u%10);
            u /= 10;    
        }        q = (u==0 ? 0 : (""+u).length());
        if (p+q > 0) { //长度发生变化的时候
            byte[] t = b;
            b = new byte[t.length+p+q]; //重建数组
            System.arraycopy(t, 0, b, q, t.length); //拷贝原数组
            for (int j=0; j<p; j++) { //补齐右边的0
                b[t.length+j] = (byte)0;
            }
            for (int j=q-1; j>=0; j--) { //补齐左边的进位
                b[j] = (byte)(u%10);
                u /= 10;
            }
        }
    }    return b;
}public static void test() {
    int n = 1000;
    long t1 = System.currentTimeMillis();
    byte[] b = getNMutiply(n);
    long t2 = System.currentTimeMillis();
    System.out.printf("time:%d ms\n", t2-t1);
    for (int i=0; i<b.length; i++) {
        System.out.print(b[i]);
    }
    System.out.println();
}

Answer 15

楼上代码我看了， 写的很好！ 学习了，我还没有测试，不过用byte数组是不是数组就有点大了， 而且要反复重建。周一上班了，我测试 一下去。辛苦！

Answer 16

初步测试，效率如下楼主 > BigDecimal > BigInteger           50000!  30000! 10000! 5000! 1000! 500!
楼主        40765    13922  1360 312 16 0
BigDecimal 50438   15406  1406 344 15 16
BigInteger 54125   16282  1500 344 32 15但是楼主的代码有BUG，楼主可以尝试一下 20000! 和 40000! 阶乘20000! 时
java.lang.ArrayIndexOutOfBoundsException: 9668
定位到 getArray -> factorAarry[i] = c;

Answer 17

这个题的目的不是用BigInteger 。  是考察数组进位的。  
20000!的BUG 我周一试，因为我已经知道。就是得到n!的位数不够。  但是数字计数：  n!的位数： log2 + .....+logn;
在用Math.log10(i); 计算再相加（数多的时候）出现误差。   大家看看有什么比较精确计算n!的位数的方法！！

Answer 18

BUG修改：private static int getBit(int n) {   
        double result = 0;   
        for (int i = 1; i < n; i++) {   
            result += Math.log10(i);   
        }   
        result += 1.5;   
        return (int) Math.ceil(result);   
    }   
＝＝＝＝＝》
private static int getBit(int n) {   
        double result = 0;   
        for (int i = 1; i <= n; i++) {   
            result += Math.log10(i);   
        }   
        result += 1.5;   
        return (int) Math.ceil(result);   
    }   

Answer 19

已经测试：public static byte[] getNMutiply(int n) {
        byte[] b = new byte[]{1};
        long u = 0; //计算和进位用
        int p, q; //计算长度用
        for (int i=2; i<=n; i++) {
            p = 0;
            q = i;
            while (q%10 == 0) { //后面是0的数
                p++; //算出0的个数
                q /= 10; //去除0后的数
            }            for (int j=b.length-1; j>=0; j--) { //运算过程
                u = (q*b[j] + u); 
                b[j] = (byte)(u%10);
                u /= 10;
            }            q = (u==0 ? 0 : (""+u).length());
            if (p+q > 0) { //长度发生变化的时候
                byte[] t = b;
                b = new byte[t.length+p+q]; //重建数组
                System.arraycopy(t, 0, b, q, t.length); //拷贝原数组
                for (int j=0; j<p; j++) { //补齐右边的0
                    b[t.length+j] = (byte)0;
                }
                for (int j=q-1; j>=0; j--) { //补齐左边的进位
                    b[j] = (byte)(u%10);
                    u /= 10;
                }
            }
        }        return b;
    }测试结果：100　：0
　　　　　1000：250
　　　　　10000：24750

Answer 20

java可以这么写
import java.math.BigInteger;public class Fac{
public static void main(String[] args)
{
BigInteger pro=new BigInteger("1");
for(int i=1;i<=1000;i++)
{
pro=pro.multiply(new BigInteger(""+i));
}
System.out.println(pro);
}
}