如何用算法来解决爱因斯坦在20世纪初出的这个谜语(页 1) - 算法讨论与研究 - ITPUB论坛

2007-3-14 11:21 soachina

如何用算法来解决爱因斯坦在20世纪初出的这个谜语

爱因斯坦在20世纪初出的这个谜语。他说世界上有98％的人答不出来。某家公司在面试应聘者时借用了爱因斯坦的这个IQ题，考查应聘者的IQ，现在我们暂且不去讨论这个公司用这样的题目来考查应聘者的IQ有多“变态”，如果是你，拿到了这样的笔试题目，你能做得出来吗？

　　1、在一条街上，有5座房子，喷了5种颜色。

　　2、每个房里住着不同国籍的人

　　3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物

　　问题是：谁养鱼？

　　提示：

　　1、英国人住红色房子

　　2、瑞典人养狗

　　3、丹麦人喝茶

　　4、绿色房子在白色房子左面

　　5、绿色房子主人喝咖啡

　　6、抽Pall Mall 香烟的人养鸟

　　7、黄色房子主人抽Dunhill 香烟

　　8、住在中间房子的人喝牛奶

　　9、挪威人住第一间房

　　10、抽Blends香烟的人住在养猫的人隔壁

　　11、养马的人住抽Dunhill 香烟的人隔壁

　　12、抽Blue Master的人喝啤酒

　　13、德国人抽Prince香烟

　　14、挪威人住蓝色房子隔壁

　　15、抽Blends香烟的人有一个喝水的邻居

　　以上是爱因斯坦在20世纪初出的这个谜语。他说世界上有98％的人答不出来。

2007-3-25 22:53 tang2007

有些复杂啊

2007-3-25 22:54 tang2007

不过应该还是有办法解决的

2007-4-6 13:58 dy_david

德国

2007-4-7 23:57 tang2007

不会只有答案吧:)过程呢？

2007-4-10 22:57 lawer-bbc

关注下

2007-4-24 23:30 sting_gxj

有意思啊

2007-4-25 10:03 fixphy1985

找到关键点就很简单了，我初中就做过这道题了

2007-4-25 13:10 lawer-bbc

[QUOTE][i]最初由 fixphy1985 发布[/i]
[B]找到关键点就很简单了，我初中就做过这道题了 [/B][/QUOTE]

讲讲:rose:

2007-5-21 20:23 chinjecn

最近在学矩阵分析，用这来分析一下：
　　　　　 1| 　　　　2| 　　　3| 　　　　4| 　　　　5
颜色　　　黄| 　　　篮| 　　　红| 　　　绿| 　　　　白
国际　　挪威| 　　丹麦| 　　英国| 　　德国| 　　　瑞典
饮料　　　水| 　　　茶| 　　牛奶| 　　咖啡| 　　　啤酒
香烟　 Dunhill| Blends| P all Mall| 　Prince| Blue Master
宠物　　　猫| 　　　马| 　　　鸟| 　　　鱼| 　　　　狗

2007-5-22 13:37 davis_zhou

经典

2007-5-29 16:46 catchwo

如果能写出这个算法来，那就是真正的人工智能了！！！！！！！！！！！！

2007-5-29 23:44 tang2007

解决了没有啊？:)

2007-5-29 23:44 tang2007

[QUOTE][i]最初由 catchwo 发布[/i]
[B]如果能写出这个算法来，那就是真正的人工智能了！！！！！！！！！！！！ [/B][/QUOTE]

:right: 94:)

2007-6-17 20:53 sibling

[QUOTE][i]最初由 lawer-bbc 发布[/i]
[B]

讲讲:rose: [/B][/QUOTE]

把5个属性每个的五种可能列出来（便于察看），再开始从左到右12345列成5*5的方阵，根据规则来填，把条件多梳理几遍，一步一步前进即可

2007-6-17 22:32 122408644

我以前思考过这个问题。但是没有考虑算法问题。

2007-6-21 13:37 dinner1007

用矩阵，这个答案早就出啦

2008-3-28 17:00 zn519

同事无聊，信手拈来，几分钟思考后，写了段代码并输出了结果。以下是部分代码内容，俺没看懂的说

据说这一段是核心算法：

