算法~~~

y=2000;
x=(y^2+y)/2;
-------------------------
这是数学问题,不是算法问题.

public class Test {
public static void main(String[] args) {
System.out.println (Test.factorial(2000));
}

public static BigInteger factorial (int num) {
BigInteger big_num = BigInteger.ONE;
for (int i = 1; i <= num; i++) {
big_num = big_num.multiply(BigInteger.valueOf(num));
}
return big_num;
}
}

BigInteger result = new BigInteger("1");
for (int i = 1; i <= 2000; i++) {
result = result.multiply(new BigInteger(String.valueOf(i)));
}
System.out.println(result);

能说下意思?
codeBigIntege,BigInteger是哪两个类?

数字不论大小，原理都是一样的。
都是声明一个自增变量
从1开始，一直增加到2000，
这时用另一个变量来保存每次累乘的值，
由于2000的阶乘结果是一个相当大的数字，
只能用BigInteger来保存。一般我在算阶乘时喜欢用递归，但只能用于基本类型（int，long之类）
对于BigInteger如果使用递归，会报堆栈异常

没有codeBigIntege这个类，是你看错了.
3楼的代码已经很完整了

给个递归算法:
class Test
{
   public BigInteger fun(int a)
   {
       if(a==0||a==1) return new BigInteger("1");
       else return fun(a-1);
   }
   public static void main(String[] args)
   {
       System.out.println("2000!="+fun(2000));
   }
}
先声明:这个算法以及跟三楼的类似的算法,效率都不高!就算能算出结果也要很久!

刚才查了biginteger的范围:-2^63 (-9223372036854775808) 到2^63-1 (9223372036854775807),不能存放2000!的结果.以上提供的算法统统都不能实现的!

这段代码至少有两个问题
1.main方法里不能引用非静态方法
2.逻辑错误，返回结果：2000!=1

不好意思!我刚才查到的是SQL中的范围!在JAVA中没有限制!

import java.math.BigInteger;
class Test
{
   public static BigInteger fun(BigInteger a)
   {
       if(a.equals(new BigInteger("0"))||a.equals(new BigInteger("1")))
        return new BigInteger("1");
       else
        return a.multiply(fun(a.subtract(new BigInteger("1"))));
   }
   public static void main(String[] args)
   {
       BigInteger a = new BigInteger("2000");
       System.out.println("2000!="+fun(a));
   }
}速度确实够慢

如果只是需要精度不是很高的值的话可以采用数学方法：1，斯特林公式：public class Test {    public static void main(String[] args) {
        stirling(10000);
    }

    /**
     * Stirling:
     * n! = sqrt(2 * pi * n) * pow(n / e, n)
     * @param n
     */
    private static void stirling(int n) {
        double a = n * Math.log10(n / Math.E);
        double s = 0.5 * Math.log10(2 * Math.PI * n);
        double base10 = a + s;
        int exponent = (int)base10;
        double base = Math.pow(10, base10 - exponent);
        System.out.println(n + "! = " + base + " * 10^" + exponent);
    }
}100000! = 2.8242270545605797 * 10^456573
2，对数法：采用对数法可以获得更高的精度，当然了复杂度也由斯特林公式的 O(1) 升为 O(N) 了。    /**
     * n! = 1 * 2 * 3 * ... * (n - 1) * n
     * log(n!) = log(1) + log(2) + log(3) + ... + log(n - 1) + log(n)
     * @param n
     */
    private static void logFactorial(int n) {
        double sum = 0;
        for(int i = 1; i <= n; i++) {
            sum += Math.log10(i);
        }
        int exponent = (int)sum;
        double base = Math.pow(10, sum - exponent);
        System.out.println(n + "! = " + base + " * 10^" + exponent);
    }100000! = 2.8242294097488676 * 10^456573

这道题考的的是算法，就是如果实现BigInterger。
算法里面的“高精度乘法"就是用数组模拟数字。
比如678923451234 * 34857240248957
int a[] = new int[100];
int b[] = new int[100];
int c[];
a[0] = 1234;//低四位
a[1] = 2345;
a[2] = 6789;b[0] = 8957;
b[1] = 4024;
b[3] = 4857;
b[4] = 3;这样通过数组的模拟相乘，进位. 结果放在c中。1000!的阶乘，只有一个因数是大数（用数组模拟），相对上面的，要容易很多了。

public class BigFactorial { public static void factorial(int f) {
int[] a = new int[1000];
// int[] ret = new int[100]; a[0] = 1;
int len = 1;
for (int i = 2; i <= f; i++) {
int jiwei = 0;
for (int j = 0; j < len; j++) {
int mul = a[j] * i;
mul += jiwei;
a[j] = mul % 1000;
jiwei = mul / 1000;
}
if (jiwei > 0) {
a[len] = jiwei;
len++;
}
}
for (int i = len - 1; i >= 0; i--) {
if (a[i] > 99 || i == len-1) {
System.out.print(a[i]);
} else if (a[i] > 9) {
System.out.print("0"+a[i]);
} else {
System.out.print("00"+a[i]);
}
}
System.out.println();
} public static void main(String[] args) {
factorial(3);
factorial(4);
factorial(5);
factorial(6);
factorial(7);
factorial(8);
factorial(9);
factorial(100);
factorial(1000);
}
}

哦，如果算大于1000到10000的阶乘
a[j] = mul %1000; 改成 a[j]=mul%10000;
jiwei = mul /1000; 改成 jiwei=mul/10000;
就行了，否则大于1000会错的:)

解决方案 »