|
精华帖 (1) :: 良好帖 (0) :: 新手帖 (10) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-06-07
最后修改：2010-06-07
8. 数字迷问题。 9. 简单分治问题。 10. 大整数乘法。 11. 取数问题。 12. 币值统计问题。 13. 子集分划问题。 14. 最X序列问题。 15. 硬币找钱问题。 input： 输入6个整数和一个2位小数的实数，分别代表可以使用的各种面值的硬币个数和付款金额。 16. 作业调度问题。 比如： 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：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] + " "); // 输出所取每种币值的数量
}
}
}
|
| 返回顶楼 | |
|
发表时间：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 |
| 返回顶楼 | |
|
发表时间：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;
}
}
|
| 返回顶楼 | |
浏览 2307 次
