C语言程序设计（第2版）-2期 经验技巧6-2 大数阶乘优化算法.pdf
版权申诉
98 浏览量
2022-07-12
22:12:06
上传
评论
收藏 69KB PDF 举报
经验技巧
6-2
大数阶乘优化算法
【例 6-6】给出了大数阶乘的算法，该算法使用数组存放阶乘的结果，每一
个数组元素存放结果的一位。计算十万的阶乘需要近 260 秒的时间，实际上只要
程序中的 N 足够大，还可以求更大数的阶乘，但程序执行的时间会更长，可能
要几个小时，甚至更长，因此需要考虑对算法进行优化。
int 型数组的每一个元素可以存放的最大整数为 2147483647，是一个十位数，
而算法中每一个元素只存放结果的一位，显然太浪费了。
由于算法中需要计算自然数 n 与数组元素值的乘积加上前一位的进位，所以
每个数组元素的位数不能太多，否则将超过最大整数 2147483647 而导致溢出，
如果每个数组元素存放 4 位数，大约可计算到二十万的阶乘，确保结果是精确的，
如果再使用无符号基本整型，大约可计算到四十万的阶乘，确保结果是精确的。
由此，定义符号常量 M 的值为 10000 作为模数，符号常量 B 的值为 4 表示
数组元素存放的最多位数，符号常量 N 的值为 600000 表示 n!结果位数的 B 分之
一，存放 n!结果的数组 bit 定义为静态无符号基本整型。
计算 i!时将原来的用 10 除处理进位和余数改为用 M 除。
由于除存放最高位的元素外，每个元素都存放 B 位，而存放最高位的元素
可能不足 B 位，输出前需先统计存放最高位元素 bit[k]的位数，另外，低位的 0
（只能输出一个 0）和不足 B 位的应使用 B 个输出域宽，不足的用 0 补足，才能
保证其它各位均输出 B 位。
其它说明详见程序代码中的注释。
优化的程序代码
：
（1）
#include "stdio.h"
（2）
#define M 10000//M
与
n
的乘积不能超过
4294967295
（3）
#define B 4//
数组元素存放的最多位数
（4）
#define N 600000 //n!
的位数，要足够大
（5）
int fact(int bit[],int n)
（6）
{
（7）
int i,j,k=N-1,carry;//k
表示第一个非
0
元素的下标
（8）
bit[k]=1;
（9）
for(i=2;i<=n;i++)
（10）
{
（11）
carry=0;//carry
表示进位数，开始进位数为
0
（12）
for(j=N-1;j>=k;j--)
（13）
{
评论0
最新资源