加法因子

一個整數可以分解為整數因子的和，例如：: 3 = 2 + 1 = 1 + 1 + 1; 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

依此類推，若數字為 n，將 n + 0 算為一種（也就是包含 n 本身的話），3 可以有三種拆法，4 可以有五種拆法，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

程式實作：

#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"); 
    } 
}

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));
    }
}

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))

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)))

# encoding: UTF-8
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))

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))

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)