## 2011年9月22日 星期四

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

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) 共七種

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(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 :
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==0return 0;              // s(0,y) or s(x,0) = 0
15.         else if(x==1 || y==1return 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==0return 0;                          // f(0)=0
62.         else if(x==1return 1;                     // f(1)=1
63.         else if(x==2return 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

## 關於我自己

Where there is a will, there is a way!