1：有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* <pre>
* <strong>説明.</strong>
* 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
* 木杆很细，不能同时通过一只蚂蚁。
* 开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。
* 当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。
* 假设蚂蚁们每秒钟可以走一厘米的距离。
* 编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
* </pre>
*
* <pre>
* <strong>注意事項：</strong>
* </pre>
*
* <pre>
* <strong>使用例：</strong>
* </pre>
*/
public class TestDemo29 {
/** 全局变量：存放所有组合*/
private static Set<String> set = new HashSet<String>();
/** 所有方向组合的蚂蚁*/
private static List<Map> staticList = new ArrayList<Map>();
/**
* @param args
*/
public static void main(String[] args) {
List<Mayi> mayiList = getInitDat();
List<String> list = new ArrayList<String>();
Mayi mayi;
try {
// 获得所有蚂蚁的编号
for (int i = 0; i < mayiList.size(); i++) {
mayi = mayiList.get(i);
list.add(mayi.getNo());
}
// 将蚂蚁编号放入list通过doList方法决定他们的初始方向
for (int i = 0; i <= list.size(); i++) {
doList(list, i);
}
String zidx = "";
int idx;
for (Iterator<String> it = set.iterator(); it.hasNext();) {
zidx = it.next();
mayiList = getInitDat();
char[] ca = zidx.toCharArray();
for (char c : ca) {
idx = Integer.parseInt(String.valueOf(c)) - 1;
mayi = mayiList.get(idx);
mayi.setStaFx(1);
mayiList.remove(idx);
mayiList.add(idx, mayi);
}
staticList.add(doWay(mayiList));
}
// 做完上面这些我们已经的出每一种方向组合和他们离开木杆所用的时间
// 接下来只需要比较他们的时间大小便可
Map map = new HashMap();
int maxTime = Integer.parseInt(staticList.get(0).get("count").toString());
int minTime = maxTime;
for (Iterator<Map> it = staticList.iterator(); it.hasNext();) {
map = it.next();
int nowTime = Integer.parseInt(map.get("count").toString());
if (nowTime > maxTime) {
maxTime = nowTime;
} else if (minTime > nowTime) {
minTime = nowTime;
}
}
System.out.println(maxTime);
System.out.println(minTime);
// 上面已经的得到了最小和最大的时间，程序在这里就可以结束了。如果要得到对应的蚂蚁初始状态可以用下面的方法
for (Iterator<Map> it = staticList.iterator(); it.hasNext();) {
map = it.next();
if (maxTime == Integer.parseInt(map.get("count").toString())) {
System.out.println("最大时间:" + maxTime + "。蚂蚁初始状态是:" +map.get("putInitSta").toString());
}
if (minTime == Integer.parseInt(map.get("count").toString())) {
System.out.println("最小时间:" + minTime + "。蚂蚁初始状态是:" +map.get("putInitSta").toString());
}
}
} catch (IndexOutOfBoundsException ioe) {
System.out.println("数组越界");
} catch (Exception e) {
e.printStackTrace();
}
}
/**
* <TT><pRE>
* <p> 定义一个蚂蚁类. 其中三个参数no：蚂蚁编号、staXy：坐标、staFx：方向．</p>
* @author wangguanquan
*</PRE></TT>
*/
static class Mayi {
private String no; // 5只蚂蚁的编号
private int staXy; // 当前坐标(距离近点的距离)
private int staFx = -1; // 当前方向，设定初始方向为负(朝向近点为负，背向近点为正)
/**
* @return 编号
*/
public String getNo() {
return no;
}
/**
* @param 编号 設定する no
*/
public void setNo(String no) {
this.no = no;
}
/**
* @return 方向
*/
public int getStaFx() {
return staFx;
}
/**
* @param 方向 設定する staFx
*/
public void setStaFx(int staFx) {
this.staFx = staFx;
}
/**
* @return 当前坐标
*/
public int getStaXy() {
return staXy;
}
/**
* @param 当前坐标 設定する staXy
*/
public void setStaXy(int staXy) {
this.staXy = staXy;
}
}
/**
* <TT><pRE>
* <p> 取得5只蚂蚁的初始数据.</p>
* @return list
* </PRE></TT>
*/
protected static List<Mayi> getInitDat() {
List<Mayi> list = new ArrayList<Mayi>();
Mayi mayi = new Mayi();
mayi.setNo("1");
mayi.setStaXy(3);
list.add(mayi);
mayi = new Mayi();
mayi.setNo("2");
mayi.setStaXy(7);
list.add(mayi);
mayi = new Mayi();
mayi.setNo("3");
mayi.setStaXy(11);
list.add(mayi);
mayi = new Mayi();
mayi.setNo("4");
mayi.setStaXy(17);
list.add(mayi);
mayi = new Mayi();
mayi.setNo("5");
mayi.setStaXy(23);
list.add(mayi);
return list;
}
/**
* <TT><pRE>
* <p> 采用回溯法找出定长度所有可能的组合.</p>
* @param list 所有蚂蚁
* @param len 个数
* @return List 指定个数所有可能的组合
* @throws Exception 例外
* </PRE></TT>
*/
protected static List doList(List list, int len) throws Exception {
List<String> lst = new ArrayList<String>();
StringBuffer sb = null;
int begIdx = 0;
if (len == 0) {
set.add("");
return list;
}
if (len == 1) {
for (Iterator it = list.iterator(); it.hasNext();) {
set.add(it.next().toString());
}
return list;
}
while (begIdx < list.size() - len + 1) {
sb = new StringBuffer();
sb.append(list.get(begIdx));
List typeLst = doList(list.subList(begIdx + 1, list.size()), len - 1);
for (int i = 0; i < typeLst.size(); i++) {
sb.append(typeLst.get(i));
lst.add(sb.toString());
set.add(sb.toString());
sb.delete(1, sb.length());
}
begIdx++;
}
return lst;
}
/**
* <TT><pRE>
* <p> 根据条件移动木棍上的每一只蚂蚁.并计算移动时间</p>
* @param Map 返回组合和每种组合所用的时间
* @throws Exception 例外
* </PRE></TT>
*/
protected static Map doWay(List<Mayi> list) throws Exception {
Map map = new HashMap();
StringBuffer sb = new StringBuffer();
int count = 0;
Mayi mayi = null;
int staXy;
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i).staFx);
sb.append(", ");
sb.append(list.get(i).staXy);
sb.append("|");
}
// /测试代码，观察蚂蚁的初期情况/
// System.out.println(sb.toString());
// System.out.println("<------------" + count +"----------->");
// //
map.put("putInitSta", sb.toString());
List<Mayi> reFxList = reSetFx(list);
// 无限循环直到所有蚂蚁离开木杆
while (!win(reFxList)) {
for (int i = 0; i < reFxList.size(); i++) {
mayi = reFxList.get(i);
// 如果蚂蚁走出木棍将不进行移动
if (mayi.getStaXy() == 0 || mayi.getStaXy() == 27) {
continue;
}
// 移动在木棍上的蚂蚁
staXy = mayi.getStaXy() + mayi.getStaFx();
mayi.setStaXy(staXy);
reFxList.remove(i);
reFxList.add(i, mayi);
}
// 同一时间每只蚂蚁都在移动所以count++放在循环外，如果想知道一共移动了多少厘米将count++放在循环体内便可
count++;
// /测试代码，观察蚂蚁的每一步的移动情况/
// for (int i = 0; i < reFxList.size(); i++) {
// System.out.println(reFxList.get(i).staFx + "|" + reFxList.get(i).staXy);
// }
// System.out.println(">------------" + count +"-----------<");
// //
reFxList = reSetFx(reFxList);
}
map.put("count", count);
return map;
}
/**
* <TT><pRE>
* <p> 判断所有蚂蚁是否走出木棍.</p>
* @param list
* @return
* </PRE></TT>
*/
protected static boolean win(List<Mayi> list) {
Mayi mayi = null;
for (int i = 0; i < list.size(); i++) {
mayi = list.get(i);
if (mayi.getStaXy() != 0 && mayi.getStaXy() != 27) {
return false;
}
}
return true;
}
/**
* <TT><pRE>
* <p> 任意两只蚂蚁碰头时的方向处理.</p>
* @param list 碰头前的队伍
* @return list 碰头后的队伍
* @throws Exception 例外
* </PRE></TT>
*/
protected static List<Mayi> reSetFx(List<Mayi> list) throws Exception {
Mayi mayi = null;
int idx = 0;
while (idx < list.size() - 1) {
mayi = list.get(idx);
// 如果蚂蚁走出木棍将不进行调头
if (mayi.getStaXy() == 0 || mayi.getStaXy() == 27) {
idx++;
continue;
}
int nidx = idx + 1;
Mayi mayix = list.get(nidx);
// 当任意两只蚂蚁碰头时，两只蚂蚁同时调头朝反方向走。
if (mayi.getStaXy() == mayix.getStaXy()) {
mayi.setStaFx(mayi.getStaFx() * -1);
mayix.setStaFx(mayix.getStaFx() * -1);
list.remove(idx);
list.add(idx, mayi);
list.remove(nidx);
list.add(nidx, mayix);
}
idx++;
}
return list;
}
}
测试结果：
最大时间:24。蚂蚁初始状态是:1, 3|-1, 7|1, 11|1,17|-1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|-1, 7|1, 11|-1,17|1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|-1, 7|-1,11|-1, 17|1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|-1, 7|1, 11|-1,17|-1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|-1, 7|-1, 11|1,17|-1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|1, 7|-1, 11|-1,17|-1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|1, 7|-1, 11|1,17|1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|-1, 7|1, 11|1,17|1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|1, 7|-1, 11|-1,17|1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|-1, 7|-1, 11|1,17|1, 23|
最小时间:11。蚂蚁初始状态是:-1, 3|-1, 7|-1,11|1, 17|1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|1, 7|1, 11|-1,17|-1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|1, 7|-1, 11|1,17|-1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|1, 7|1, 11|1,17|1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|1, 7|1, 11|1,17|-1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|-1, 7|-1,11|-1, 17|-1, 23|
最大时间:24。蚂蚁初始状态是:1, 3|1, 7|1, 11|-1,17|1, 23|
// 1, 3|1, 7|1, 11|-1, 17|1, 23 可以这么看：第一位是方向，第二位是蚂蚁的初始位置， “|” 各开每一只蚂蚁，假设5只蚂蚁都在X坐标上移动，往正方向移动那么方向为1，相反负方向移动方向为-1
2：参加会议:有人邀请A,B,C,D,E,F6个人参加一项会议，这6个人有些奇怪，因为他们有很多要求，已知：
(1).A,B两人至少有1人参加会议。
(2).A,E,F3人中有2人参加会议。
(3).B和C两人一致决定，要么两人都去，要么两人都不去。
(4).A,D两人中只1人参加会议。
(5).C,D两人中也只要1人参加会议。
(6).如果D不去，那么E也决定不去。
那么最后究竟有哪几个人参加了会议呢？
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
public class TestDemo28 {
/** 全局变量：存放所有组合*/
private static Set<String> set = new HashSet<String>();
/**
* @param args
*/
public static void main(String[] args) {
// 用一个List存放所有参会人员
List<String> preList = new ArrayList<String>();
preList.add("A");
preList.add("B");
preList.add("C");
preList.add("D");
preList.add("E");
preList.add("F");
try {
// 得到所有的组合
for (int i = 1; i <= preList.size(); i++) {
doList(preList, i);
}
// 判断每一种组合是否符合条件
for (Iterator<String> it = set.iterator(); it.hasNext();) {
marc(it.next().toString());
}
} catch (IndexOutOfBoundsException ioe) {
System.out.println("数组越界");
} catch (Exception e) {
e.printStackTrace();
}
}
/**
* <TT><PRE>
* <p>参加会议:有人邀请A,B,C,D,E,F6个人参加一项会议.</p>
* @param sb 参数：A,B,C,D,E,F6个人的某种组合
* @return boolean true:符合条件 false:不符合条件
*</PRE></TT>
*/
protected static boolean marc(String sb) {
// (1).A,B两人至少有1人参加会议。
if (!sb.contains("A") && !sb.contains("B")) {
return false;
}
// (2).A,E,F3人中有2人参加会议。
if (!((sb.contains("A") && sb.contains("E"))
|| (sb.contains("A") && sb.contains("F"))
|| (sb.contains("E") && sb.contains("F")))) {
return false;
}
// (3).B和C两人一致决定，要么两人都去，要么两人都不去。
if ((sb.contains("B") && !sb.contains("C"))
|| (!sb.contains("B") && sb.contains("C"))) {
return false;
}
// (4).A,D两人中只1人参加会议。
if (sb.contains("A") && sb.contains("D")) {
return false;
}
// (5).C,D两人中也只要1人参加会议。
if (sb.contains("C") && sb.contains("D")) {
return false;
}
// (6).如果D不去，那么E也决定不去。
if (!sb.contains("D") && sb.contains("E")) {
return false;
}
// 输出满足条件的组合
System.out.println(sb);
return true;
}
/**
* <TT><PRE>
* <p> 采用回溯法找出制定长度所有可能的组合.</p>
* @param list 所有候选人
* @param len 个数
* @return List 指定人数所有可能的组合
* @throws Exception 例外
* </PRE></TT>
*/
protected static List doList(List list, int len) throws Exception {
List<String> lst = new ArrayList<String>();
StringBuffer sb = null;
int begIdx = 0;
if (len == 1) {
for (Iterator it = list.iterator(); it.hasNext();) {
set.add(it.next().toString());
}
return list;
}
while (begIdx < list.size() - len + 1) {
sb = new StringBuffer();
sb.append(list.get(begIdx));
List typeLst = doList(list.subList(begIdx + 1, list.size()), len - 1);
for (int i = 0; i < typeLst.size(); i++) {
sb.append(typeLst.get(i));
lst.add(sb.toString());
set.add(sb.toString());
sb.delete(1, sb.length());
}
begIdx++;
}
return lst;
}
3：用程序求解：
请回答下面10个问题：
1、第一个答案是b的问题是哪一个？
（a）2；（b） 3；（c）4；（d）5；（e）6
2、唯一的连续两个具有相同答案的问题是：
（a）2，3；（b）3，4；（c）4，5；（d）5，6；（e）6，7；
3、本问题答案和哪一个问题的答案相同？
（a）1；（b）2；（c）4；（d）7；（e）6
4、答案是a的问题的个数是：
（a）0；（b）1；（c）2；（d）3；（e）4
5、本问题答案和哪一个问题的答案相同？
（a）10；（b）9；（c）8；（d）7；（e）6
6、答案是a的问题的个数和答案是什么的问题的个数相同？
（a）b；（b）c；（c）d；（d）e；（e）以上都不是
7、按照字母顺序，本问题的答案和下一个问题的答案相差几个字母？
（a）4；（b）3；（c）2；（d）1；（e）0 （注：a和b相差一个字母）
8、答案是元音字母的问题的个数是：
（a）2；（b）3；（c）4；（d）5；（e）6 （注：a和e是元音字母）
9、答案是辅音字母的问题的个数是：
（a）一个质数；（b）一个阶乘数；（c）一个平方数；（d）一个立方数，（e）5的倍数
10、本问题的答案是：
（a）a；（b）b；（c）c；（d）d；（e）e
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
/**
* @author bree06
*
*/
public class Demo9 {
public static final char DEFAULTCHAR = 'a';
public static final String DEFAULTSTR_A = "a";
public static final String DEFAULTSTR_B = "b";
public static final String DEFAULTSTR_E = "e";
public static List<String[]> list = null;
private static String allAnswer = null;
/**
* @param args
*/
public static void main(String[] args) {
long start = System.currentTimeMillis();
init();
StringBuilder answer = new StringBuilder();
answer.append("aaaaaaaaaa");
File file = new File("e:/allanswer.txt");
FileWriter writer = null;
try {
if (!file.exists()) {
file.createNewFile();
}
writer = new FileWriter(file);
for (char i = 'a'; i <= 'e'; i++) {
answer.deleteCharAt(0);
answer.insert(0, i);
for (char j = 'a'; j <= 'e'; j++) {
answer.deleteCharAt(1);
answer.insert(1, j);
for (char m = 'a'; m <= 'e'; m++) {
answer.deleteCharAt(2);
answer.insert(2, m);
for (char n = 'a'; n <= 'e'; n++) {
answer.deleteCharAt(3);
answer.insert(3, n);
for (char a = 'a'; a <= 'e'; a++) {
answer.deleteCharAt(4);
answer.insert(4, a);
for (char b = 'a'; b <= 'e'; b++) {
answer.deleteCharAt(5);
answer.insert(5, b);
for (char c = 'a'; c <= 'e'; c++) {
answer.deleteCharAt(6);
answer.insert(6, c);
for (char d = 'a'; d <= 'e'; d++) {
answer.deleteCharAt(7);
answer.insert(7, d);
for (char e = 'a'; e <= 'e'; e++) {
answer.deleteCharAt(8);
answer.insert(8, e);
for (char f = 'a'; f <= 'e'; f++) {
answer.deleteCharAt(9);
answer.insert(9, f);
allAnswer = answer.toString();
if (matcher()) writer.write(allAnswer + "\n");
}
}
}
}
}
}
}
}
}
}
writer.write("total time: (ms)" + (System.currentTimeMillis() - start));
} catch (IOException e) {
try {
writer.write(e.getMessage());
} catch (IOException e1) {}
e.printStackTrace();
} finally {
try {
if (writer != null)
writer.close();
} catch (IOException e) {}
}
}
/**
* 初始化所有问题的答案
*/
private static void init() {
list = new ArrayList<String[]>();
list.add(new String[]{"2", "3", "4", "5", "6"});
list.add(new String[]{"2,3", "3,4", "4,5", "5,6", "6,7"});
list.add(new String[]{"1", "2", "4", "7", "6"});
list.add(new String[]{"0", "1", "2", "3", "4"});
list.add(new String[]{"10", "9", "8", "7", "6"});
list.add(new String[]{"b", "c", "d", "e", "a"});
list.add(new String[]{"4", "3", "2", "1", "0"});
list.add(new String[]{"2", "3", "4", "5", "6"});
list.add(new String[]{"a", "b", "c", "d", "e"});
list.add(new String[]{"a", "b", "c", "d", "e"});
}
private static boolean matcher() {
return (No1() && No2() && No3() && No4() && No5() && No6() && No7() && No8() && No9());
}
/**
* 1、第一个答案是b的问题是哪一个？
* @return
*/
private static boolean No1() {
return ((allAnswer.indexOf(DEFAULTSTR_B) + 1) == Integer.parseInt(list.get(0)[getThisAns(1)]));
}
/**
* 2、唯一的连续两个具有相同答案的问题是：
* @return
*/
private static boolean No2() {
int cnt = 0, idx = 0;
while (idx < allAnswer.length() - 1) {
if (allAnswer.charAt(idx) == allAnswer.charAt(++idx)) {
cnt++;
}
}
if (cnt != 1) return Boolean.FALSE;
String ans = list.get(1)[getThisAns(2)];
return (allAnswer.charAt(Integer.parseInt(ans.split(",")[0])-1) == allAnswer.charAt(Integer.parseInt(ans.split(",")[1])-1));
}
/**
* 3、本问题答案和哪一个问题的答案相同？
* @return
*/
private static boolean No3() {
return ((allAnswer.charAt(Integer.parseInt(list.get(2)[getThisAns(3)]) - 1) - DEFAULTCHAR) == getThisAns(3));
}
/**
* 4、答案是a的问题的个数是：
* @return
*/
private static boolean No4() {
return (Integer.parseInt(list.get(3)[getThisAns(4)]) == contChar(allAnswer, DEFAULTSTR_A));
}
/**
* 5、本问题答案和哪一个问题的答案相同？
* @return
*/
private static boolean No5() {
return ((allAnswer.charAt(Integer.parseInt(list.get(4)[getThisAns(5)]) - 1) - DEFAULTCHAR) == getThisAns(5));
}
/**
* 6、答案是a的问题的个数和答案是什么的问题的个数相同？
* @param thisAns
* @param allAnswer
* @return
*/
private static boolean No6() {
return (contChar(allAnswer, DEFAULTSTR_A) == contChar(allAnswer, list.get(5)[getThisAns(6)]));
}
/**
* 7、按照字母顺序，本问题的答案和下一个问题的答案相差几个字母？
* @return
*/
private static boolean No7() {
return (Math.abs(allAnswer.charAt(6)-allAnswer.charAt(7)) == Integer.parseInt(list.get(6)[getThisAns(7)]));
}
/**
* 8、答案是元音字母的问题的个数是：
* @return
*/
private static boolean No8() {
int cntae = contChar(allAnswer, DEFAULTSTR_A) + contChar(allAnswer, DEFAULTSTR_E);
return (Integer.parseInt(list.get(7)[getThisAns(8)]) == cntae);
}
/**
* 9、答案是辅音字母的问题的个数是：
* （a）一个质数；（b）一个阶乘数；（c）一个平方数；（d）一个立方数，（e）5的倍数;
* @return
*/
private static boolean No9() {
int cntbcd = allAnswer.length() - contChar(allAnswer, DEFAULTSTR_A) - contChar(allAnswer, DEFAULTSTR_E);
switch (getThisAns(9)) {
case 0:
return (String.valueOf(cntbcd).matches("[2357]"));
case 1:
return (String.valueOf(cntbcd).matches("[026]"));
case 2:
return (String.valueOf(cntbcd).matches("[149]"));
case 3:
return (String.valueOf(cntbcd).matches("[18]"));
case 4:
return (cntbcd % 5 == 0);
default:
return Boolean.FALSE;
}
}
/**
* 计算字符串中有多少个指定字符
* @param str
* @param chr
* @return
*/
public static int contChar(String str, String chr) {
if (str == null || "".equals(str)) return 0;
return (str.length() - str.replace(chr, "").length());
}
/**
* 取得本题答案
* @param index 题号
* @return
*/
public static int getThisAns(int index) {
index = index > allAnswer.length() ? allAnswer.length() - 1 : index - 1;
return allAnswer.charAt(index) - DEFAULTCHAR;
}
}
//
满足条件的组合有
:
abddaedcba
cdebeeaece
cdebeedcba
