大家好，我是Ziyang。欢迎大家来到我的博客，希望能和大家多多交流。地址：https://www.cnblogs.com/ziyang1060/。
大数阶乘
由于阶乘的结果会呈几何级数增长，即使在如今的64位字长的计算机中，能表示的大小也是有限的，只能保存20的阶乘。
那我们如何求很大的数的阶乘呢？（例如1000！）
这里我们不考虑复杂的大整数函数，而尝试用一种简单的求大数阶乘的办法。
思路:
将多位数相乘化解为一位数相乘，例如：
已知 11! = 39916800
此时，我们想要得出 12！
当我们将 11! 的每一位数都乘以12后，总的结果就变得十分简单明了。我们只需从最低位开始，依次考虑该位的进位问题，假如说这个位上是96，那么就要往上一位进9，以此类推。
代码如下：
//求大数阶乘 https://blog.csdn.net/Ziyang1060
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int find_digit(int num);//返回阶乘结果的位数
void factorial(int* fact, int digit, int num);
int find_pos(int* fact, int digit);
void process_carry(int* fact, int pos);
void output(int* fact, int digit, int num);
int main(void)
{
int num, digit;
int* fact = NULL;
scanf("%d", &num);//输入求阶乘的数:num!
digit = find_digit(num);
if (!(fact = (int*)calloc(digit , sizeof(int))))//动态分配并初始化为0
{
printf("分配数组空间失败!
");
return -1;
}
factorial(fact, digit,num);
output(fact, digit, num);
free(fact); fact = NULL;
return 0;
}
int find_digit(int num)
{
double digit_f = 0;
for (int i = 1; i <= num; i++)
{
digit_f += log10(i);
}
return (int)digit_f + 1;
}
void factorial(int* fact, int digit, int num)
{
int pos;//最高位的位数
fact[0] = 1;//设置第一位为1:0! = 1! = 1
for (int i = 2; i <= num; i++)
{
pos = find_pos(fact, digit);
for (int j = 0; j <= pos; j++)
{
fact[j] *= i;
}
process_carry(fact, pos);
}
}
int find_pos(int* fact, int digit)
{
for (int i = digit - 1; i >= 0; i--)//找到最高位
{
if (fact[i] != 0)
{
return i;
}
}
}
void process_carry(int* fact, int pos)
{
int carry = 0;//进位
for (int i = 0; i <= pos; i++)
{
fact[i] += carry;
if (fact[i] <= 9)
{
carry = 0;
}
if (fact[i] > 9 && i < pos)// 此时不是最高位
{
carry = fact[i] / 10;
fact[i] %= 10;
}
if (fact[i] > 9 && i == pos)// 此时为最高位
{
while (fact[i] > 9)
{
carry = fact[i] / 10;
fact[i] %= 10;
fact[++i] = carry;
}
}
}
}
void output(int* fact, int digit, int num)
{
int n = 0;
int m = 0;
int pos = find_pos(fact, digit);//最高位的索引
printf("
输出%d的阶乘结果:
", num);
for (int i = pos; i >= 0; i--)
{
printf("%d", fact[i]);
if (++m % 3 == 0)//每三个数字凑一组
{
printf(" ");
}
if (m == 3 * 13)//每一行输出13组
{
printf("
");
m = 0;
}
}
printf("
%d!共有%d位。
", num, pos + 1);
}
输出结果：
