[ Algorithm in Java ] 集合問題 : 數字拆解

轉載自 這裡
題目說明 :
考慮某個數字可能的組合或拆解, 這邊以數字 3,4,5 進行說明 : 

3(第1種) = 2+1(第2種) = 1+1+1(第3種) 所以3有三種拆法
4(1) = 3 + 1(2) = 2 + 2(3) = 2 + 1 + 1(4) = 1 + 1 + 1 + 1(5) 共五種
5(1) = 4 + 1(2) = 3 + 2(3) = 3 + 1 + 1(4) = 2 + 2 + 1(5) = 2 + 1 + 1 + 1(6) = 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(5, 5) + f(5, 4) + f(5, 3) + f(5, 2) + f(5 ,1)

其中 f(5, 5) 與 f(5, 1) 都會是1, 因為一個數字使用小於等於一來組合該數字的可能性只有一種. 而 f(5, 3)=2, f(5, 2)=2...
接著我們觀察 f(5, 2), 可以看成 2 + (...). 而 (...) 的合為 5-2=3 (使用小於2的數字來組合). 故 f(5, 2) 可以看成 f(3, 2) + f(3, 1)!
如果是 f(5, 3), 可以看成 3 + (...). 而 (...) 的合為 5-3=2. 因此 f(5, 3) 可以看成 f(2, 3) = f(2, 2). 用更精確的寫法就是 :

f(x, y) = f(x-y, min((x-y), y)) ; f(1, y)=f(x, 1)=f(x, x) or f(y, y)=1

實作 :

- NumberSet.java :

view plaincopy to clipboardprint?

1. package alg.set;  
2.   
3. public class NumberSet {  
4.     private int num=0;  
5.       
6.     public NumberSet(){}  
7.     public NumberSet(int num)  
8.     {  
9.         this.num = num;  
10.     }  
11.   
12.     public int subFun(int x, int y)  
13.     {  
14.         if(x==0 || y==0) return 0;              // s(0,y) or s(x,0) = 0  
15.         else if(x==1 || y==1) return 1;         // s(1,y) or s(x,1) = 1       
16.         else if(x==y) return 1;                 // s(x,y) under x=y, = 1  
17.         else if(y>x)                         // s(x,y) under y>x, = f(x)  
18.         {  
19.             return numSetfun(x);  
20.         }  
21.         else                                       
22.         {  
23.             // s(x,y) under x>y and z=x-y then  
24.             // if z<=y, then f(z)  
25.             // if z>y , then s(z,y)+s(z,y-1)+...+s(z,1)  
26.             int z = x-y;  
27.             if(z<=y) return numSetfun(z);  
28.             else   
29.             {  
30.                 int sum = 0;  
31.                 for(int i=y; i>=1; i--) sum+=subFun(z,i);  
32.                 return sum;  
33.             }  
34.         }  
35.     }  
36.     public int numSetfun(){return numSetfun(num);}  
37.     public int numSetfun(int x){  
38.         int sum = 0;  
39.         for(int i=x; i>=1; i--) sum+=subFun(x, i); // f(x)=s(x,x-1)+s(x,x-2)...+s(x,1)  
40.         return sum;  
41.     }  
42.       
43.     public static int min(int x, int y) {return x>y?y:x;}  
44.       
45.     /** 
46.      * BD : 
47.      *  Using Dynamic programming 
48.      * @param x 
49.      * @return 
50.      */  
51.     public int dymNumsetFun(int x)  
52.     {  
53.         //    | 1       2       3       4  
54.         //  ====================================  
55.         //  1 | s(1,1)  s(1,2)  s(1,3)  s(1,4)  
56.         //  2 | s(2,1)  s(2,2)  s(2,3)  s(2,4)  
57.         //  3 | s(3,1)  s(3,2)  s(3,3)  s(3,4)  
58.         //  4 | s(4,1)  s(4,2)  s(4,3)  s(4,4)  
59.         //  
60.         //  Based on this matrix, f(3)=s(3,3)+s(3,2)+s(3,1)  
61.         if(x==0) return 0;                          // f(0)=0  
62.         else if(x==1) return 1;                     // f(1)=1  
63.         else if(x==2) return 2;  
64.         else   
65.         {  
66.             int mtx[][] = new int[x][x];  
67.             for(int i=0; i
68.             {  
69.                 mtx[0][i]=1;        // s(1,y)=1  
70.                 mtx[i][0]=1;        // s(x,1)=1  
71.                 mtx[i][i]=1;        // s(x,y) and x=y, =1  
72.             }  
73.             for(int i=2; i
74.                 for(int j=1; j<=i; j++)  
75.                 {  
76.                     int z = i-j;  
77.                     int m = min(z,j+1)-1;  
78.                     for(int k=0; k<=m; k++) {  
79.                         mtx[i][j]+=mtx[z-1][k];  
80.                     }  
81.                 }  
82.             int sum=0;  
83.             for(int i=0; i1][i];  
84.             return sum;  
85.         }         
86.     }  
87.       
88.     public int getNum() {  
89.         return num;  
90.     }  
91.   
92.     public void setNum(int num) {  
93.         this.num = num;  
94.     }  
95.   
96.     public static void main(String args[])  
97.     {  
98.         //NumberSet ns = new NumberSet(4);  
99.         //System.out.println("Number "+ns.getNum()+" has "+ns.numSetfun()+" possible sets.");  
100.         System.out.println("=====Using Dynamic Programming=====");  
101.         NumberSet ns = new NumberSet();  
102.         long st = System.currentTimeMillis();  
103.         for(int i=50; i<=55; i++)  
104.         {  
105.             System.out.println("Number "+i+" has "+ns.dymNumsetFun(i)+" possible sets.");  
106.         }  
107.         System.out.println("\t[Performance] Spending time="+(System.currentTimeMillis()-st)+" ms");  
108.         System.out.println("=====Using Recursive Method=====");  
109.         st = System.currentTimeMillis();  
110.         for(int i=50; i<=55; i++)  
111.         {  
112.             System.out.println("Number "+i+" has "+ns.numSetfun(i)+" possible sets.");  
113.         }  
114.         System.out.println("\t[Performance] Spending time="+(System.currentTimeMillis()-st)+" ms");  
115.     }  
116. }  

執行結果 :

=====Using Dynamic Programming=====
Number 50 has 204226 possible sets.
Number 51 has 239943 possible sets.
Number 52 has 281589 possible sets.
Number 53 has 329931 possible sets.
Number 54 has 386155 possible sets.
Number 55 has 451276 possible sets.
[Performance] Spending time=11
=====Using Recursive Method=====
Number 50 has 204226 possible sets.
Number 51 has 239943 possible sets.
Number 52 has 281589 possible sets.
Number 53 has 329931 possible sets.
Number 54 has 386155 possible sets.
Number 55 has 451276 possible sets.
[Performance] Spending time=38

可以看出來使用 Dynamic programming 比用 Recursive method 更有效率, 但是使用 Recursive method 寫的 code 會比較簡潔且易讀!