大数的阶乘

10000的阶乘的算法（⼤数的阶乘）很多天没有更新⾃⼰的Blog了,前⼏天拿到⼀个题⽬.就是写⼀段程序计算10000的阶乘.当时我还以为这题⽬⾮常简单,没想到还是需要动点⼤脑的.花了将近半个⼩时才搞定,拿出来分享⼀下.为什么不能⽤普通的⽅法来写呢,⽐如说递归?在我的教科书上可是⽤的是递归呀?不知道你注意没有,如果是100的阶乘的话,其结果肯定是⾮常⼤的,以我们现有语⾔的数据类型肯定是没法使⽤的,就拿C来说,long型能存的下100的阶乘吗?未必.所以我就使⽤数组来存储结果的每⼀位,然后输出每⼀位不就是结果吗.那么具体怎样去做?⾸先确定结果的位数?如何确定呢?请看下⾯.2!=1*2<=10*103!=1*2*3<=10*10*10.......所以我们可以得出⼀个结论n!<=10n所以n!的位数可以这样计算:两边取对数,即log10n!<=log1010n两边n>=Log101+Log102+Log10 3+....Log10 n这样n!的位数肯定等于⼩于Log101+Log102+Log10 3+....Log10 n.以上是错误的正确的推断如下:可以将n!表⽰成10的次幂,即n!=10^M(10的M次⽅)则不⼩于M的最⼩整数就是 n!的位数，对该式两边取对数，有 =log10^n!即：M = log10^1+log10^2+log10^3...+log10^n循环求和,就能算得M值，该M是n!的精确位数。

