數字拆解


說明

這個題目來自於 JavaWorld@TW 數字拆解。題目是這樣的：
3 = 2 + 1
  = 1 + 1 + 1 所以 3 有三種拆法（包括 3 本身）
4 = 3 + 1
  = 2 + 2
  = 2 + 1 + 1
  = 1 + 1 + 1 + 1 五種（包括 4 本身）
5 = 4 + 1
  = 3 + 2
  = 3 + 1 + 1
  = 2 + 2 + 1
  = 2 + 1 + 1 + 1
  = 1 + 1 + 1 + 1 + 1 七種（包括 5 本身）

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

解法

我們以上例中第三個數字 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)，也就是數字1只會有一種拆法，也就是 1 本身，同樣地，f(0, 5) 會等於 f(0, 0)，也就是數字 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 * (NUM / 2 + 1)。以數字 10 為例，其維度為10 * 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    JavaScript    Haskell

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

void init(int[][NUM / 2 + 1]);
int min(int, int);
int f(int[][NUM / 2 + 1], int, int);
void dp(int[][NUM / 2 + 1]);
int count(int[][NUM / 2 + 1]);
void print(int[][NUM / 2 + 1]);

int main(void) { 
    int table[NUM][NUM / 2 + 1] = {0};

    init(table);
    dp(table);
    printf("可拆解出 %d 組數字\n", count(table)); 

    if(DEBUG) { print(table); }

    return 0; 
}

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

int min(int a, int b) { return a > b ? b : a; }

int f(int table[][NUM / 2 + 1], int x, int y) {
    int c, i;
    for(c = 0, i = 1 ; i <= y; i++) { c += table[x - i][min(x - i, i)]; }
    return c;
}

void dp(int table[][NUM / 2 + 1]) {
    int x;
    for(x = 2; x < NUM; x++){ 
        int y;
        for(y = 2; y < NUM / 2 + 1 && y <= x; y++) if(x + y <= NUM) {
            table[x][y] = f(table, x, y); 
        }
    } 
}

int count(int table[][NUM / 2 + 1]) {
    int i, result;
    for(i = 1, result = 0 ; i <= NUM; i++) {
        result += table[NUM - i][(NUM - i >= i) ? i : NUM - i];
    }
    return result;
}

void print(int table[][NUM / 2 + 1]) {
    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"); 
    } 
}

  • Java
import java.util.Arrays;

public class Number {
    private static int[][] table(int number) {
        int[][] table = new int[number][number / 2 + 1];
        for(int i = 0; i < table.length; i++) { 
            table[i][0] = table[i][1] = 1;
        }
        return table;
    }
    
    private static int f(int[][] table, int x, int y) {
        int c = 0;
        for(int i = 1 ; i <= y; i++) { 
            c += table[x - i][Math.min(x - i, i)]; 
        }
        return c;
    }
    
    private static int[] dp(int[][] table, int x) {
        int[] row = Arrays.copyOf(table[x], table[x].length);
        for(int y = 2; y < row.length && y <= x; y++) {
            if(x + y <= table.length) { row[y] = f(table, x, y); }
        }
        return row;
    }
    
    private static int[][] dp(int[][] table) {
        table = Arrays.copyOf(table, table.length);
        for(int x = 2; x < table.length; x++) { table[x] = dp(table, x); } 
        return table;
    }
    
    private static int count(int[][] table) {
        int result = 0;
        for(int i = 1; i <= table.length; i++) {
            result += table[table.length - i][
                (table.length - i >= i) ? i : table.length - i];
        }
        return result;
    }
    
    public static int ofDeconstructions(int number) {
        return count(dp(table(number)));
    }
    
    public static void main(String[] args) {
        System.out.printf("可拆解出 %d 組數字%n", 
            Number.ofDeconstructions(10));
    }
}

  • Python
