锁定老帖子 主题:递归与分治策略(二):超大阶乘的实现
精华帖 (0) :: 良好帖 (0) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-12-16
最后修改:2009-12-16
递归与分支策略: public long factorial(int n){//关于返回值的类型,小的话用int,long if(n==0) return 1; else return factorial(n-1)*n; }
abs() //返回其值是此BigInteger的绝对值的BigInteger。 add(BigInteger val) //返回其值为(this+val)的BigInteger。 subtract(BigInteger val) //返回其值为(this-val)的BigInteger。 multiply(BigInteger val) // 返回其值为(this*val)的BigInteger。 divide(BigInteger val) //返回其值为(this/val)的BigInteger。 remainder(BigInteger val) //返回其值为(this%val)的BigInteger。 compareTo(BigInteger val) //将此BigInteger与指定的BigInteger进行比较。返回值1、0、-1分别表示大于、等于、小于 pow(int exponent) //返回当前大数的exponent次幂。 toString() //返回此BigInteger的十进制字符串表示形式。 toString(int radix) //返回此BigInteger的给定基数(radix进制)的字符串表示形式。
BigDecimal bigDecimal = new BigDecimal(Math.PI); bigDecimal = bigDecimal.setScale(2,BigDecimal.ROUND_DOWN);//接近零的舍入模式取PI值小数点后面二位 ->3.14
package DataStructures_Algorithm; import java.math.BigInteger; public class FactorialBigIntegerTest { public static void main(String[] args) { System.out.println(factorial(10000)); } private static final BigInteger factorial(int n){ BigInteger bigInteger=new BigInteger(""+n); if(n==0) return BigInteger.ONE; else return factorial(n-1).multiply(bigInteger); } }
n=1,f(1)=0; private static final BigInteger distributePoker(int n) { // BigInteger数组 BigInteger[] resultBigInteger = new BigInteger[n]; for (int i = 0; i < n; i++) { if (i == 0) resultBigInteger[i] = BigInteger.ZERO; if (i == 1) resultBigInteger[i] = BigInteger.ONE; if(i>=2) resultBigInteger[i] = resultBigInteger[i - 2] .add(resultBigInteger[i - 1]); } return resultBigInteger[n - 1]; }
private static final String ArrayStringFactorial(int n) { int a[] = new int[200];// 确保保存最终运算结果的数组位数足够大,200位的数已经够大了 int carry = 0;// 进位标志位 int digit = 1;// 位数 a[0] = 1;// 将结果先初始化为1 int temp;// 阶乘的任一元素与临时结果的某位的乘积结果 StringBuffer resultStr = new StringBuffer(); for (int i = 2; i <= n; ++i)// 开始阶乘,阶乘元素从2开始依次“登场” { // 按最基本的乘法运算思想来考虑,将临时结果的每位与阶乘元素相乘 for (int j = 1; j <= digit; ++j) { temp = a[j - 1] * i + carry;// 相应阶乘中的一项与当前所得临时结果的某位相乘(加上进位) a[j - 1] = temp % 10;// 更新临时结果的位上信息 carry = temp / 10; // 看是否有进位 } while (carry!=0?true:false)// 如果有进位 { a[(++digit) - 1] = carry % 10;// 新加一位,添加信息。位数增1 carry /= 10; // 看还能不能进位 } } for (int i = digit; i >= 1; --i) { resultStr.append(a[i - 1]); } return resultStr.toString(); }
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2009-12-16
纠正一个地方,把while (carry!=0?true:false)改为while (carry!=0),呵呵。
|
|
返回顶楼 | |
发表时间:2009-12-16
话说,分治策略在哪?
|
|
返回顶楼 | |
发表时间:2009-12-16
我记得再华科的算法书上有这么一个实例吧
|
|
返回顶楼 | |
发表时间:2009-12-16
Elminster 写道 话说,分治策略在哪?
分治在后面文章中会讨论的! |
|
返回顶楼 | |
发表时间:2009-12-16
lioncin 写道 我记得再华科的算法书上有这么一个实例吧
难道此算法是传说中“华科”的专利?国内外计算机科学的经典教材中都有这么一例吧,我写出来只是督促自己坚持学习下去罢了,O(∩_∩)O哈哈~ 我看的是《Data Structures & Algorithms in Java 2nd Edition》 |
|
返回顶楼 | |
发表时间:2009-12-16
liyun_1981 写道 纠正一个地方,把while (carry!=0?true:false)改为while (carry!=0),呵呵。
谢谢,昨晚上肯定真喝多了,居然写出这样的条件,O(∩_∩)O哈哈~ |
|
返回顶楼 | |
发表时间:2009-12-17
BigInteger bigInteger=new BigInteger(""+n);
不如改成 BigInteger bigInteger=BigInteger.valueOf(n); 好,多谢楼主分享。 |
|
返回顶楼 | |
发表时间:2009-12-17
supersun 写道
C.不使用BigInteger,计算超大数阶乘算法——>用整型数组保存每位数的结果,最后返回字符串,效率最高 private static final String ArrayStringFactorial(int n) { int a[] = new int[200];// 确保保存最终运算结果的数组位数足够大,200位的数已经够大了 int carry = 0;// 进位标志位 int digit = 1;// 位数 a[0] = 1;// 将结果先初始化为1 int temp;// 阶乘的任一元素与临时结果的某位的乘积结果 StringBuffer resultStr = new StringBuffer(); for (int i = 2; i <= n; ++i)// 开始阶乘,阶乘元素从2开始依次“登场” { // 按最基本的乘法运算思想来考虑,将临时结果的每位与阶乘元素相乘 for (int j = 1; j <= digit; ++j) { temp = a[j - 1] * i + carry;// 相应阶乘中的一项与当前所得临时结果的某位相乘(加上进位) a[j - 1] = temp % 10;// 更新临时结果的位上信息 carry = temp / 10; // 看是否有进位 } while (carry!=0?true:false)// 如果有进位 { a[(++digit) - 1] = carry % 10;// 新加一位,添加信息。位数增1 carry /= 10; // 看还能不能进位 } } for (int i = digit; i >= 1; --i) { resultStr.append(a[i - 1]); } return resultStr.toString(); }
你这完全是个 C 程序,结果的位数也限死了。
在网上随便找了一个C++的:
std::vector<int> void cal_factorial(int n) { std::vector<int> a; a.push_back(1); for (int i = 2; i <= n; ++i) { int carry = 0; for (int j = 0; j < a.size(); ++j) { int temp = a[j] * i + carry; a[j] = temp % 10; carry = temp / 10; } while (carry) { a.push_back(carry % 10); carry /= 10; } } return a; }
|
|
返回顶楼 | |
发表时间:2009-12-17
这个方法得的结果精确不精确啊?
|
|
返回顶楼 | |