算法练习：砍树，不相邻（JAVA实现）

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

package net.mldream.datang;/* * 问题域：一排N棵树，现在要砍掉K（K<N）棵树,要求砍掉的2棵树之间不相邻，问有几种看法。 * 边界分析：如果K>N-K+1,则即使每个间隔都砍树，也还不能达到目标。 */public class ShutTrees {/* * ①一种思路：把问题转换一下角度，可以看作相当有一排N-K棵树，现在要插入K棵树，且不能插在同一个间隔中。 * 思路总结：简单的说，其实就是在求一种排列方法，这样就能轻而易举的解决这个问题。 * 具体解法：在N-K+1个间隙中选择K个位置(即：固定元素个数集合的固定元素个数子集问题)。 */public void shut(int n,int k){int num[] = new int[n=k+1] ;for(int i=0;i<num.length;i++) {//初始化num[i] = i ;}getNfromM(num,k) ;}/* * 附赠：经典ACM算法-Algorithm Gossip: m元素集合的n个元素子集 * 提出问题：假设有个集合拥有m个元素，任意的从集合中取出n个元素，则这n个元素所形成的可能子集有那些？ * 算法思路： * 假设有5个元素的集点，取出3个元素的可能子集如下： *{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} *这些子集已经使用字典顺序排列，如此才可以观察出一些规则： *如果最右一个元素小于m，则如同码表一样的不断加1  *如果右边一位已至最大值，则加1的位置往左移  *每次加1的位置往左移后，必须重新调整右边的元素为递减顺序  *所以关键点就在于哪一个位置必须进行加1的动作，到底是最右一个位置要加1？还是其它的位置？ */public static void getNfromM(int num[],int n) {for(int i=0;i<n;i++) {//生成并且显示第一个子集num[i] = i+1 ;System.out.print(num[i]) ;}System.out.println("") ;int position = n-1;int m=num.length ;while(true) {if(num[n-1]==m) {position --;} else {position = n-1 ;}num[position]++ ;//调整右边的元素for(int i=position+1;i<n;i++) {num[i] = num[i-1] +1 ;}for(int i=0;i<n;i++) {System.out.print(num[i]) ;}System.out.println("") ;if(num[0] >= m-n+1) break;}}/* * ②另一种思路：直面问题，N棵树砍掉K棵树。根据条件限制，怎么选择的问题。 * 思路总结：一颗一颗树顺序的做出选择，选择砍掉和选择不砍掉，并且条件为不相邻。 * 具体解法：采用DP（动态规划）的思想，依次进行决策，当所有决策序列完成之时，问题也就得到了解决。 * 1：判断当前树是否砍掉 * 2：如果砍掉，则问题域变为剩下的N-2棵树砍掉K-1棵树（因为相邻的树不能砍，所以剩下N-1-1） * 3：如果不砍掉，则问题域变为剩下的N-1棵树砍掉K棵树 * 4：如果剩下供选择的树总树为M，需砍掉的树为J，如果M为奇数，则如果J<M/2+1终止，J=M/2+1相隔树全部选择砍掉； *  如果M为偶数，则如果J<M/2终止，J=M/2时相隔树全部选择砍掉。 */public void shut2(int n,int k){}/* * 测试实例MAIN方法 */public static void main(String[] args) {new ShutTrees().shut(10,6) ;}}

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