藍橋杯【基礎練習】階乘計算（高精度）

資源限制

時間限制：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!的準确值。

樣例輸入

10

樣例輸出

3628800

思路

題目提示得很清晰，當位數較大時，普通整型将無法容納這樣的大整數，是以采用數組的形式來存儲這個大整數，然後進行相應的計算。注意處理進位和不必要的乘0計算

當符合下面三個條件即可終止循環，避免不必要的乘0計算，提高效率

1. 目前位原有數值為0

2. 前一位的進位數值為0

3. 目前位已經超過原數值的最大位數 

（細節——避免了在數值的中間出現連續的0元素而導緻提前終止的情況）

代碼

#include<iostream>
using namespace std;
int main() {
	int n;
	cin>>n;
	int length=1;
	int a[10000]={1};//初始化各個元素 
	for(int i=1;i<=n;i++){
		int p=0;
		int carry=0;//進位 
		while(1){
			//模拟乘法計算的過程，類似豎式計算，滿十進一 
			int product=a[p]*i+carry; 
			a[p]=product%10;
			carry=product/10;
			p++;
			if(a[p]==0&&carry==0&&p>=length) break; //進行多餘0元素的排除，提前終止乘法運算 
		}
		length=p;
	}
	for(int i=length-1;i>=0;i--) cout<<a[i];
	return 0;
}
           

同理，高精度加法有着異曲同工之處 ：藍橋杯【基礎練習】高精度加法

結合這兩題來體會用數組來解決高精度系列問題的巧妙之處！