输入一个正整数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
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=0;k--){
if(a[k]){
//在数组中从后往前遍历,找到第一个不为0的数,记录此时数组中k的位置
break;
}
}
//输出结果,因为我们是按照从低位到高位计算的,但是我们要按照从高位到低位输出
for(int i=k;i>=0;i--){
cout<<a[i];
}
return 0;
}
以上就是对于本题的解题思路了。如果你觉得我的文章对你有用请点个赞支持一下吧,喜欢我写的文章那么请点个关注再走哟。如果此文章有错误或者有不同的见解欢迎评论或者私信。
我是ACfun:一个成长中的程序猿,感谢大家的支持。