位数的确定解决之后,就看看如何计算了.看看如下代码:1int index=0;2long carrier=0;3double bitCount = 1;4int begin = 0;56for(index=2; index<=n; ++index)7 {8long multiValue = 0;9 bitCount += log10((long double)index);10if(arrValue[begin] == 0)11 begin++;1213for(int j=begin; j<int(bitCount); ++j)14 {15 multiValue += (index*arrValue[j]);16 arrValue[j] = char(multiValue % 10);17 multiValue /= 10;18 }19 }这⾥就是计算的关键了.注意⼀下进位问题即可.所有代码如下:12//////////////////////////////////////////////////////////////////////////3// Date created: 2005/07/124// Author: Confach Zhang5// Purpose: 计算n!的值6//////////////////////////////////////////////////////////////////////////789using namespace std;10#include "StdAfx.h"11#include <iostream.h>12#include <conio.h>13#include <stdlib.h>14#include <math.h>15#include <stdio.h>16#include <iomanip.h>1718int GetNumber(); //输⼊ n19int GetBitLength(int n); //求n!的位数20char* Initialize(int); //初始化存储结果的值21void PrintValue(char *a,int size); //打印值到屏幕22void PrintValue(char *a,int size,char* fileName); //打印值到⽂件 23char* GetValue(int val); //计算24char* SubGetValue(char* ,int);252627int main()28{29int value=GetNumber();30char fileName[16];31int size=GetBitLength(value);32char *pa = Initialize(size);3334//pa=GetValue();35 pa=GetValue(value);3637 PrintValue(pa,size);3839//sprintf(fileName,"%s","10000!.txt");40 sprintf(fileName,"%d!.txt",value);4142 PrintValue(pa,size,fileName);43 delete []pa; //note:44return 1;45}46//函数GetValue47// 求得计算结果48//返回结果49//History:50//1)char* GetValue()51//2)GetValue(int val)52// 参数:val 计算阶乘的值53char* GetValue(int val)54{55//定义⼀个数组存储阶乘的值56 //⾸先得到10000!阶乘的位数57int VALUE=val;58int length=GetBitLength(VALUE);59char *arrValue = new char[length];60if(!arrValue) {61 cout <<"申请内存失败!" << endl;62 exit(1);63 }64 arrValue[0] = 1;65for(int i=1; i<length; i++)66 arrValue[i] = 0;67 arrValue=SubGetValue(arrValue,VALUE);68return arrValue;69}7071char* SubGetValue(char* arrValue,int n)72{73int index=0;74long carrier=0;75double bitCount = 1;76int begin = 0;7778for(index=2; index<=n; ++index)79 {80long multiValue = 0;81 bitCount += log10((long double)index);82if(arrValue[begin] == 0)83 begin++;8485for(int j=begin; j<int(bitCount); ++j)86 {87 multiValue += (index*arrValue[j]);88 arrValue[j] = char(multiValue % 10);89 multiValue /= 10;90 }91 }92return arrValue;93}9495//得到计算阶乘的值,此函数为新增96int GetNumber()97{98int n;99 cout << "请输⼊要计算阶乘的n值: ";100 cin >> n;101while(n < 0) {102 cout << "输⼊错误,请重新输⼊: ";103 cin >> n;104 }105if(n == 0)106 exit(1);107return n;108}109110//函数GetBitLength111// 求得计算结果的位数,本函数为新增加112//参数113// n 需要计算的阶乘的数114//返回结果的位数115int GetBitLength(int n)116{117double sum = 1.0;118for(int i=1; i<=n; i++)119 sum += log10((long double)i);120return int(sum);121}122//-----------123//函数:Initialize124// 初始化存储结果的数组125//参数:126// size 数组的长度127//返回值128// 初始化后的数组129//-------------130char * Initialize(int size)131{132char *arrValue = new char[size];133if(!arrValue) {134 cout << size<<"太⼤,申请内存失败!" << endl; 135 exit(1);136 }137 arrValue[0] = 1;138for(int i=1; i<size; i++)139 arrValue[i] = 0;140return arrValue;141}142143//-----------144//函数:PrintValue145// 将结果输⼊到屏幕上146//参数:147// buff 存储结果的数组148// buffLen 数组的长度149// fileName ⽂件名150//-------------151void PrintValue(char *buff, int buffLen)152{153int bit = 0;154int nCol=0;155for(int i=buffLen-1; i>=0; i--) {156if(bit % 10 == 0)157 {158 cout << " " ;159 nCol++;160if(nCol==10)cout<<endl;161 }162 cout << int (buff[i]);163 bit++;164 }165 cout << endl;166167}168//-----------169//函数:PrintValue170// 将结果输⼊到⼀个⽂件中171//参数:172// buff 存储结果的数组173// buffLen 数组的长度174// fileName ⽂件名175//-------------176177void PrintValue(char *buff,int buffLen,char *fileName) 178{179int bit = 0;180int nCol=0;181182 FILE *fp=NULL;183//-----------------------------184185if (fileName==NULL) return ;186 fp=fopen(fileName,"wt");187if (fp==NULL)188 {189 printf("不能创建⽂件%s",fileName);190return ;191 }192193for(int i=buffLen-1; i>=0; i--)194 {195 fprintf(fp,"%d",int(buff[i]));196197if(bit % 9 == 0)198 {199 fprintf(fp,"%s"," ");200 nCol++;201if(nCol==8)202 {203 fprintf(fp,"%s","\n");204 nCol=0;205 }206 }207 bit++;208209 }210 fprintf(fp,"\n");211 fclose(fp);212}213好了,不说了.Last Updated: 2005年7⽉14⽇12:43:07 感谢的建议Last Updated: 2005年7⽉15⽇ 8:48:20 感谢的精彩建议posted on 2005-07-14 12:17 阅读(1260) 所属分类:re: 10000的阶乘 2005-07-14 12:34@Milestone能写多点⽂字吗？⽐如说说，⽤普通的递归会出现什么问题和不⾜你的这种新⽅法的原理是什么，关键的技术点⼜在哪？这样⼀堆代码，我真的看不懂，可能我技术太菜了；）*￥—#**re: 10000的阶乘 2005-07-14 12:36@kwklover谢谢你的提议,有空我写上.re: 10000的阶乘 2005-07-14 13:13普通的递归不⾏猜想原因是C的标准数据类型有可能不能保存结果那么⼤的数值。

