《爱因斯坦的问题》解答 Myeclipse算法J#
程序员文章站
2022-06-04 16:04:18
...
看到这样一个问题，题目就叫《爱因斯坦的问题》，光看题目就很有意思，打开后看了问题内容，第一反应是“晕”，而后在纸上画了画，大体理清了思路，不过实在是懒得算，就准备写个程序来帮忙。
首先把问题的内容贴出来：
爱因斯坦的超级问题
1、在一条街上，有5座房子，喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物
问题是：谁养鱼？
提示：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽PallMall香烟的人养鸟
7、黄色房子主人抽Dunhill香烟
8、住在中间房子的人喝牛奶
9、挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill香烟的人隔壁
12、抽BlueMaster的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居
1、在一条街上，有5座房子，喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物
问题是：谁养鱼？
提示：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽PallMall香烟的人养鸟
7、黄色房子主人抽Dunhill香烟
8、住在中间房子的人喝牛奶
9、挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill香烟的人隔壁
12、抽BlueMaster的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居
通过程序解这种题，第一个反应是穷举法。现在先算算穷举法有多少种组合。一条街，包含5间有序的房屋，每间房屋有五个互不相同的属性：国籍、颜色、宠物、饮料和香烟。因为5间房屋相同类型的属性都不一样，所以每个属性都有5!=120种组合，5种属性加起来，共有120^5=24883200000种！接近250亿了。
直接穷举这么多种情况，显得很不合适，所以在使用穷举法的时候，不要等把一种组合确定下来之后再去判断是否符合条件，而是在组合中的一部分属性确定下来后马上做判断，这样会快很多。
本来想把房屋和街道抽象成java类，但是感觉有点兴师动众，所以就只写了一个类，以解决问题为主。下面直接上代码。
import java.util.ArrayList;
public class Einstein {
private static final String[] MEN = { "挪威", "瑞典", "英国", "丹麦", "德国" };
private static final int NORWAY = 0;
private static final int SWEDEN = 1;
private static final int ENGLAND = 2;
private static final int DENMARK = 3;
private static final int GERMANY = 4;
// ================================================================
private static final String[] PET = { "狗", "鸟", "马", "猫", "鱼" };
private static final int DOG = 0;
private static final int BIRD = 1;
private static final int HORSE = 2;
private static final int CAT = 3;
private static final int FISH = 4;
// ================================================================
private static final String[] COL = { "蓝色", "红色", "黄色", "白色", "绿色" };
private static final int BLUE = 0;
private static final int RED = 1;
private static final int YELLOW = 2;
private static final int WHITE = 3;
private static final int GREEN = 4;
// ================================================================
private static final String[] WIN = { "牛奶", "咖啡", "啤酒", "水", "茶" };
private static final int MILK = 0;
private static final int COFFE = 1;
private static final int BEER = 2;
private static final int WHAT = 3;
private static final int TEE = 4;
// ================================================================
private static final String[] SMO = { "PallMall", "Dunhill", "BlueMaster",
"Prince", "Blends" };
private static final int PM = 0;
private static final int DH = 1;
private static final int BM = 2;
private static final int P = 3;
private static final int B = 4;
// ================================================================
private static final ArrayList<int[]> list = new ArrayList<int[]>(120);
public static void main(String[] args) {
// 先生成0-4的全排列。算法很笨，但是很有效。
for (int i1 = 0; i1 < 5; i1++) {
for (int i2 = 0; i2 < 5; i2++) {
if (i2 == i1) {
continue;
}
for (int i3 = 0; i3 < 5; i3++) {
if (i3 == i1 || i2 == i1 || i2 == i3) {
continue;
}
for (int i4 = 0; i4 < 5; i4++) {
if (i3 == i1 || i2 == i1 || i4 == i1 || i3 == i4
|| i3 == i2 || i2 == i4) {
continue;
}
int[] arr = new int[] { i1, i2, i3, i4,
(10 - i1 - i2 - i3 - i4) };
list.add(arr);
}
}
}
}
getM();
}
/**
* 国籍的全排列
*/
private static final void getM() {
long begin = System.nanoTime();
// 开始
for (int[] men : list) {
if (men[0] != NORWAY) {
// 9、挪威人住第一间房
continue;
}
getC(men);
}
System.out.println("耗时：" + (System.nanoTime() - begin) + "纳秒。");
}
/**
* 颜色的全排列
*/
private static void getC(int[] men) {
out: for (int[] color : list) {
if (color[1] != BLUE || color[4] == GREEN) {
// 14、挪威人住蓝色房子隔壁
// 所以，左起第二间房屋一定是蓝色色的
// 4、绿色房子在白色房子左面
// 所以，最右边的房屋一定不是绿色的
continue;
}
for (int i = 0; i < 4; i++) {
if (color[i] == GREEN && color[i + 1] != WHITE) {
// 4、绿色房子在白色房子左面
continue out;
}
}
for (int i = 0; i < 5; i++) {
if (men[i] == ENGLAND && color[i] != RED) {
// 1、英国人住红色房子
continue out;
}
}
getP(men, color);
}
}
/**
* 宠物的全排列
*/
private static void getP(int[] men, int[] color) {
out: for (int[] pet : list) {
for (int i = 0; i < 5; i++) {
if (men[i] == SWEDEN && pet[i] != DOG) {
// 2、瑞典人养狗
continue out;
}
}
getW(men, color, pet);
}
}
/**
* 饮料的全排列
*/
private static void getW(int[] men, int[] color, int[] pet) {
out: for (int[] win : list) {
if (win[2] != MILK) {
// 8、住在中间房子的人喝牛奶
continue;
}
for (int i = 0; i < 5; i++) {
if (men[i] == DENMARK && win[i] != TEE) {
// /3、丹麦人喝茶
continue out;
}
}
for (int i = 0; i < 5; i++) {
if (color[i] == GREEN && win[i] != COFFE) {
// 5、绿色房子主人喝咖啡
continue out;
}
}
getS(men, color, pet, win);
}
}
/**
* 香烟的全排列
*/
private static void getS(int[] men, int[] color, int[] pet, int[] win) {
out: for (int[] smo : list) {
for (int i = 0; i < 5; i++) {
if (pet[i] == BIRD && smo[i] != PM) {
// 6、抽PallMall香烟的人养鸟
continue out;
}
}
for (int i = 0; i < 5; i++) {
if (color[i] == YELLOW && smo[i] != DH) {
// 7、黄色房子主人抽Dunhill香烟
continue out;
}
}
for (int i = 0; i < 5; i++) {
if (win[i] == BEER && smo[i] != BM) {
// /12、抽BlueMaster的人喝啤酒
continue out;
}
}
for (int i = 0; i < 5; i++) {
int man = men[i];
if (man == GERMANY && smo[i] != P) {
// 13、德国人抽Prince香烟
continue out;
}
}
boolean b = true;
for (int i = 0; i < 4; i++) {
if ((smo[i] == B && pet[i + 1] == CAT)
|| (smo[i + 1] == B && pet[i] == CAT)) {
// 10、抽Blends香烟的人住在养猫的人隔壁
b = false;
break;
}
}
if (b) {
continue;
}
b = true;
for (int i = 0; i < 4; i++) {
if ((smo[i] == B && win[i + 1] == WHAT)
|| (smo[i + 1] == B && win[i] == WHAT)) {
// 15、抽Blends香烟的人有一个喝水的邻居
b = false;
break;
}
}
if (b) {
continue;
}
b = true;
for (int i = 0; i < 4; i++) {
if ((smo[i] == DH && pet[i + 1] == HORSE)
|| (smo[i + 1] == DH && pet[i] == HORSE)) {
// 11、养马的人住抽Dunhill香烟的人隔壁
b = false;
break;
}
}
if (b) {
continue;
}
int[][] old = new int[][] { men, color, pet, win, smo };
print(old);
}
}
/**
* 打印结果
*/
private static final void print(int[][] old) {
int[][] arr = new int[5][5];
// 转置
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
arr[j][i] = old[i][j];
}
}
StringBuilder sb = new StringBuilder("房屋位置\t国籍\t房子颜色\t宠物\t饮料\t香烟");
for (int i = 0; i < arr.length; i++) {
sb.append("\n左起").append(i + 1);
sb.append("\t").append(MEN[arr[i][0]]);
sb.append("\t").append(COL[arr[i][1]]);
sb.append("\t").append(PET[arr[i][2]]);
sb.append("\t").append(WIN[arr[i][3]]);
sb.append("\t").append(SMO[arr[i][4]]);
}
sb.append("\n============================");
System.out.println(sb);
}
}
在MyEclipse中的运行结果：
