|
锁定老帖子 主题：递归与分治策略（二）：超大阶乘的实现
精华帖 (0) :: 良好帖 (0) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-12-17
Solstice 写道
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-18
不知道那个BigInteger的数组方式（非递归）实现LZ是怎么个意思，我没理解，我觉得应该是这样的
private static final BigInteger distributePoker(int n) {
// BigInteger数组
BigInteger[] resultBigInteger = new BigInteger[n + 1];
for (int i = 0; i <= n; i++) {
if (i < 2)
resultBigInteger[i] = BigInteger.ONE;
else
resultBigInteger[i] = resultBigInteger[i - 1]
.multiply(BigInteger.valueOf(i));
}
return resultBigInteger[n];
}
|
| 返回顶楼 | |
|
发表时间：2009-12-18
最后修改：2009-12-18
我也不明白你在说什么，你这个代码是想干什么呢
我原题是这么说的：扩展这样一组数字序列0，1，1，2，3，5，8........，求第100个数是多少！ n=1,f(1)=0; n=2,f(2)=1; n=3,f(3)=f(1)+f(2)=0+1=1; n=4,f(4)=f(2)+f(3)=1+1=2; n=5,f(5)=f(3)+f(4)=1+1=1+2=3; n=6,f(6)=f(4)+f(5)=2+3=5; .......................... n=n,f(n)=f(n-2)+f(n-1); 编程实现f(100)：这里用数组实现，用递归没效率（测试了下用递归比20！更大的话几乎半天不出结果） 1. private static final BigInteger distributePoker(int n) { 2. // BigInteger数组 3. BigInteger[] resultBigInteger = new BigInteger[n]; 4. for (int i = 0; i < n; i++) { 5. if (i == 0) 6. resultBigInteger[i] = BigInteger.ZERO; 7. if (i == 1) 8. resultBigInteger[i] = BigInteger.ONE; 9. if(i>=2) 10. resultBigInteger[i] = resultBigInteger[i - 2] 11. .add(resultBigInteger[i - 1]); 12. } 13. return resultBigInteger[n - 1]; 14. 15. } 这里是用数组实现f(n)=f(n-2)+f(n-1) |
| 返回顶楼 | |
|
发表时间：2009-12-18
我也不明白你在说什么，你这个代码是想干什么呢
我原题是这么说的：扩展这样一组数字序列0，1，1，2，3，5，8........，求第100个数是多少！ n=1,f(1)=0; n=2,f(2)=1; n=3,f(3)=f(1)+f(2)=0+1=1; n=4,f(4)=f(2)+f(3)=1+1=2; n=5,f(5)=f(3)+f(4)=1+1=1+2=3; n=6,f(6)=f(4)+f(5)=2+3=5; .......................... n=n,f(n)=f(n-2)+f(n-1); 编程实现f(100)：这里用数组实现，用递归没效率（测试了下用递归比20！更大的话几乎半天不出结果） 1. private static final BigInteger distributePoker(int n) { 2. // BigInteger数组 3. BigInteger[] resultBigInteger = new BigInteger[n]; 4. for (int i = 0; i < n; i++) { 5. if (i == 0) 6. resultBigInteger[i] = BigInteger.ZERO; 7. if (i == 1) 8. resultBigInteger[i] = BigInteger.ONE; 9. if(i>=2) 10. resultBigInteger[i] = resultBigInteger[i - 2] 11. .add(resultBigInteger[i - 1]); 12. } 13. return resultBigInteger[n - 1]; 14. 15. } 这里是用数组实现f(n)=f(n-2)+f(n-1) |
| 返回顶楼 | |
|
发表时间：2010-01-03
阶乘也有分治策略？，斐波那契数倒有个矩阵乘法的做法
|
| 返回顶楼 | |