1乘到100的简便方法公式求1到100的乘积的简便方法公式是阶乘（factorial）。

阶乘是指一个正整数与小于它的所有正整数之积。

在数学中表示为n!。

具体地，1到100的乘积可以表示为100!，即100的阶乘。

阶乘的计算可以通过循环的方式进行，从1到n依次相乘，或者通过递归的方式实现。

在计算机程序中，通常使用循环的方法来求解阶乘。

拓展：
阶乘的计算在数学和计算机领域中有广泛的应用。

以下是一些拓展的情况：
1.负整数的阶乘：
负整数的阶乘是没有意义的，因为阶乘要求所有相乘的数都是正整数。

2.非整数的阶乘：
非整数的阶乘也没有明确的定义。

然而，可以通过Gamma函数来
拓展阶乘的定义，其中Gamma函数是阶乘的延伸。

3.大数阶乘的计算：
当n非常大时，直接计算n的阶乘可能会超出计算机的表示范围。

解决办法是使用大数运算的技术，例如使用字符串来表示大数，并通
过手动模拟竖式计算来求解阶乘。

4. Stirling近似公式：
Stirling近似公式是对阶乘的近似计算公式，可以用于计算大数
的阶乘。

该公式可以用于估计n的阶乘的近似值，其中n较大。

阶乘函数阶乘函数是数学中常见的函数之一，用于计算非负整数的阶乘。

在数学中，阶乘表示为n!，其中n是一个非负整数。

定义如下：n! = n * (n-1) * (n-2) * … * 3 * 2 * 1在本文档中，我们将讨论阶乘函数的计算方法、应用场景以及相关注意事项。

阶乘函数的计算方法阶乘函数可以通过多种方法进行计算。

以下是两种常见的计算方法：递归方法递归方法是一种将问题分解为较小子问题的解决方法。

通过不断地调用自身来实现计算阶乘函数。

以下是使用递归方法计算阶乘函数的示例代码：def factorial_recursive(n):if n ==0:return1else:return n * factorial_recursive(n-1)上述代码中，首先判断n是否为0，如果是，则返回1（0的阶乘为1）。

否则，计算n与n-1的阶乘的乘积，并返回。

使用递归方法计算阶乘函数时，需要注意避免堆栈溢出。

当计算的数值较大时，递归方法可能会导致堆栈溢出的问题。

迭代方法迭代方法是一种使用循环结构来计算阶乘函数的方法。

通过不断迭代更新一个变量的值来实现计算阶乘。

以下是使用迭代方法计算阶乘函数的示例代码：def factorial_iterative(n):result =1for i in range(1, n+1):result *= ireturn result上述代码中，使用一个变量result来保存计算结果，并通过循环结构不断更新result的值，最终得到阶乘函数的结果。

迭代方法相对于递归方法来说，不会存在堆栈溢出的问题，适用于计算较大数值的阶乘。

阶乘函数的应用场景阶乘函数在数学和计算机科学中有广泛的应用场景。

以下是一些常见的应用场景：排列组合在排列组合中，阶乘函数用于计算不同元素的排列或组合数量。

例如，计算从n个元素中取出k个元素进行排列的数量可以使用阶乘函数。

概率统计在概率统计中，阶乘函数用于计算事件的可能性。

1000的阶乘算法
计算1000的阶乘是一个相当大的数字，它的结果将是一个包含很多位的数。

由于1000的阶乘是一个非常大的数字，所以不可能直接将它写入内存中。

一个有效的方法来计算大数的阶乘是使用迭代方法。

这种方法的基本思想是：
n的阶乘= (n-1的阶乘) * n
这是一个Python代码示例，用于计算1000的阶乘：
python复制代码：
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
print(factorial(1000))
此代码首先检查n是否为0，因为0的阶乘是1。