def table(number):
    return [[1, 1] + [0] * (number // 2 - 1)] * number

def f(table, x, y):
    def c(i):
        return table[x - i][min(x - i, i)] + c(i + 1) if i <= y else 0
    return c(1)

def dpRowOf(table, x):
    return table[x][0:2] + [f(table, x, y) 
        if y <= x and x + y <= len(table) 
        else table[x][y] for y in range(2, len(table[x]))]
    
def dp(table):
    def dp(t, x):
        return dp(t[0:x] + 
            [dpRowOf(t, x)] + t[x + 1:], x + 1) if x < len(t) else t
    return dp(table, 2)
    
def count(table):
    def j(i): return i if len(table) - i >= i else len(table) - i
    return sum([table[len(table) - i][j(i)] 
        for i in range(1, len(table) + 1)])

def numOfDecons(number): return count(dp(table(number)))

print("可拆解出 %d 組數字\n" % numOfDecons(10))

  • Scala
import scala.math.min
import List.fill

def table(number: Int) = fill(number)(List(1, 1) ++ fill(number / 2 - 1)(0))

def f(table: List[List[Int]], x: Int, y: Int) = {
    def c(i: Int): Int = 
        if(i <= y) table(x - i)(min(x - i, i)) + c(i + 1) else 0
    c(1)
}
    
def dpRowOf(table: List[List[Int]], x: Int) = {
    table(x).take(2) ++ (for(y <- 2 until table(x).size) yield 
        (if(y <= x && x + y <= table.size) f(table, x, y) 
         else table(x)(y)))
}
    
def dp(table: List[List[Int]]) = {
    def idp(t: List[List[Int]], x: Int): List[List[Int]] = {
        if(x < t.size) 
            idp(t.take(x) ++ (dpRowOf(t, x) :: t.drop(x + 1)) , x + 1)
        else t
    }
    idp(table, 2)
}

def count(table: List[List[Int]]) = {
    def j(i: Int) = if(table.size - i >= i) i else table.size - i
    (for(i <- 1 to table.size) yield table(table.size - i)(j(i))).sum
}

def numOfDecons(number: Int) = count(dp(table(number)))

println("可拆解出 %d 組數字%n".format(numOfDecons(10)))

  • Ruby
# encoding: Big5
def table(number); [[1, 1] + [0] * (number / 2 - 1)] * number end

def f(table, x, y)
    c = ->(i) { i <= y ? table[x - i][[x - i, i].min] + c.call(i + 1) : 0 }
    c.call(1)
end
        
def dpRowOf(table, x)
    table[x].take(2) + (2...10).map { |y|
        y <= x && x + y <= table.size ? f(table, x, y) : table[x][y]
    }
end
    
def dp(table)
    dp = ->(t, x) {
        x < t.size ? dp.call(
            t.take(x) + [dpRowOf(t, x)] + t.drop(x + 1), x + 1) : t
    }
    dp.call(table, 2)
end 

def count(table)
    j = ->(i) { table.size - i >= i ? i : table.size - i }
    (1..table.size).map { |i| table[table.size - i][j.call(i)] }.reduce(:+)
end

def numOfDecons(number); count(dp(table(number))) end
    
printf("可拆解出 %d 組數字\n", numOfDecons(10))

  • JavaScript
Array.prototype.fill = function(n, ele) {
    var arr = this.slice(0, this.length);
    for(var i = 0; i < n; i++) { arr.push(ele); }
    return arr;
};

function table(number) {
    var table = [];
    for(var i = 0; i < number; i++) {
        table[i] = [1, 1].fill(parseInt(number / 2) + 1, 0);
    }
    return table;
}

function f(table, x, y) {
    var c = 0;
    for(var i = 1 ; i <= y; i++) { 
        c += table[x - i][Math.min(x - i, i)]; 
    }
    return c;
}

function dpRowOf(table, x) {
    var row = table[x].slice(0, table[x].length);
    for(var y = 2; y < row.length && y <= x; y++) {
        if(x + y <= table.length) {
            row[y] = f(table, x, y);
        }
    }
    return row;
}

function dp(table) {
    table = table.slice(table, table.length);
    for(var x = 2; x < table.length; x++) { 
        table[x] = dpRowOf(table, x);
    }
    return table;
}

function count(table) {
    var result = 0;
    for(var i = 1; i <= table.length; i++) {
        result += table[table.length - i][
                (table.length - i >= i) ? i : table.length - i];
    }
    return result;
}

function numOfDecons(number) { return count(dp(table(number))); }

print('拆解組數：' + numOfDecons(10))

  • Haskell
table number =
    replicate number ([1, 1] ++ replicate (number `div` 2 - 1) 0)

f table x y = c 1
    where c i = if i <= y 
                    then table !! (x - i) !! min (x - i) i + c (i + 1) 
                    else 0

dpRowOf table x =
    (take 2 (table !! x)) ++
        [if y <= x && x + y <= length table 
            then f table x y 
            else table !! x !! y | y <- [2 .. length (table !! x) - 1]]

dp table = idp table 2
    where 
        idp t x =
            if x < length t 
                then idp (take x t ++ (dpRowOf t x : drop (x + 1) t)) (x + 1)
                else t

count table = 
    foldl (+) 0 [table !! (len - i) !! (j i) | i <- [1 .. len]]
    where j i = if len - i >= i then i else len - i
          len = length table

numOfDecons = count . dp . table

main = putStrLn \$ "Number of deconstructions: " ++ (show \$ numOfDecons 10)