算法练习:砍树,不相邻(JAVA实现)

问题域:一排N棵树,现在要砍掉K(K<N)棵树,要求砍掉的2棵树之间不相邻,问有几种看法。
边界分析:如果K>N-K+1,则即使每个间隔都砍树,也还不能达到目标。

[java][/java] view plaincopyprint?
  1. package net.mldream.datang;
  2. /*
  3.  * 问题域:一排N棵树,现在要砍掉K(K<N)棵树,要求砍掉的2棵树之间不相邻,问有几种看法。
  4.  * 边界分析:如果K>N-K+1,则即使每个间隔都砍树,也还不能达到目标。
  5.  */
  6. public class ShutTrees {
  7.     /*
  8.      * ①一种思路:把问题转换一下角度,可以看作相当有一排N-K棵树,现在要插入K棵树,且不能插在同一个间隔中。
  9.      * 思路总结:简单的说,其实就是在求一种排列方法,这样就能轻而易举的解决这个问题。
  10.      * 具体解法:在N-K+1个间隙中选择K个位置(即:固定元素个数集合的固定元素个数子集问题)。
  11.      */
  12.     public void shut(int n,int k){
  13.         int num[] = new int[n=k+1] ;
  14.         for(int i=0;i<num.length;i++) {//初始化
  15.             num[i] = i ;
  16.         }
  17.         getNfromM(num,k) ;
  18.     }
  19.     /*
  20.      * 附赠:经典ACM算法-Algorithm Gossip: m元素集合的n个元素子集
  21.      * 提出问题:假设有个集合拥有m个元素,任意的从集合中取出n个元素,则这n个元素所形成的可能子集有那些?
  22.      * 算法思路:
  23.      * 假设有5个元素的集点,取出3个元素的可能子集如下:
  24.      *{1 2 3}、{1 2 4 }、{1 2 5}、{1 3 4}、{1 3 5}、{1 4 5}、{2 3 4}、{2 3 5}、{2 4 5}、{3 4 5}
  25.      *      这些子集已经使用字典顺序排列,如此才可以观察出一些规则:
  26.      *      如果最右一个元素小于m,则如同码表一样的不断加1
  27.      *      如果右边一位已至最大值,则加1的位置往左移
  28.      *      每次加1的位置往左移后,必须重新调整右边的元素为递减顺序
  29.      *      所以关键点就在于哪一个位置必须进行加1的动作,到底是最右一个位置要加1?还是其它的位置?
  30.      */
  31.     public static void getNfromM(int num[],int n) {
  32.         for(int i=0;i<n;i++) {//生成并且显示第一个子集
  33.             num[i] = i+1 ;
  34.             System.out.print(num[i]) ;
  35.         }
  36.         System.out.println(“”) ;
  37.         int position = n-1;
  38.         int m=num.length ;
  39.         while(true) {
  40.             if(num[n-1]==m) {
  41.                 position –;
  42.             } else {
  43.                 position = n-1 ;
  44.             }
  45.             num[position]++ ;
  46.             //调整右边的元素
  47.             for(int i=position+1;i<n;i++) {
  48.                 num[i] = num[i-1] +1 ;
  49.             }
  50.             for(int i=0;i<n;i++) {
  51.                 System.out.print(num[i]) ;
  52.             }
  53.             System.out.println(“”) ;
  54.             if(num[0] >= m-n+1) break;
  55.         }
  56.     }
  57.     /*
  58.      * ②另一种思路:直面问题,N棵树砍掉K棵树。根据条件限制,怎么选择的问题。
  59.      * 思路总结:一颗一颗树顺序的做出选择,选择砍掉和选择不砍掉,并且条件为不相邻。
  60.      * 具体解法:采用DP(动态规划)的思想,依次进行决策,当所有决策序列完成之时,问题也就得到了解决。
  61.      *      1:判断当前树是否砍掉
  62.      *      2:如果砍掉,则问题域变为剩下的N-2棵树砍掉K-1棵树(因为相邻的树不能砍,所以剩下N-1-1)
  63.      *      3:如果不砍掉,则问题域变为剩下的N-1棵树砍掉K棵树
  64.      *      4:如果剩下供选择的树总树为M,需砍掉的树为J,如果M为奇数,则如果J<M/2+1终止,J=M/2+1相隔树全部选择砍掉;
  65.      *                                           如果M为偶数,则如果J<M/2终止,J=M/2时相隔树全部选择砍掉。
  66.      */
  67.     public void shut2(int n,int k){
  68.     }
  69.     /*
  70.      * 测试实例MAIN方法
  71.      */
  72.     public static void main(String[] args) {
  73.         new ShutTrees().shut(10,6) ;
  74.     }
  75. }

没完善的,之后补上。。。有更好的算法的童鞋,望告知!!!

标签