蓝桥杯基础练习 BASIC-30 阶乘计算

水深无声 2023-10-06 09:42 28阅读 0赞

基础练习 阶乘计算

时间限制：1.0s 内存限制：512.0MB

问题描述

输入一个正整数 *n*，输出 *n*!的值。  
　　其中 *n*!=1\*2\*3\*…\* *n*。

算法描述

*n*!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组 *A*来表示一个大整数 *a*， *A*\[0\]表示 *a*的个位， *A*\[1\]表示 *a*的十位，依次类推。  
　　将 *a*乘以一个整数 *k*变为将数组 *A*的每一个元素都乘以 *k*，请注意处理相应的进位。  
　　首先将 *a*设为1，然后乘2，乘3，当乘到 *n*时，即得到了 *n*!的值。

输入格式

输入包含一个正整数 *n*， *n*<=1000。

输出格式

输出 *n*!的准确值。

样例输入

样例输出

3628800

示例代码：

1 #include<iostream>
     2 using namespace std;
     3 
     4 #define MAX_NUM 2600
     5 
     6 int a[MAX_NUM];        //保存大数，个位为a[0]，以此类推 
     7 
     8 int main() 
     9  {  
    10     int n; 
    11     cin >> n; 
    12     int x = n;     //先将n记录下来 
    13     
    14     for(int i = 0; n > 0; i++)     //逆着将数存入数组a 
    15     {    
    16             a[i] = n % 10;    //取最低位 
    17             n /= 10;        //去除最低位 
    18     }
    19     
    20     int carry, temp;    
    21     for(int i = x-1; i >= 2; i--)    //n x (n-1) x (n-2) x ... x 2
    22     { 
    23         carry = 0;      //进位 
    24         for(int j = 0; j < MAX_NUM; j++)
    25         {  
    26             temp = a[j] * i + carry;      //乘完后加上进位 
    27             a[j] = temp % 10;                //将末位存入a[j] 
    28             carry = temp / 10;          //将进位保存 
    29         }  
    30           
    31     }  
    32       
    33     bool flag = false;  //非零标志 
    34       
    35     for(int i=MAX_NUM - 1; i >= 0; i--)
    36     {  
    37         if(flag)
    38         {  
    39             cout << a[i];  
    40             continue; 
    41         }  
    42         if(a[i-1] != 0)    //如果当前位的下一位不为0，非零标志为真 
    43             flag = true;  
    44     }
    45 
    46     return 0; 
    47 }