2011年9月22日 星期四

[ 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(23) = 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 :
  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

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

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...