|
大数是算法语言中的数据类型无法表示的数，其位数超过最大数据类型所能表示的范围，所以，在处理大数问题时首先要考虑的是怎样存储大数，然后是在这种存储方式下其处理的实现方法。
一般情况下大数的存储是采用字符数组来存储，即将大数当作一个字符串来存储，而对其处理是按其处理规则在数组中模拟实现。
六??大数阶乘。
?
阶乘问题比较典型，下面，将通过自己的学习逐步介绍。
首先介绍两种常规方法。
?
1.迭代法
- ????
- #include?<stdio.h>??
- int?main()??
- {??
- ????int?n;??
- ????long?result?=?1;??
- ????scanf("%d",&n);??
- ????while(?n>1?)??
- ????{??
- ????????result?*=n;??
- ????????n--;??
- ????}??
- ????printf("%ld",result);??
- return?0;??
- }??
?
2.递归法
??
- long?factorial_recursion(?int?n?)??
- ????if(?n<=0?)??
- ????{??
- ????????return?1;??
- else??
- return?n?*?factorial_recursion(?n-1?);??
- }??
- int?main()??
- {??
- int?n;??
- long?result;??
- ????scanf("%d",&n);??
- ????result?=?factorial_recursion(?n?);??
- ????printf("%ld",result);??
- return?0;??
- }??
这两种方法都比较常规，也比较简单，初学c的时候，还没接触算法，就是利用这样的思路完成。
但是，一旦求N!中N的值大了，那么不管是int 还是 long 都无法满足。这时候就涉及到大数处理的问题上了。
下面介绍常规的大数阶乘。
?
3.利用数组存结果。
#include?<stdio.h>??
- int?a[9000];???
- ?????int?digit?=?1;???
- ?????int?temp;?????
- int?i,?j,?carry;???
- ??
- ?????printf("please?in?put?n:n");??
- ????a[0]?=?1;?????
- for?(?i=2;?i<=n;?i++?)????
- ????{????
- ?????????for(?j=1,?carry=0;??j<=digit;?j++?)??
- ????????{??
- ????????????temp?=?a[j-1]?*?i?+?carry;???
- ??????????????a[j-1]?=?temp?%?10;???
- ??????????????carry?=?temp?/?10;???
- ?????????}??
- ????????while(carry)??
- ????????{??????
- ??????????????a[++digit-1]?=?carry?%?10;???
- ????????????carry?=?carry?/?10;???
- ?????????}??
- ????}??
- ????printf("n?!?=?");??????
- for(j?=?digit;?j?>=1;j--)??
- ????????printf("%d",a[j-1]);??
- ????printf("n");??
- }??
?
这种大数阶乘算法也比较常规，目前水平能看懂。?
具体思路代码中的注释也比较详细，就不重复了。? 还是模拟笔算的过程。
?
下面附带两个大牛的算法 ， 虽然现在还看不懂，但是先mark一下。以后慢慢琢磨。
?
4. 大牛算法一
出处 ：??http://www.cnblogs.com/xianghang123/archive/2011/08/24/2152430.html
?
#define?N?400??
- long?a[8916]={1,0},n,i,c,len;???
- int?main(void)????
- {???
- ????n=N;???
- for?(?len=1;n>1;?n--)???
- ????{???
- for?(c=0,i=0;?i<len;i++?)???
- ????????{???
- ????????????a[i]=?(?c+=?a[i]*n?)?%?10000;?c/=10000;???
- ????????}???
- ???????????
- ????????((a[i]=c)>0)?len++:0;???
- ??
- ????}??????
- for(?len--,printf("%d",a[len--]);len>=0;?len--)?printf("%04d",a[len]);???
- ???????????
- return?0;???
- }??
?
【解释】
?for ( len=1;n>1; n--)???? //把len的长度初始为1，因为数组中已经有一个元素了a[0]=1
?{?
?? for (c=0,i=0; i<len;i++ ) //c初始为0，一开始还没运算哪来的进位，这是个内层循环，数组a中的len
????????????????????????? //个元素都必须参与运算，都必须*n，这就是下面a[i]*n的来由
???? {?
?????????? a[i]= ( c+= a[i]*n ) % 10; c/=10;?? //c是进位，不用说了，c+=a[i]*n，a每个元素与n
??????????????????????????????????????????????? //相乘必须考虑低位是否有进位，有就加起来
???? }
?? ((a[i]=c)>0)?len++:0;? //最后一个元素也有进位吗，有的话就在当前的元素的下个数组位置直接等于进位值，并
????????????????????????? // 且数组的元素值 要加1,没有的话什么都不干,光一个0什么都不是
????????????????????
? }
?
?
?
5.大牛算法二
出处：http://bbs.csdn.net/topics/390025206
?
int?a[100000]={1},m=1;??
- main()??
- for(;n;n--)??
- for(c=i=0;i<m||c;)??
- ????????????a[i++]=(c+=a[i]*n)%10,c/=10;m=i;??
- for(;m;)??
- ????????putch(a[--m]+48);??
- }??
?
还有关于大数阶乘另有一个斯特林公式，不过这个是估算的值，并不是精确值，n的值越大，他的结果越精确。大家可以自己学习一下。
?
另外，网上关于大数阶乘的讨论也比较多。我也google了一些，学习后，感觉下面几个比较有意义。
还是先mark下。 便于以后温习。
http://www.cnblogs.com/qlwy/archive/2012/07/18/2598028.html
?
http://www.voidcn.com/article/p-zerxkjef-uw.html
?
http://blog.csdn.net/yxnk/article/details/1665052
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
