• 周二. 8月 16th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

大数据阶乘(The factorial of large data)

admin

11月 28, 2021
题目描述 Description
阶乘是计算中的基础运算,虽然规则简单,但是位数太多了,也难免会出错。现在的问题是:给定任意位数(long long类型)的一个数,求它的阶乘,请给出正确结果。为提高速度,保证给定运算的结果均为正整数。
 输入输出格式 Input/output
输入格式:
一行:一个long long类型的数
输出格式:
一个正整数,表示计算的结果(不可以有前导0)
 输入输出样例 Sample input/output
样例测试点#1
输入样例#1:
3
输出样例#1:

6

输入样例#2:
4
输出样例#2:

24

思路:这题的数据量很大,long long类型的,如果直接计算是不可取的,必须用高精度算法。
这里可以分为几个函数来计算:
①乘法函数:专题里面会细细地讲的
倒序输出函数:专题里面会细细地讲的
③阶乘函数:要把增序的数转换成数组,再传入乘法函数进行计算
代码如下:
 1 #include <stdio.h>
 2 #include <string.h>
 3 /*=============================================================*/
 4                                   /////////乘法函数////////////// 
 5     
 6 void mul(int a[],int b[])//正整数的高精度运算 a*b ---> c
 7 {
 8     int i=0,j=0,x=0,lenc=0;
 9     int c[99999]; 
10     memset(c,0,sizeof(c));//清零 
11     for(i=1;i<=a[0];i++)
12     {
13         x=0;//表示进位
14         for(j=1;j<=b[0];j++)
15         {
16             c[i+j-1]=c[i+j-1]+a[i]*b[j]+x;
17             x=c[i+j-1]/10;
18             c[i+j-1]=c[i+j-1]%10;
19         }
20         c[i+b[0]]=x;//表示进位(向c的更高位进位)
21     }
22     lenc=a[0]+b[0];
23     while(c[lenc]==0&&lenc>1)  lenc--;
24     c[0]=lenc;
25     for(i=0;i<=lenc;i++)//重新存入数组a 
26     {
27         a[i]=c[i];
28     }
29 }
30 /*==============================================================*/
31                                 /////////倒序输出函数////////////// 
32 void output(int c[])//倒序输出 
33 {
34     int i;
35     for(i=c[0];i>=1;i--)
36     {
37         printf("%d",c[i]);
38     } 
39     printf("
");    
40 }
41 /*==============================================================*/
42                                    /////////计算阶乘函数///////////
43 void kee(long long n)     
44 {    
45     int h,p=0,r=0,q=0;//一堆for用的东西 
46     int i,k=0;//k记录b数组的有多少号元素 
47     int b[99999]={0};//依次增加乘数 
48     int a[99999]={1,1};//当前被乘数 
49     for(i=1;i<=n;i++)
50     {
51         h=1;
52         p=i; 
53         while(p>0)//把阶乘数i转换成数组
54         {
55             b[h]=p%10;
56             p=p/10;
57             k++;
58         }
59         b[0]=k;
60         mul(a,b);//传入乘法函数 
61     }
62     output(a);//输出结果 
63 }
64 /*==============================================================*/
65                                         /////////主函数///////////
66 int main()
67 {    
68     long long n; 
69     scanf("%I64d",&n);
70     if(n==1||n==2)//如果是1、2的话,输出即可 
71     {
72         printf("%I64d
",n);
73     }
74     else if(n<0)
75     {
76         printf("Wrong Answer!
");
77     }
78     else kee(n);//传入阶乘函数 
79     return 0;
80 }

发表回复

您的电子邮箱地址不会被公开。