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

實作：C    Java    Python    Scala    Ruby

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

int main(void) { 
    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); 
    
    int table[NUM][NUM/2+1] = {0}; // 動態規畫表格 
    int count = 0; 
    int result = 0; 

    // 初始化 
    int i;
    for(i = 0; i < NUM; i++){ 
        table[i][0] = 1;  // 任何數以0以下的數拆解必只有1種 
        table[i][1] = 1;  // 任何數以1以下的數拆解必只有1種 
    }        
    // 動態規劃 
    for(i = 2; i <= NUM; i++){ 
       int j;
       for(j = 2; j <= i; j++){ 
            if(i + j > NUM) // 大於 NUM 
                continue; 
            
            count = 0;
            int k;
            for(k = 1 ; k <= j; k++){ 
                count += table[i-k][(i-k >= k) ? k : i-k];
            } 
            table[i][j] = count; 
        }            
    } 

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

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

    return 0; 
}

  • Java
public class Number {
    public static void main(String[] args){
       final int NUM = 10;

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

       int[][] table = new int[NUM][NUM / 2 + 1];
       int count = 0;
       for(int i = 0; i < NUM; i++) {
           table[i][0] = 1;
           table[i][1] = 1;
       }
       for(int i = 2; i <= NUM; i++) {
           for(int j = 2; j <= i; j++) {
               if(i + j > NUM) {
                   continue;
               }
               count = 0;
               for(int k = 1; k <= j; k++) {
                   count += table[i-k][(i-k >= k) ? k : i-k];
               }
               table[i][j] = count;
           }
       }
       int result = 0;
       for(int k = 1; k <= NUM; k++) {
           result += table[NUM-k][(NUM-k >= k) ? k : NUM-k];
       }
       System.out.printf("\n\nresult: %d\n", result);
       
    }
}

  • Python
NUM = 10

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

table = []
for i in range(NUM):
    table.append([0] * (NUM // 2 + 1))
count = 0

for i in range(NUM):
    table[i][0] = 1
    table[i][1] = 1

for i in range(2, NUM + 1):
    for j in range(2, i + 1):
        if i + j > NUM:
            continue
        count = 0
        for k in range(1, j + 1):
            count += table[i-k][k if i-k >= k else i-k]
        table[i][j] = count

result = 0
for k in range(1, NUM + 1):
    result += table[NUM-k][k if NUM-k >= k else NUM-k]
    
print("\n\nresult: ", result)

  • Scala
val NUM = 10
val table = new Array[Array[Int]](NUM, NUM / 2 + 1)
var count = 0

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

for(i <- 0 until NUM) {
    table(i)(0) = 1
    table(i)(1) = 1    
}
for(i <- 2 to NUM; j <- 2 to i if i + j <= NUM) {
    count = 0
    for(k <- 1 to j) {
        count += table(i - k)(if(i - k >= k) k else i - k)
    }
    table(i)(j) = count
}

var result = 0
for(k <- 1 to NUM) {
    result += table(NUM - k)(if(NUM - k >= k) k else NUM - k)
}
printf("\n\nresult: %d\n", result)

  • Ruby
# encoding: Big5

NUM = 10

puts "數字拆解"
puts "3 = 2 + 1 = 1 + 1 + 1 所以 3 有三種拆法"
puts "4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1"
puts "共五種"
puts "5 = 4 + 1 = 3 + 2 = 3 + 1 + 1"
puts "  = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1"
puts "共七種"

table = Array.new(NUM) {
    Array.new(NUM / 2 + 1, 0)
}

count = 0

NUM.times { |i|
    table[i][0] = table[i][1] = 1
}

2.upto(NUM) { |i|
    2.upto(i) { |j|
        if i + j > NUM
            next
        end
        count = 0
        1.upto(j) { |k|
            count += table[i - k][i-k >= k ? k : i - k]
        }
        table[i][j] = count
    }
}

result = 0
1.upto(NUM) { |k|
    result += table[NUM - k][NUM-k >= k ? k : NUM - k]
}

puts "依此類推，則 #{NUM} 會有 #{result} 種拆法"