From Gossip@caterpillar

Algorithm Gossip: 數字拆解

說明

這個題目來自於數字拆解，我將之改為C語言的版本，並加上說明。

題目是這樣的：

3 = 2+1 = 1+1+1 所以3有三種拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

共七種

依此類推，請問一個指定數字NUM的拆解方法個數有多少個？

解法

我們以上例中最後一個數字5的拆解為例，假設f( n )為數字n的可拆解方式個數，而f(x, y)為使用y以下的數字來拆解x的方法個數，則觀察：

5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

使用函式來表示的話：

f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5)

其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1)，但是使用大於1的數字來拆解1沒有意義，所以f(1, 4) = f(1, 1)，而同樣的，f(0, 5)會等於f(0, 0)，所以：

f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0)

依照以上的說明，使用動態程式規畫（Dynamic programming）來進行求解，其中f(4,1)其實就是f(5-1, min(5-1,1))，f(x, y)就等於f(n-y, min(n-x, y))，其中n為要拆解的數字，而min()表示取兩者中較小的數。

使用一個二維陣列表格table[x][y]來表示f(x, y)，剛開始時，將每列的索引0與索引1元素值設定為1，因為任何數以0以下的數拆解必只有1種，而任何數以1以下的數拆解也必只有1種：

for(i = 0; i < NUM +1; i++){
table[i][0] = 1; // 任何數以0以下的數拆解必只有1種
table[i][1] = 1; // 任何數以1以下的數拆解必只有1種
}

接下來就開始一個一個進行拆解了，如果數字為NUM，則我們的陣列維度大小必須為NUM x (NUM/2+1)，以數字10為例，其維度為10 x 6我們的表格將會如下所示：

1 1 0 0 0 0
1 1 0 0 0 0
1 1 2 0 0 0
1 1 2 3 0 0
1 1 3 4 5 0
1 1 3 5 6 7
1 1 4 7 9 0
1 1 4 8 0 0
1 1 5 0 0 0
1 1 0 0 0 0

實作

#include <stdio.h> 
#include <stdlib.h> 
#define NUM 10    //  要拆解的數字 
#define DEBUG 0 

int main(void) { 
    int table[NUM][NUM/2+1] = {0}; // 動態規畫表格 
    int count = 0; 
    int result = 0; 
    int i, j, k; 

    printf("數字拆解\n"); 
    printf("3 = 2+1 = 1+1+1 所以3有三種拆法\n"); 
    printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1");   
    printf("共五種\n"); 
    printf("5 = 4 + 1 = 3 + 2 = 3 + 1 + 1");
    printf(" = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1");
    printf("共七種\n"); 
    printf("依此類推，求 %d 有幾種拆法？", NUM); 

    // 初始化 
    for(i = 0; i < NUM; i++){ 
        table[i][0] = 1;  // 任何數以0以下的數拆解必只有1種 
        table[i][1] = 1;  // 任何數以1以下的數拆解必只有1種 
    }        

    // 動態規劃 
    for(i = 2; i <= NUM; i++){ 
       for(j = 2; j <= i; j++){ 
            if(i + j > NUM) // 大於 NUM 
                continue; 
            
            count = 0;    
            for(k = 1 ; k <= j; k++){ 
                count += table[i-k][(i-k >= k) ? k : i-k];                  
            } 
            table[i][j] = count; 
        }            
    } 

    // 計算並顯示結果 
    for(k = 1 ; k <= NUM; k++) 
        result += table[NUM-k][(NUM-k >= k) ? k : NUM-k];                    
    printf("\n\nresult: %d\n", result); 

    if(DEBUG) { 
        printf("\n除錯資訊\n"); 
        for(i = 0; i < NUM; i++) { 
            for(j = 0; j < NUM/2+1; j++) 
                 printf("%2d", table[i][j]); 
            printf("\n"); 
        } 
    } 

    return 0; 
}