public class Einstein{

public static void main(String[] args) {
List<Object> hl = new LinkedList<Object>();
for (int i = 0; i < 5; i++) {
hl.add(i);
}
List<List<Object>> random = DFC(hl);
List<List<House>> houseList = new LinkedList<List<House>>();
List<List<Country>> countryList = new LinkedList<List<Country>>();
List<List<Pet>> petList = new LinkedList<List<Pet>>();
List<List<Drink>> drinkList = new LinkedList<List<Drink>>();
List<List<Smoke>> smokeList = new LinkedList<List<Smoke>>();
for (List<Object> o : random) {
List<House> hList = new LinkedList<House>();
List<Country> cList = new LinkedList<Country>();
List<Pet> pList = new LinkedList<Pet>();
List<Drink> dList = new LinkedList<Drink>();
List<Smoke> sList = new LinkedList<Smoke>();
for (Object oo : o) {
int i = (Integer) oo;
hList.add(House.values()[i]);
cList.add(Country.values()[i]);
pList.add(Pet.values()[i]);
dList.add(Drink.values()[i]);
sList.add(Smoke.values()[i]);
}
houseList.add(hList);
countryList.add(cList);
petList.add(pList);
drinkList.add(dList);
smokeList.add(sList);
}
// 第一趟，循环国家
for (List<Country> c : countryList) {
// 9、挪威人住第一间房
if (c.get(0) != Country.norway)
continue;
// 第二趟，循环房子
for (List<House> h : houseList) {
// 1、英国人住红房子
if (c.indexOf(Country.english) != h.indexOf(House.red))
continue;
// 4、绿房子在白房子左边
if (h.indexOf(House.white) - h.indexOf(House.green) != 1)
continue;
// 14、挪威人住蓝色房子隔壁
int p14 = c.indexOf(Country.norway) - h.indexOf(House.blue);
if (p14 != 1 && p14 != -1)
continue;
// 第三趟，循环饮料
for (List<Drink> d : drinkList) {
// 3、丹麦人喝茶
if (d.indexOf(Drink.tea) != c.indexOf(Country.danmark))
continue;
// 5、绿色房子喝咖啡
if (d.indexOf(Drink.coffee) != h.indexOf(House.green))
continue;
// 8、中间房子喝牛奶
if (d.indexOf(Drink.milk) != 2)
continue;
// 第四趟，循环烟
for (List<Smoke> s : smokeList) {
// 7、黄色房子主人抽Dunhill 香烟
if (h.indexOf(House.yellow) != s.indexOf(Smoke.D))
continue;
// 12、抽Blue Master的人喝啤酒
if (d.indexOf(Drink.beer) != s.indexOf(Smoke.BM))
continue;
// 13、德国人抽Prince香烟
if (c.indexOf(Country.germen) != s.indexOf(Smoke.P))
continue;
// 15、抽Blends香烟的人有一个喝水的邻居
int p15 = d.indexOf(Drink.water) - s.indexOf(Smoke.B);
if (p15 != 1 && p15 != -1)
continue;
// 第五趟，循环宠物
for (List<Pet> p : petList) {
// 2、瑞典人养狗
if (p.indexOf(Pet.dog) != c.indexOf(Country.sweeden))
continue;
// 6、抽Pall Mall 香烟的人养鸟
if (p.indexOf(Pet.bird) != s.indexOf(Smoke.PM))
continue;
// 10、抽Blends香烟的人住在养猫的人隔壁
int p10 = p.indexOf(Pet.cat) - s.indexOf(Smoke.B);
if (p10 != 1 && p10 != -1)
continue;
// 11、养马的人住抽Dunhill 香烟的人隔壁
int p11 = p.indexOf(Pet.horse) - s.indexOf(Smoke.D);
if (p11 != 1 && p11 != -1)
continue;
System.out.println("答案：");
System.out.println("房间顺序："+h);
System.out.println("国家顺序："+c);
System.out.println("饮料顺序："+d);
System.out.println("香烟顺序："+s);
System.out.println("宠物顺序："+p);
}
}
}
}
}

}

public static List<List<Object>> DFC(List<Object> values) {
List<List<Object>> result = new LinkedList<List<Object>>();
if (values.size() == 1) {
List<Object> r = new LinkedList<Object>();
r.add(values.get(0));
result.add(r);
} else {
for (int i = 0; i < values.size(); i++) {
List<Object> t = new LinkedList<Object>(values);
t.remove(i);
List<List<Object>> tr = DFC(t);
for (List<Object> temp : tr) {
List<Object> r = new LinkedList<Object>();
r.add(values.get(i));
r.addAll(temp);
result.add(r);
}
}
}
return result;
}

}

答案：
房间顺序：[yellow, blue, red, green, white]
国家顺序：[norway, danmark, english, germen, sweeden]
饮料顺序：[water, tea, milk, coffee, beer]
香烟顺序：[D, B, PM, P, BM]
宠物顺序：[cat, horse, bird, fish, dog]

代码不全，但核心算法已经有了，凑合着看吧

[[i] 本帖最后由 zn519 于 2008-3-28 17:07 编辑 [/i]]

2008-3-28 17:10 zn519

另外分别定义了5种事物

Country.java

public enum Country {
english,sweeden,danmark,germen,norway
}

Drink.java

public enum Drink {
tea,coffee,beer,milk,water
}

House.java

public enum House {

red,blue,green,white,yellow
}

Pet.java

public enum Pet {
bird,fish,cat,dog,horse
}

Smoke.java

public enum Smoke {
B,BM,P,D,PM
}

2008-3-28 17:11 zn519

还有一同事，按照咨询师的思维逻辑，手工弄出来了，佩服。
见附件。