计算n!的准确值（n＞=1000）

谁践踏了优雅 2022-11-13 01:55 170阅读 0赞

题目描述：  
高精度数值计算，计算n！的准确值（n>=1000）

在解此类高精度数值计算要求的题目时，需要在算法设计时采用合适的数据结构算法，将高精度数值的运算转化为计算机中可以表示的数的运算，在计算中，通常将结果的每一位或者若干位截下来放到一个数组中去或逐次输出。

思路：使用一个一维数组存放阶乘值，将阶乘的个位数放在数组的第一个元素，十位数放在第二个元素，以此类推。当(k-1)!存放在数组中时，要求k!，则应由低位至高位依次将数组的各元素乘k，以积的个位数作为数组当前位置的新值，积除以10的商的整数部分作为向高位的进位加到较高位的乘积上去。

思路有了之后，就可以去写代码了，不过有些地方非常容易出错，这道题我查了很多文章，发现很多人的代码对于运行小的阶乘没有问题，但是一旦到大的阶乘就会出错，下面是这道题的正确答案：

正确解答的代码如下：

#include <iostream>
    using namespace std;
    int main()
    { 
      int result[40000]; //保存结算结果的数组
      int height = 1;  //结果的最高位
      int num;  //计算阶乘的数字
      cin>>num;
      result[0] = 1;
      for (int i=1;i<=num;i++)
      { 
        int res = 0; //进位
        for (int j=0;j<height;j++)
        { 
          int buf = result[j] * i + res; //计算结果
          result[j] = buf % 10;  //取当前位
          res = buf / 10;   //计算进位
        }
        while (res)  //这个while循环是很多人都会写错的，很多人在此处用的if
        { 
          result[height++] = res % 10; //取当前位
          res /= 10;   //计算进位
        }
      }
    
      for (int k=height-1;k>=0;k--)
      { 
         cout<<result[k];
      }
      cout<<endl;
      cout<<"length="<<height<<endl;
    }

解释一点：  
对于这个地方：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]  
这个while循环，为什么这样去处理，假设最高位数字为9，当前阶乘到88，正好在最高位上，上一次的进位为0：

9x88=792  
792%10=2  
792/10=79  
如果是if语句的话，那么此时最高位存的是79，与我们最初设想的数组每个位置存储的数字位数为1不一致，后面就会出现错误。所以当你使用if的时候，虽然对于10!这样的结果不会出现错误，但是对于5000！这样的问题，结果就会出现错误。下面贴一下5000！前面一些位的结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]  
参考：  
https://blog.csdn.net/gaoshou7126/article/details/37932313

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]: /images/20221022/5329318b2f9445e9b2333b12f64b6716.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]: /images/20221022/4bdc2f17587748df9252563e76ef5c63.png