大数阶乘求法
大数阶乘求法
方绍伟 发表于4年前
大数阶乘求法
  • 发表于 4年前
  • 阅读 37
  • 收藏 1
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

一、递归方法
这个是最容易想的,如果是1的阶乘,则返回1,其他的都返回n-1的阶乘与n的积,循环调用即可。不过问题是即使用double来存放该值,由于double本身的精度、能存的数字大小所限,算不了太大的数的阶乘。
二、数组方法
思路:用data数组来存放阶乘的每一位数字,首先令第一位的数值为1,位数为1,然后将每次相乘的乘积存回数组,并循环处理每个数组中超过10的数,若数值超过10,则需要进位,将位数加1,原来的数除以10,商数加前一位数的数值后存回前一位数的数组中,再将余数存回原来位数的数组中。
例如求5!的值
步骤一:
1!=1
位数1
数组内容0      0      0      1
步骤二:
2!=2*1!=2
位数1
数组内容0      0      0      2
步骤三:
3!=3*2!=3*2=6
位数1
数组内容0      0      0      6
步骤四:
4!=4*3!=4*4=24
位数1
数组内容0      0      0      24
因为24大于10,需要进位
data[1]=data[1]+data[0]/10=0+2=2
data[0]=data[0]%10=4
所以数组内容为0      0      2      4
位数2
步骤五:
5!=5*4!=5*24=120
位数2
数组内容为0      0      2*5      4*5
即0      0      10      20
因为data[0]大于10,需要进位
data[1]=data[1]+data[0]/10=10+2=12
data[0]=data[1]%10=0
此时数组内容为0      0      12      0
data[2]=data[2]+data[1]/10=0+1=1
data[1]=data[1]%10=2
位数加1
数组内容为0      1      2      0
一次类推,可以计算大数的阶乘,代码如下:
#include <stdio.h>

int main(void)
{
       int Data[10001];
       int digit;
       int i,j,r,k;
       int N;
    
       for(i=1;i<10000+1;i++)
          Data[i]=0;
       Data[0]=1;
       Data[1]=1;
       digit=1;
    
       printf("Enter a number what you want to calculus:");
       scanf("%d",&N);
    
       for(i=1;i<N+1;i++)
       {
           for(j=1;j<digit+1;j++)
               Data[j]*=i;
           for(j=1;j<digit+1;j++)
           {
               if(Data[j]>10)
               {
                   for(r=1;r<digit+1;r++)
                   {
                       if(Data[digit]>9)
                           digit++;
                       Data[r+1]+=Data[r]/10;
                       Data[r]=Data[r]%10;
                   }
               }
           }
       }
       printf("%d!=",N);
       for(k=digit;k>0;k--)
           printf("%d",Data[k]);
       return 0;
}

具体算法中有最朴实的乘法运算思想,请各位细细体味。
#include 
int main()
{

int n;                                             //阶乘大小
printf("请输入n的大小:");
scanf("%d",&n);                                    //从键盘接收阶乘大小
int a[200];                                        //确保保存最终运算结果的数组足够大
int carry;                                         //进位
int digit = 1;                                     //位数
a[0] = 1;                                          //将结果先初始化为1
int temp;                                          //阶乘的任一元素与临时结果的某位的乘

积结果
         
for(int i = 2; i <= n; ++i)                        //开始阶乘,阶乘元素从2开始依次“登场


{
          //按最基本的乘法运算思想来考虑,将临时结果的每位与阶乘元素相乘 
   for(int 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;                 //新加一位,添加信息。位数增1
    carry /= 10;                               //看还能不能进位
   }
}

printf("结果是:\n%d ! = ",n);                      //显示结果
for(int i = digit; i >=1; --i)
{
   printf("%d",a[i-1]);
}
return 0;
}

#include<stdio.h>
#include<stdlib.h> // for malloc()
#include<string.h> // for memset()
#define QUOTIETY 4 // 内存分配系数,计算10000以内阶乘设置为4就足够,如果需要
                     // 计算更大的数的阶乘,则将该系数适当增大

void process(const int index, int *result);
int cnt = 1;

int main(void)
{
    int index = 0;
    int input = 0;
    int *result = NULL;

    // 获得输入数据
    printf("请输入你要计算的阶乘数,内存有限,请不要超过10000:\n");
    scanf("%d", &input);
    while (input <= 0 || input > 10000)
    {
        printf("请输入合理的数据,谢谢:\n");
        scanf("%d", &input);
    }
    
    // 申请空间储存计算结果
    result = (int *)malloc(sizeof(int) * input * QUOTIETY);
    if (result == NULL)
    {
        printf("内存申请失败!\n");
        exit(-1);
    }
    memset(result, 0, sizeof(int) * input * QUOTIETY); // 初始化存储空间
    result[0] = 1;

    // 进行阶乘计算
    for ( index = 1; index <= input; ++index)
    {
        process(index, result);
    }

    // 打印结果
    for (index = cnt - 1; index >= 0L; --index)
    {
        printf("%d", result[index]);
    }
    putchar('\n');
    printf("结果一共有%d位数!\n", cnt);

    free(result);
    return 0;
}

/*
* 计算阶乘核心代码
*/
void process(const int index, int *result)
{
    int product = 0; // 乘积
    int carry = 0;    // 进位
    int remainder = 0; // 余数
    int i = 0;

    for (i = 0; i < cnt; ++i)
    {
        product = result[i] * index + carry;
        carry = product / 10;
        remainder = product % 10;
        result[i] = remainder;
    }

    if (carry != 0)
    {
        while (carry / 10 != 0)
        {
            result[cnt] = carry % 10;
            carry /= 10;
            ++cnt;
        }
        result[cnt++] = carry;
    }
}

共有 人打赏支持
粉丝 7
博文 60
码字总数 1947
×
方绍伟
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: