是否很久没抽象和逻辑了呢？ DODO它吧(很基础)二

8. 数字迷问题。
   A B C A B
 X         A
 ------------
 D D D D D D

9. 简单分治问题。
   用递归分治法求出n个元素集合中的最大值和最小值。

10. 大整数乘法。
    设计一个有效地算法，进行两个n(n<256)位大整数的乘法运算。

11. 取数问题。
    有两个人轮流取2n个数中的n个数，所取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。

12. 币值统计问题。
    某单位给每个职工发工资(精确到元)，为了保证不要临时归还零钱且取款的张数最少，取工资前需要统计出所有职工的工资所需
各种币值(100,50,20,10,5,2,1元共7种)的张数，请编程完成。

13. 子集分划问题。
    给定正整数n, 计算出n个元素的集合{1,2,...,n}可以划分为多少个不同的非空子集。

14. 最X序列问题。
    找出由n个数组成的序列的最长单调递增子序列。

15. 硬币找钱问题。
    有6种不同面值的硬币，各硬币的面值分别为5分、1角、2角、5角、1元和2元。先要用这些面值的硬币来购物和找钱。
购物时可以使用的各种面值的硬币个数存于数组coins[6]中，商店里各面值的硬币有足够多。在一次购物中希望使用最少硬币个数。
    对于给定的各种面值的硬币个数和付款金额，编程计算使用硬币个数最少的交易方案。

    input： 输入6个整数和一个2位小数的实数，分别代表可以使用的各种面值的硬币个数和付款金额。
    output：最少硬币个数。 如果不可能完成交易，则输出"impossible"。

16. 作业调度问题。
    n个作业(1,2,...,n)要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工顺序都是现在M1上加工，
然后再M2上加工。M1和M2加工作业i所需要的时间分别为ai和bi。确定这n个作业的最优加工顺序，使得从第一个
作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需要的时间最少。

    比如：
    n=3
    -------------------------------------------------
     作业i          机器M1           机器M2
      1               2                1
      2               3                1
      3               2                3
    -------------------------------------------------
    这3个作业的6种可能的调度方案是(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1),它们所对应的完成时间和分别是19，18，20，21，
19，19. 显而易见，最佳调度方案是(1,3,2)，其完成时间和为18.

评论

3 楼 maozj 2010-06-09  

16. 作业调度问题。

package abstractandlogic;

/**
 * 16. 作业调度问题。 n个作业(1,2,...,n)要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工顺序都是现在M1上加工，
 * 然后再M2上加工。M1和M2加工作业i所需要的时间分别为ai和bi。确定这n个作业的最优加工顺序，使得从第一个
 * 作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需要的时间最少。
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.08
 * 
 */
public class WorkAttemper {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 3;
		int[][] job = { { 0, 0, 0 }, { 0, 2, 1 }, { 0, 3, 1 }, { 0, 2, 3 } };
		WorkAttemper wa = new WorkAttemper(n, job);
		wa.tryi(1);
		int[] x = wa.getBestx();
		int bestf = wa.getBestf();

		for (int i = 1; i <= n; i++) {
			System.out.print(x[i] + " ");
		}
		System.out.println();
		System.out.println(bestf);

	}

	private int n; // n个作业
	private int[] x; // n个作业
	private int[][] job; // 作业在机器1和机器2上的时间
	private int[] bestx; // 最优作业调度顺序
	private int bestf; // 最短时间
	private int f1 = 0; // 作业在机器1上完成的时间
	private int[] f2; // 作业在机器2上完成的时间
	private int f; //完成总的时间和

	/**
	 * 构造
	 * 
	 * @param _n
	 * @param _job
	 */
	public WorkAttemper(int _n, int[][] _job) {
		n = _n;
		x = new int[n + 1];
		bestx = new int[n + 1];
		job = new int[n + 1][3];
		for (int i = 1; i <= n; i++) {
			x[i] = i;
			for (int j = 1; j <= 2; j++) {
				job[i][j] = _job[i][j];
			}
		}
		bestf = 32767;
		f1 = 0;
		f2 = new int[n + 1];
		f = 0;
	}

	/**
	 * 递归回溯
	 * 
	 * @param i
	 */
	public void tryi(int i) {
		if (i == n + 1) {
			for (int j = 1; j <= n; j++) {
				bestx[j] = x[j];
				bestf = f;
			}
		} else {
			for (int j = i; j <= n; j++) {
				f1 += job[x[j]][1];

				if (f2[i - 1] > f1) {
					f2[i] = f2[i - 1] + job[x[j]][2];
				} else {
					f2[i] = f1 + job[x[j]][2];
				}
				
				f += f2[i];
				if (f < bestf) {
					swap(x, i, j);
					tryi(i + 1);
					swap(x, i, j);
				}
				f -= f2[i];
				f1 -= job[x[j]][1];
			}
		}
	}

	/**
	 * 交换
	 * 
	 * @param x
	 * @param i
	 * @param j
	 */
	private void swap(int[] x, int i, int j) {
		int temp = x[i];
		x[i] = x[j];
		x[j] = temp;

	}

	/**
	 * 获得最优调度顺序
	 * 
	 * @return
	 */
	public int[] getBestx() {
		return bestx;
	}

	/**
	 * 获得作业完成最短时间
	 * 
	 * @return
	 */
	public int getBestf() {
		return bestf;
	}

}

2 楼 maozj 2010-06-08  

8. 数字迷问题

package abstractandlogic;

/**
 * 8. 数字迷问题。 ABCAB * A = DDDDDD
 * 
 * @sincejdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.08
 * 
 */
public class NumberAnagram {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int D;
		int A;

		for (D = 1; D <= 9; D++) {
			int S = D * 100000 + D * 10000 + D * 1000 + D * 100 + D * 10 + D;
			for (A = 2; A <= 9; A++) {
				int R = S / A;
				int A0 = R / 10000;
				char[] ch = (R + "").toCharArray();
				int len = ch.length;
				if (A == A0) {
					if (len == 5) {
						if (ch[0] == ch[3] && ch[1] == ch[4] && ch[0] != ch[2]
								&& ch[1] != ch[2]) {
							System.out.print(ch);
							System.out.print(" * " + ch[0] + " = " + S);
						}
					}
				}
			}
		}

	}
}

输出：
37037 * 3 = 111111

1 楼 maozj 2010-06-08  

12. 币值统计问题。

package abstractandlogic;

/**
 * 12. 币值统计问题。 某单位给每个职工发工资(精确到元)，为了保证不要临时归还零钱且取款的张数最少，取工资前需要统计出所有职工的工资所需
 * 各种币值(100,50,20,10,5,2,1元共7种)的张数，请编程完成。
 * 
 * 贪心策略：币值从大到小排序
 * 
 * @sincejdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.07
 * 
 */
public class CurrencyStatistics {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		CurrencyStatistics cs = new CurrencyStatistics();
		int n = 148; // 职工工资
		cs.currencyStatistics(n);

	}

	private int[] cv = { 100, 50, 20, 10, 5, 2, 1 }; // 币值从大到小排列
	private int[] s = new int[cv.length]; // 每种币值所取的数量

	/**
	 * 币值统计
	 * 
	 * @param n
	 */
	public void currencyStatistics(int n) {
		for (int i = 0; i < cv.length; i++) {
			int count = n / cv[i];
			s[i] = count;
			n -= (count * cv[i]);
		}

		for (int i = 0; i < s.length; i++) {
			System.out.print(s[i] + " "); // 输出所取每种币值的数量
		}
	}

}