Java数据结构和算法(第二版)第六章 编程作业

/**	Java数据结构和算法(第二版)第六章 编程作业
/**	Programming Projects in Chapter 6, Data Structure & Algorithms in Java 2nd Edition
 * 	by puladiao
 * 	http://blog.verypod.com
 */
// 6.3 递归解决N次方问题
public class Power {
	public static void main(String[] args) {
		System.out.println(doPower(2, 4));
	}

	public static long doPower(long base, long power) {
		long result = 1;
		if (power == 1) {
			result = base;
		} else {
			long factor = 1;
			if (power % 2 == 1) {
				factor = base;
			}
			power = power / 2;
			result = doPower(base, power) * doPower(base, power) * factor;
		}
		return result;
	}
}

// 6.4 递归解决背包问题
public class Knapsack {

	private static int[] arr = new int[] { 5, 6, 7, 8, 11 };

	public static void main(String[] args) {
		System.out.println(doKnapsack(arr.length-1, 20));
	}

	public static boolean doKnapsack(int n, int sum) {
		if (sum == 0) {
			return true;
		} 
		if (sum < 0 || (sum > 0 && n < 0)) {
			return false;
		} 
		if (doKnapsack(n - 1, sum - arr[n])) {
			System.out.println(arr[n]);
			return true;
		}
		System.out.printf("%d %d\n", arr[n],sum);
		return doKnapsack(n-1,sum);
	}
}

// 6.5 递归解决组合问题
public class Picker {
	static char[] arr = new char[] { 'A', 'B', 'C', 'D', 'E' };

	public static void main(String[] args) {
		Picker p = new Picker();
		p.pick(0, 5, 3, "");
	}

	// s为当前index,t为总数,n为组合数
	public void pick(int s,int t,int n,String str){
		if(n==1){
			for(int i=s;i<t+s;i++){
			System.out.println(str+arr[i]);
			}
		} else if(s<5) {
			//System.out.println(s);
			pick(s+1,t-1,n-1,str+arr[s]);
			pick(s+1,t-1,n,str);
		}
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注