數字拆解算法分析及實作（C/OC）

數字拆解簡介

 這個題目來自于數字拆解，我将之改為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

代碼實作（C/OC）

#define NUM 12    //  要拆解的數字
#define DEBUG 1
           

//主程式（建議依據算法分析來看）
int table[NUM][NUM/2+1] = {0}; // 動态規劃表格
int count = 0;
int result = 0;
int i, j, k;
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++){//周遊2-NUM，循環内，i看做一個不變的數，是以是要計算i行的資料了
    for(j = 2; j <= i; j++){//j又開啟了一個子循環
        if(i + j > NUM) // 大于 NUM，i循環進入下一次
            continue;
        
        count = 0;//臨時的值，用于統計表中某元素對應的值，每次j循環時清零
        for(k = 1 ; k <= j; k++){
            count += table[i-k][(i-k >= k) ? k : i-k];//取小的值（套用公式，還是先了解一下公式的好，犀利）
        }
        table[i][j] = count;//将計數指派給第i行，第j列
    }
}

// 計算并顯示結果
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("%3d", table[i][j]);
        printf("\n");
    }
}