【題解筆記】PTA基礎6-10：階乘計算升級版

題目地址：https://pintia.cn/problem-sets/14/problems/742

前言

咱目前還只能說是個小白，寫題解是為了后面自己能夠回顧，如果有哪些寫錯的/能優化的地方，也請各位多指教，( ?? ω ?? )

題目描述

本題要求實作一個列印非負整數階乘的函式，要求能處理一定大數值的階乘，

void Print_Factorial ( const int N );

#include <stdio.h>

void Print_Factorial ( const int N );

int main()
{
    int N;
    
    scanf("%d", &N);
    Print_Factorial(N);
    return 0;
}

/* 你的代碼將被嵌在這里 */

15

1307674368000

想法

怎么儲存如此之大的階乘結果

不看不知道，細看嚇一跳，題目中對N的限制是0<=N<=1000，得想個辦法讓程式儲存1000!這么大的一個數，

掃視了一圈C語言的基本資料型別，就連unsigned long long型別也遠存不下1000的階乘，

轉換一下思路，數字每一位之間都是緊挨在一起的，我們其實可以采用一種連續的資料結構來儲存這個結果，比如....陣列！

設陣列第一個元素表示個位，第二個元素表示十位...以此類推，這樣一來，我們就可以用陣列以數位升序來儲存這個大數了，最后只需將陣列中的每個元素(int)列印到螢屏上即可，

給陣列分配多少個元素

題目的裁判測驗程式并沒有引入stdlib.h頭檔案，因此我沒法使用動態記憶體分配/回收函式，而1000!的結果到底有多少位，我一時半會兒也是不知道的，

其實可以用最簡單粗暴的方式估計一下：1000個1000相乘

這樣算出來的結果有3001位，如果是運算1000!的話，是怎么也不會算出3001個數位的數字的，所以分配3000個元素一定能保證陣列能裝得下結果的所有數位，

注：有一種可以用來計算階乘近似值的公式——斯特林公式

實作乘法時關注的物件

階乘運算的基礎是乘法運算，只要把正確的乘法演算法寫出來，這道題咱們就幾乎能解決了！

關于乘法演算法，我覺得要關注以下三種情況：

1. 無需進行進位操作

   

   每一位數字乘上因數后均未超過9，無需進位，

2. 需要進行進位操作

   

   假設當前處理的是十位，十位數字乘上因數后為12，超過了9，將12“拆成”1和2，將最低位2保留下來，其余的數位1進入高位，

3. 需要進行進位操作，而且進了一位后的數位又可以再進一位

   

   假設當前處理的是百位，百位數字乘上因數后為49，超過了9，將49“拆成”4和9，將最低位9保留下來，其余的數位4進入高位，

   然而此時發現，之前在處理十位時，十位上的數字被拆分為1和4，其中1進入到百位，而百位現在的數字是9，9+1又可以向后進一位，

   9+1=10，因此將0保留下來，而1進入高位，加上之前進入高位的數字4，現在進入高位的數字是4+1=5，

   注：這是很容易被忽略的一種情況，

根據以上描述，可以發現在每次迭代中，我關注的是：

1. 當前處理的數位
2. 進入到下一位的數值

處理乘法中的進位

上面給出的演示中，進入高位的數字都沒有超過9，那么如果要進入高位的數字超過了9怎么辦呢？

實際上這里和上面的處理方法是差不多的，

每次迭代中處理進到當前數位的數值時，將待進位的數值中的最低位進到當前的數位，在去除待進位的數值中的最低位后，剩余的數值留到后面處理更高位的進位，

咱做了一個動圖來直觀地演示一下這個程序：

代碼實作乘法部分

這里只截取了乘法部分，完整代碼可以看下方題解代碼

// arr是按數位儲存結果的陣列
// arrLen是上述陣列的長度，也代表了結果數值的位數
// factor是每次迭代中要乘上的因數

