C++クラシックアルゴリズム問題-デジタル分解

31.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

全部で7種類
このように、指定された数値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)であり、nは分解すべき数字であり、f(n-y, min(n-x, y))は両者のうち小さい数を表す.
2 Dアレイテーブル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  
#include 
#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("    
");
        printf("3 = 2+1 = 1+1+1   3     
");
        printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1");
        printf("   
");
        printf("5 = 4 + 1 = 3 + 2 = 3 + 1 + 1");
        printf(" = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1");
        printf("   
");
        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("

result: %d
", result);

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

        return 0;
    }