题目信息

问题描述

 输入一个正整数n，输出n!的值。
 其中n!=123*…*n。

算法描述

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

输入格式

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

输出格式

 输出n!的准确值。

样例输入

10

样例输出

3628800

解题思路

主要考察

 本题给出的主要考察关键字是：高精度。首先我们要明白什么是高精度算法：

 高精度算法，属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。

通过上面的解释再加上题目提供的算法描述，我们就可以明白如何使用高精度算法来求一个数的阶乘了。

解题思路

 如果已经明白了后面这段文字可以跳过，直接看代码，代码里也有相应的解释。计算过程实际上就是在模拟我们算乘法的过程，我们将存大数的数组初始化为1，然后我们从2开始乘直到相乘到n。比如我们定义存储的数组为a[]。我们使a[0]存储数字的个位，a[1]存储十位，a[2]存储百位……依次类推。当我们计算到数字k的时候我们从a[0]开始使数组中的每一个元素乘以k（这也是我们计算乘法的方法），在将每一位乘以k的同时我们要注意进位问题，我们使用一个变量carry来存储进位并将其初始化为0。每次的都将(a[i]*k)+carry，即该位数乘以k加上上一次的进位数。然后我们再将该结果对10取模，求出当前结果的个位数并将该数存到当前位置，然后再将该数除以10求出当前结果的进位数。不断的进行循环最终就可以求出结果。
注意：

• 计算之前一定要将数组的每一位初始化为0
• 由于我们是从低位向高位计算存储的，所以我们输出的时候应该倒着输出，即从高位到低位输出。这里我们初始化数组的空间为4000，如果我们直接倒着输出肯定会先输出很多很多的0,所以我们需要倒着遍历一下数组，直到数组元素不为0为止，我们将这个数标记为k，然后输出时我们直接从k倒着输出即可

解题代码

#include<iostream> using namespace std; #define MAX 4000  int main(){ int a[MAX] = {0}; //将每一位初始化为0  int n;  cin>>n;  a[0] = 1; //初始化数组中的数为 1   //从 2 一直乘到 n  for(int i=2;i<=n;i++){ int carry = 0; //用carry记录进位  //每次都将当前数组中存储的数字乘以 i   for(int j=0;j<MAX;j++){ int t = a[j]*i + carry; //将数组中当前的数的每一位乘以j,在加上上一位的进位     a[j] = t%10; //将当前位置乘以 i 的结果保存到j位     carry = t/10; //计算进位，如果超过10，保留的会是十位上的数，不超10 carry 为 0  } } int k; //使用k来标记数组的长度  for(k = MAX-1;k>=0;k--){ if(a[k]){ //在数组中从后往前遍历，找到第一个不为0的数，记录此时数组中k的位置  break; } } //输出结果，因为我们是按照从低位到高位计算的，但是我们要按照从高位到低位输出  for(int i=k;i>=0;i--){   cout<<a[i]; } return 0; } 

 以上就是对于本题的解题思路了。如果你觉得我的文章对你有用请点个赞支持一下吧，喜欢我写的文章那么请点个关注再走哟。如果此文章有错误或者有不同的见解欢迎评论或者私信。

我是ACfun：一个成长中的程序猿，感谢大家的支持。