// 將陣列每一位都乘i，并進行進位處理(超過9的數字往高處進)
int j;
int carry = 0; // 要進到高位的數字
int multiplied; // 用于臨時儲存陣列中每一位數字乘了因數之后的值
int calcDigit; // 用于臨時儲存新計算出來的某一個數位
for (j = 0; j < arrLen; j++) {
    multiplied = arr[j] * factor; // 每一位都乘i
    // multiplied % 10 取 <當前數位×因數> 的最低位，比如6*3=18>9，這個時候取出8，而1要進到高位
    // carry % 10 將 <上一次迭代留給本次迭代進位的數值> 的最低位取出，這一位是進到 <當前正在處理的數位> 的
    calcDigit = multiplied % 10 + carry % 10;
    // 運算留給 <下一次迭代> 進位的數值(carry)
    // 將 <進到當前數位的值> 去掉最低位(因為最低位在上面已經進到當前數位了)，加上multiplied要進到高位的數字
    carry = carry / 10 + multiplied / 10; 
    // 一種很容易錯的情況，雖然multiplied % 10和carry % 10分別不會>=10，但是他們加起來是可能>=10的！
    // 也就是說，當前處理的數位在進位后可能>=10，需要再處理一道
    // 這種時候還要再進一次位
    if (calcDigit >= 10) {
        // 將除最低位外的數位加到 <下一次迭代> 進位的數值(carry)上
        carry += calcDigit / 10; 
        // 當前數位只保留最低位
        calcDigit %= 10;
    }
    // 存入最終運算出來的當前數位的值
    arr[j] = calcDigit;
    // j到陣列邊界了，但是還有要進到高位的數值，這說明位數不夠了，那么就增加位數（增加陣列元素）
    if (j >= arrLen - 1 && carry > 0) 
        arrLen++;
}

題解代碼

部分正確

這部分正確的代碼錯就錯在忽略了當前數位的二次進位問題，

void Print_Factorial(const int N) {
    if (N < 0) {
        printf("Invalid input");
        return;
    }
    int arr[3000] = {}; 
    arr[0] = 1; 
    int arrLen = 1; 
    int factor = 2; 
    for (; factor <= N; factor++) {
        int j;
        int carry = 0; 
        int multiplied; 
        for (j = 0; j < arrLen; j++) {
            multiplied = arr[j] * factor; 
            arr[j] = multiplied % 10 + carry % 10;
            carry = carry / 10 + multiplied / 10; 
            // 這里少考慮了一種情況
            if (j >= arrLen - 1 && carry > 0) 
                arrLen++;
        }
    }
    int i;
    for (i = arrLen - 1; i >= 0; i--) {
        printf("%d", arr[i]);
    }
}

Accepted

void Print_Factorial(const int N) {
    if (N < 0 || N > 1000) {
        printf("Invalid input");
        return;
    }
    /*
        如果階乘結果大到C語言中任意一種基本資料型別都無法表達，
        不妨考慮一下能不能用某種資料結構來解決問題
        這里采用陣列
    */
    /* 1000個1000相乘：1*(10^(3*1000))=1e+3000,
        結果是1000000000....(3000個零)
        而本題N不超過1000，階乘結果肯定也達不到1e+3000,
        這里就給陣列分配3000個元素
    */
    // 從陣列第一個元素為個位開始，往后數位升高
    int arr[3000] = {}; // 全初始化為0
    arr[0] = 1; // 個位為1
    int arrLen = 1; // 標記陣列目前元素個數(結果位數)
    int factor = 2; // 從2開始乘，因為arr[0]=1
    for (; factor <= N; factor++) {
        int j;
        int carry = 0; 
        int multiplied; 
        int calcDigit; 
        for (j = 0; j < arrLen; j++) {
            multiplied = arr[j] * factor; 
            calcDigit = multiplied % 10 + carry % 10;
            carry = carry / 10 + multiplied / 10; 
            if (calcDigit >= 10) {
                carry += calcDigit / 10;
                calcDigit %= 10;
            }
            arr[j] = calcDigit;
            if (j >= arrLen - 1 && carry > 0) 
                arrLen++;
        }
    }
    // 列印結果數字
    int i;
    // 因為隨著下標增加，數位升高，要列印出來正常的數值就得倒著遍歷陣列
    for (i = arrLen - 1; i >= 0; i--) {
        printf("%d", arr[i]);
    }
}

提交結果截圖

• WA

  

• AC

  

標籤：其他

上一篇：狀態空間_1

下一篇：參加了個演算法比賽，真是一言難盡啊