然后，它递归地调用自身，每次将n减1，并将结果乘以n。

这个过程一直持续到n为0为止。

然而，需要注意的是，这种方法在计算非常大的阶乘时可能会遇到问题，因为Python的默认数据类型无法存储这
么大的数字。

在这种情况下，你可能需要使用一些特殊的数据结构或库，如大数库，来处理大数的计算。

大数的认识知识点总结在数学中，大数是指位数较大的整数或实数。

处理大数涉及到许多特殊的计算方法和技巧。

本文将总结一些与大数相关的知识点，帮助读者更好地理解和处理大数。

一、大数的表示方法1. 十进制表示法：将大数按照普通的十进制数进行表示，例如123456789。

2. 科学计数法：将大数转化为指数形式，使其更加紧凑。

例如，一亿可以表示为1×10^8。

3. 简化表示法：如果大数中存在一段重复的数字，可以使用简化表示法。

例如，222222可以表示为2×10^5。

二、大数的运算1. 大数的加法：按照普通的竖式加法规则进行计算。

需要注意的是，对齐两个加数的各位，并考虑进位的情况。

2. 大数的减法：按照普通的竖式减法规则进行计算。

需要注意的是，被减数与减数的各位对齐，并考虑借位的情况。

3. 大数的乘法：可以使用快速乘法算法，将乘法转化为多次加法的形式。

需要注意的是，按位相乘后的进位问题。

4. 大数的除法：可以使用长除法的方法进行计算，将除法转化为多次减法的形式。

5. 大数的取模运算：通过除法计算得到商和余数，只保留余数。

三、大数的性质1. 位数相加：两个大数的位数相加，等于它们的数字位数之和。

例如，10000位的数与1000位的数相加后，结果仍然是10000位。

2. 位数相乘：两个大数的位数相乘，等于它们的数字位数之和。

例如，1000位的数与1000位的数相乘后，结果是2000位。

3. 大数的阶乘：计算大数的阶乘时，需要考虑到大数的位数增长非常快。

可以利用特殊的算法来优化计算过程，如分治算法或递归算法。

四、大数的应用领域1. 密码学：在密码学中，需要使用大素数进行加密操作。

大数的运算和性质对密码学算法的安全性具有重要影响。

2. 数据分析：在大数据时代，需要处理包含大量数字的数据集。

大数运算的技巧对数据分析和统计具有重要作用。

3. 金融领域：在金融交易和计算中，经常涉及到大量的数字计算，如股票交易、利率计算等。

