模板
教程
环境
性能
功能
管理
求算大数（比如100）阶乘的思路
发表于：2007-05-26来源：作者：点击数：
标签：
如题~~ DX们指点指点啊~~:m01: 财产已冻结 回复于：2004-04-26 00:54:59 顶上去~~顺便捞一分~~：） uiibono 回复于：2004-04-26 08:47:49 [quote:5e8a88d9b4="财产已冻结"]如题~~ DX们指点指点啊~~:m01:[/quote:5e8a88d9b4] 按定义算就行了，用迭代法。 para
如题~~
DX们指点指点啊~~ :m01:
| 财产已冻结 回复于：2004-04-26 00:54:59 |
| 顶上去~~顺便捞一分~~：） |
| uiibono 回复于：2004-04-26 08:47:49 |
| [quote:5e8a88d9b4="财产已冻结"]如题~~
DX们指点指点啊~~ :m01:[/quote:5e8a88d9b4] 按定义算就行了，用迭代法。 |
| parady 回复于：2004-04-26 10:22:02 |
| [quote:026b7ba8d5="uiibono"]
按定义算就行了，用迭代法。[/quote:026b7ba8d5] 这样好像不行吧，太大了，会溢出的！ |
| henngy 回复于：2004-04-26 10:23:47 |
| 很容易的递归函数，，自己写试试 |
| luopengxo 回复于：2004-04-26 10:51:14 |
| 递归 |
| 财产已冻结 回复于：2004-04-26 12:50:57 |
| [quote:b77a0de9a6="henngy"]很容易的递归函数，，自己写试试[/quote:b77a0de9a6]
好像没那么容易吧~~ 谁能给个完整的思路？ :em16: |
| 风中的枫叶 回复于：2004-04-26 13:19:41 |
| 仍然按定义算就行了，用迭代法，你用long double定义变量！ |
| sprinklexu 回复于：2004-04-26 18:33:06 |
| 定义一个一维数组，每一个数组元素代表一个10000的数
然后按照10000进一 如果觉得静态数组麻烦还可以定义链表来解决。 |
| 财产已冻结 回复于：2004-04-26 19:24:51 |
| [quote:097709b9b9="风中的枫叶"]仍然按定义算就行了，用迭代法，你用long double定义变量！[/quote:097709b9b9]
long double太小了，仍会溢出的。 |
| 财产已冻结 回复于：2004-04-26 19:27:38 |
| [quote:cb761f37ea="sprinklexu"]定义一个一维数组，每一个数组元素代表一个10000的数
然后按照10000进一 如果觉得静态数组麻烦还可以定义链表来解决。[/quote:cb761f37ea] 我也曾想过把结果存入一个数组中，数组中的每一个元素代表数字的每一位，可是实现起来比较困难，不知道从哪里下手。 :em16: |
| sprinklexu 回复于：2004-04-27 09:18:14 |
| 为什么要只显示一位啊？
一个元素显示一个小于10000的数 这样还可以减少数组的大小[/code] |
| lllll 回复于：2004-04-27 10:09:13 |
| 一个大数，例如，3284789421570324478324。用字符窜表示。以后的是不用多说了吧。 |
| clearcase/" target="_blank" >cc8829 回复于：2004-04-27 10:53:23 |
| 将大数字符串表示，按一定长度分段，比如说8位，每段分别参与运算，考虑段间进位和退位的问题，所有运算都做完之后，将所有运算结果再合成一个字符串，即是结果。 |
| chg.s 回复于：2004-04-27 11:36:22 |
| 下面的longint不是通用的长整数类，而是为了求阶乘特别设计的，所以构造函数功能非常有限，也没有重载operator*。不过对这个具体问题，够用了。:p
[code:1:c8b4277ee4] #include <iostream> #include <iomanip> #include <vector> using namespace std; class longint { private: vector<int> iv; public: longint(void) { iv.push_back(1); } longint& multiply(const int &); friend ostream& operator<<(ostream &, const longint &); }; ostream& operator<<(ostream &os, const longint &v) { vector<int>::const_reverse_iterator iv_iter = v.iv.rbegin(); os << *iv_iter++; for ( ; iv_iter < v.iv.rend(); ++iv_iter) { os << setfill('0') << setw(4) << *iv_iter; } return os; } longint& longint::multiply(const int &rv) { vector<int>::iterator iv_iter = iv.begin(); int overflow = 0, product = 0; for ( ; iv_iter < iv.end(); ++iv_iter) { product = (*iv_iter) * rv; product += overflow; overflow = 0; if (product > 10000) { overflow = product / 10000; product -= overflow * 10000; } *iv_iter = product; } if (0 != overflow) { iv.push_back(overflow); } return *this; } int main(int argc, char **argv) { longint result; int l = 0; sscanf(argv[1], "%d", &l); for (int i = 2; i < l; ++i) { result.multiply(i); } cout << result << endl; return 0; }[/code:1:c8b4277ee4] 运行a.out 100得到99的阶乘。 大致的想法就是用一个vector<int>来保存一个长整数。vector中的每一个元素保存长整数中的四位。 例如 3368230 保存为 iv[0]=8230, iv[1]=336。 这个数乘10的过程是： product=iv[0]*10=82300; overflow=product/10000=8; product-=overflow*10, product = 2300; ----Next loop product=iv[1]*10=3360; product += overflow, product = 3368; //overflow是低四位的乘积中万位以上的数字 ----end 得到的结果是iv[0]=2300, iv[1]=3368 --> 33682300. |
| odin_free 回复于：2004-04-27 11:43:58 |
| 网上很多大数算法 找简单的看看
多数是字符串的解决方法 |
| whyglinux 回复于：2004-04-27 11:46:12 |
| 很好。怎样用C++解决实际问题，这就是一个生动的实例，特别值得C++学习者仔细研究。 |
| mirnshi 回复于：2004-04-27 12:33:36 |
| 找个数学库，一切ok |
| flc1976 回复于：2004-04-27 16:04:54 |
| 给你一个
class DGDY{ int res=1; int factorial(int ii){ if ( ii!=1) res= ii* factorial(ii-1); return res; } } 用java编译运行一下你就明白了。 |
| redspider 回复于：2004-04-27 18:02:32 |
| 计算这么大的数，做什么用的 |
| IaMaBoY 回复于：2004-04-28 08:46:50 |
| 网上的大数库都是以科学计数表示的 怎么让它全部显示阿 |
| lijunyu 回复于：2004-05-01 11:24:15 |
| 降一个数表示为科学计数法的形式
NEe 如1024表示为1.024E3的形式 将前面的数值部分和后面的指数部分设为类的2个数据成员 重载+-*/=这些运算符 就可以解决了 |
| THEBEST 回复于：2004-05-01 12:29:27 |
| 钱能书上一练习：
[code:1:fdbd41766a]/* 可以把n!的结果放在数组中，数组中每个元素都表示n!值的一位. 对整数范围内的n,求n!. 对于输入的n想办法昼精确地估计出n!所占的位数.就能确定数组元素的个数 可以将n!表示成10的次幂,即n!=10^M(10的M次方)则不小于M的最小整数就是 n!的位数，对该式两边取对数，有?=log10^n!即： M = log10^1+log10^2+log10^3...+log10^n 循环求和,就能算得M值，该M是n!的精确位数。 数组初始化时,令数组第一个元素(n!的第一位)为整数1,其余为0. 在数组中计算n!时是通过将数组中的值乘2,3,4,。。一直到乘n的方式得的 把数组的第一个元素看做是n!的最低位，最后一个元素看做是最高位。 */ #include <iostream> using namespace std; #include <cmath> #include <cstdlib> #include <iomanip> int getN(); //输入n int getBitNum(int n); //求n!的位数 char *init(int size); void calc(char *a,int n); //求n! void display(char *a,int size); int main() { int n = getN(); int size = getBitNum(n); char *pa = init(size); calc(pa,n); display(pa,size); delete []pa; //note: } int getN() { int n; cout << "Please input n of n! : "; cin >> n; while(n < 0) { cout << "input error,again: "; cin >> n; } if(n == 0) exit(1); return n; } int getBitNum(int n) { double sum = 1.0; for(int i=1; i<=n; i++) sum += log10((long double)i); //参数为double &和long double& //不转换重载函数不能解析 return int(sum); //不转换会有warning } char * init(int size) { char *pa = new char[size]; if(!pa) { //n太大时考虑申请内存不成功情况的执行动作 cout << "too large factor of " << size << endl; exit(1); } pa[0] = 1; for(int i=1; i<size; i++) pa[i] = 0; return pa; } void calc(char *a, int n) { double bitcount = 1; int begin = 0; for(int i=2; i<=n; ++i) { long add = 0; //源为long and=0;由于and是C++关键字，所以出错。 //故所有为add的源文为and.不小心的出错点。 bitcount += log10((long double)i); if(a[begin] == 0) begin++; for(int j=begin; j<int(bitcount); ++j) { add += (i*a[j]); a[j] = char(add % 10); add /= 10; } } } void display(char *a, int size) { int bit = 0; for(int i=size-1; i>=0; i--) { if(bit % 50 == 0) cout << endl << "The" << setw(5) << (bit/50+1) << " \'s 50 bit: "; cout << int (a[i]); //思考：为什么需要进行显式的整形转换呢? bit++; } cout << endl; } [/code:1:fdbd41766a] |
| mzpvsww 回复于：2004-05-01 12:34:58 |
| 乱说，这个是要用链表分段算的，要不，100！你的机器早就game over了 |
| THEBEST 回复于：2004-05-01 14:22:32 |
| [quote:698961e0b5="mzpvsww"]乱说，这个是要用链表分段算的，要不，100！你的机器早就game over了[/quote:698961e0b5]什么意思? |
| mzpvsww 回复于：2004-05-01 14:59:30 |
| 你的机器可以容忍100！的大小？？？不会益出？？？ |
| THEBEST 回复于：2004-05-01 15:29:30 |
| 你有没有看上面的程序???
并不是直接存储啊,没看到是用数组吗? |
| hefish 回复于：2004-05-02 00:19:38 |
| 就是《数据结构》里面曾经说到的 分段乘法。
只要内存足够，可以计算出n! |
| yardley 回复于：2004-05-14 17:29:22 |
| 我写的程序。
name : factorial.c function: 计算阶乘 memo : 使用数组来保存特大的运算结果 计算100000!耗费时间1400秒 使用特殊技巧以加快计算 |
| improgrammer 回复于：2004-05-21 13:00:29 |
| 给个用16进制显示的程序：
N的大小不是问题， 我只分配了256字节来表示结果，N最大可取到(300)base10。 再大，多分配些字节就是了。 时间效率不是问题，很快的。 void print_base16(unsigned char *v,int size) { int i; printf("\n0X"); for(i=size-1;i>=0;--i) { if(v[i]) { break; } } for(;i>=0;--i) { printf("%02X",v[i]); } } int multiply(unsigned char *v,int size,int n) { int i,t=0; for(i=0;i<size;++i) { t += v[i] * n; v[i] = t & 0xFF; t >>= 8; } return t; } void factor(int n) { unsigned char v[256]; int i; for(i=0;i<256;++i)v[i]=0; v[0]=1; for(;n>0;--n) { if(multiply(v,256,n)) { printf("%i over flow!\n",n); break; } } print_base16(v,256); |
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-
