[藍橋杯][基礎訓練]階乘計算(不了解你錘我)

問題描述

Description

輸入一個正整數n，輸出n!的值。

其中n!=123*…*n。

Input

輸入包含一個正整數n，n≤1000。

Output

輸出n!的準确值。

Sample Input

10

Sample Output

3628800

More Info

n!可能很大，而計算機能表示的整數範圍有限，需要使用高精度計算的方法。

使用一個數組A來表示一個大整數a，A[0]表示a的個位，A[1]表示a的十位，依次類推。

将a乘以一個整數k變為将數組A的每一個元素都乘以k，請注意處理相應的進位。首先将a設為1，然後乘2，乘3，當乘到n時，即得到了n!的值。

問題解法

使用一個數組存一個數字的方法，極為繁瑣，接下來的方法，一定能夠讓你了解的。

我們使用數組的一個地方來存4為數字，相對10進制來說，這是10000進制，即上一數字滿10000,下一個數字加一，題目中最大的n為1000,這意味這，目前位置乘完之後，最多向下一位進位，不可能向下下一位進位。于是有了下面的代碼。

完整代碼

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int data[10005];
    int temp[10005];
    int n,r,t1,tail;
    memset(data,0,sizeof(data));
    cin >> n;
    if(n <= 1) return 1;
    int head = 0;
    data[0] = 1;
    for (int i = 1; i <= n; i++) {
        t1 = 0;
        for (int j = 0; j <= head; j++) {
            // !!! 模拟手工計算 目前位相乘後加上進位數
            r = data[j] * i + t1;
            if(r >= 10000){
                // !!! 計算出進位數字
                t1 = r / 10000;
                data[j] = r % 10000;
                // !!! 最大位+1
                if(j == head) head++;
            }else{
                data[j] = r;
                t1 = 0;
            }
        }
    }
    printf("%d",data[head]);
    for (int i = head - 1; i >= 0; i--) {
        // !!! %04d 是列印4位，不足的用零來填充
        printf("%04d",data[i]);
    }
    cout << endl;
    return 0;
}
           

參考連結

https://www.jianshu.com/p/25b49190305e