*************************************(1)************************************ ****************假如需要计算n+16的阶乘，n+16接近10000，已经求得n!（共有m个单元），（每个单元用一个long数表示，表示1-100000000）第一种算法（传统算法）计算(n+1)! 需要m次乘法，m次加法(加法速度较快,可以不予考虑,下同)，m次求余（求本位)，m次除法(求进位），结果为m+1的单元计算(n+2)! 需要m+1次乘法，m+1次求余，m+1次除法, 结果为m+1个单元计算(n+3)! 需要m+1次乘法，m+1次求余，m+1次除法，结果为m+2个单元计算(n+4)! 需要m+2次乘法，m+2次求余，m+2次除法，结果为m+2个单元计算(n+5)! 需要m+2次乘法，m+2次求余，m+2次除法，结果为m+3个单元计算(n+6)! ...计算(n+7)! ...计算(n+8)! ...计算(n+9)! ...计算(n+10)! ...计算(n+11)! ...计算(n+12)! ...计算(n+13)! ...计算(n+14)! 需要m+7次乘法，m+7次求余，m+7次除法，结果为m+7个单元计算(n+15)! 需要m+7次乘法，m+7次求余，m+7次除法，结果为m+8个单元计算(n+16)! 需要m+8次乘法，m+8次求余，m+8次除法，结果为m+8个单元该算法的复杂度：共需:m+(m+8)+(m+1+m+7)*7=16m+64次乘法，16m+64次求余，16m+64次除法第二种算法：1.将n+1 与n+2 相乘,将n+3 与n+4 相乘,将n+5 与n+6...n+15与n+16,得到8个数，仍然叫做n1,n2,n3,n4,n5,n6,n7,n82. n1 与n2相乘，结果叫做p2，结果为2个单元，需要1次乘法。

大数的阶乘众所周知，阶乘的定义就是n! = (n-1)!*n，但是有基本的初始条件的，即0! = 1因此1! = 1*0! = 1 * 1 = 1;2! = 2*1! = 2 * 1 = 2;依次类推，但是当n足够大时，整型根本无法装下n的阶乘，如果用C语言来实现的话，根本不可能，那怎么办呢？其实阶乘也无非是乘法和加法罢了，如4!= 24;我们可以用数组来存各位，结舌数组的起始长度是1哈，每当遇到超过长度时，就自加1，不过这里要稍微处理下的，我们可以倒过来存，以便做乘法的，可以这样来存。

4! 4 25! = 5 * 4!，可以用5去乘以4，如果大于10则需向高位进位，下一位的结果就等于下一位乘以5然后加上刚才的进位，当然也要取余数哈，然后继续看有没进位哈，知道遍乘数组每一位哈。

给个能求1000！的例子，用C语言实现的，供大家参考，以便交流学习哈。

#include <iostream>using namespace std;#define N 1000 // 所需求的N的阶乘static int a[N*3]; // 保存阶乘的各位int main(){int i,j; //临时变量int len = 1;int tem,carry;a[1] = 1; //1的阶乘for (i = 2;i<=N;i++) //求阶乘的方法{carry = 0;for (j=1;j<=len;j++){tem = a[j]*i +carry;a[j] = tem%10;carry = tem/10;if (j==len&&carry!=0){len++;}}}for (i = len;i>=1;i--) //输出各位{cout<<a[i];}cout<<endl;return 0;}我们也可以用Python来实现的哈，很简单两句话，就好啦Import mathMath.factorial(1000)就OK了，爽把！不过3.x以上的版本才有此函数哈。

c语⾔⼤数加法、阶乘和乘法⼀.⼤数加法定义两个⾜够⼤的数字，其数值远超过long的取值范围，设该⼤数的位数有两百位，求其相加所得⼤数加法的核⼼思想详见此链接，内有详细的动画演⽰，这⾥不再赘述直接上代码：#include<string.h>#include<stdio.h>#define N 10//定义当前⼀个⾜够⼤的数字为10位，可任意更改void print_num(int a[],int n){int i=n-1;//从逆序数组的最后⼀项开始查找，进⾏反逆序while(a[i]==0)//由于规定的数组⽐真实计算的数字⼤，所以数组最后⼏位必定存在0的情况--i;//这种情况下⼀定要将0舍去，否则会抬⾼数组的位数for(;i>=0;i--)//找到⾮零的数组，进⾏反逆序输出printf("%d",a[i]);}void plus(int num1[],int num2[],int n){//尤其注意！由于数组是逆序的，所以num[0]是个位,num[1]是⼗位,num[2]是百位for(int i=0,up=0;i<n;i++)//算法参考⼩学加法，这⾥定义⼀个up进位标记{int temp=num1[i]+num2[i]+up;//up最开始设为0，因为在个位⽆法获取进位num1[i]=temp%10;//若产⽣进位⾏为，则选取个位部分赋给num1up=temp/10;//在个位上，若个位相加产⽣进位，则⽤temp/10取整加到下⼀次的⼗位上}print_num(num1, n);}int main(){char buffer1[]="123456";//缓冲数组，将当前数组倒序写⼊num1中char buffer2[]="78951234";//同上，写⼊num2中int num1[N]={0};//将num1，2全部置为0，⽤来将缓冲数组写⼊到num数组当中int num2[N]={0};int n=N;//定义上述两个数组的长度为10for(int i=0,temp=(int)strlen(buffer1)-1;temp>=0;temp--)num1[i++]=buffer1[temp]-'0';//⽤倒序的⽅式将缓冲数组写⼊num中，意味着num的第⼀位是个位，第⼆位是⼗位，三是百位...for(int i=0,temp=(int)strlen(buffer2)-1;temp>=0;temp--)num2[i++]=buffer2[temp]-'0';plus(num1, num2, n);//将两数字相加printf("\n");}⼆.⼤数阶乘⼤数阶乘的中⼼思想参考上述视频和⼀篇博客，博客详情：但是，这⾥需要说明⼀个点：1*2=2,将2存到a[0]中，接下来是⽤a[0]*3；2*3=6，将6储存在a[0]中，接下来是⽤a[0]*4；6*4=24，是两位数，那么24%10==4存到a[0]中，24/10==2存到a[1]中，接下来是⽤a[0]*5；a[1]*5+num(如果前⼀位相乘结果位数是两位数，那么num就等于⼗位上的那个数字；如果是⼀位数，num==0)24*5=120，是三位数，那么120%10==0存到a[0]中，120/10%10==2存到a[1]中，120/100==1存到a[2]中由于上述博客存在某些地⽅没有说清楚的情况，这⾥解释⼀下关于上述博客的Q&A：1.这⾥的num指的是什么？答：这⾥的num指的是前⾯两数值相乘后进位数位多少：例如6*4得24，这⾥的num值的是24/10=2，进位数为2，num=22.下⾯代码为什么要充i=2开始？答：如果这⾥看懂了代码其实理解2不是很难，但是没有看懂是真的难懂：⾸先明确⼀点：5的阶乘是1*2*3*4*5，我定义的value数组的第⼀位为1，⽽我的i是从2起的，这样以来不就直接凑出了1*2了吗？当我的i⾃增到3，我直接在value数组中找出1*2的值，拿他们去和3相乘，也就凑成了1*2*3了3.如何在代码当中表现出进位的思想？答：我们以5！为例，当计算到1*2*3*4的时候，value当中的表现形式是42000000，从左到右依次是个位，⼗位，百位，千位...etc（value表⽰的是24这个数字）我们在关于j的循环当中拿i=5去和value数组求乘积：5先和位于个位的4求积得20：20%10得0，0放⼊个位中；20/10得2，进位为2，up=2。

大数阶乘c语言程序下面是一个计算大数阶乘的C 语言程序：c#include <stdio.h>#include <stdlib.h>/* 定义一个结构体来表示大数*/typedef struct {unsigned int digits[1000]; 数字数组int length; 数字长度} BigNum;/* 初始化大数为1 */void init(BigNum *p) {int i;for (i = 0; i < 1000; i++) {p->digits[i] = 0;}p->digits[0] = 1;p->length = 1;}/* 大数乘法*/void multiply(BigNum *p, int n) {int i, carry = 0;for (i = 0; i < p->length; i++) {int value = p->digits[i] * n + carry;p->digits[i] = value % 10;carry = value / 10;}while (carry > 0) {p->digits[p->length] = carry % 10;p->length++;carry /= 10;}}/* 计算阶乘*/void factorial(int n) {BigNum result;init(&result);int i;for (i = 1; i <= n; i++) {multiply(&result, i);}printf("%d! = ", n);for (i = result.length - 1; i >= 0; i) {printf("%d", result.digits[i]);}printf("\n");}int main() {int n;printf("请输入要计算的阶乘：");scanf("%d", &n);if (n < 0) {printf("错误：阶乘不能为负数！\n");return 0;}if (n > 1000) {printf("错误：阶乘过大！\n");return 0;}factorial(n);return 0;}这个程序使用一个自定义的`BigNum` 结构体来表示大数，其中`digits` 数组存储数位，`length` 表示数字的长度（即数位数）。