锁定老帖子 主题:一道应聘智力题的编程求解
精华帖 (0) :: 良好帖 (9) :: 新手帖 (0) :: 隐藏帖 (0)
|
|||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
作者 | 正文 | ||||||||||||||||||||||||||||||||||||
发表时间:2010-03-04
最后修改:2010-03-04
请编程解决如下难题:
遇到这样的题目,一般思路是遍历所有可能,再根据给出的条件约束一一排除,最后得到正确结果。但是如果仔细算一下就会发现直接遍历的方法不可取,因为根据排列组合的公式算一下如果不排除任何约束条件大约有40亿(40^6=40亿,高中学的公式,不一定记的准确)种可能,显然直接遍历的话肯定会溢出(没测试过),所以正确的方法是首先排除掉一些可能,使遍历的长度尽可能的小。
仔细观察题目给出的条件,我个人认为可以分为两类:
第一类: 1、英国人住在红房子里 6、抽PALL MALL烟的人养了一只鸟 7、黄房子主人抽DUNHILL烟 8、住在中间那间房子的人喝牛奶 9、挪威人住第一间房子 13、德国人抽PRINCE烟
第二类: 4、绿房子在白房子左边 10、抽混合烟的人住在养猫人的旁边 14、挪威人住在蓝房子旁边
如果我们画一张二维图表的话,第一类的约束条件可以直接反映出来,而第二类无法直接反映,需要间接推理。
这里具体的推理就不列出来了,相信大部分的朋友应该都能看的明白。这样一来,图表里的每一列的可能性分别降低到了25、21、33、14、33种,但是如果不去除重复的项,经过排列组合后所有的可能性仍旧高达超过800万种,所以在具体编程计算中,还要去掉重复的项。去掉重复的项后可能性聚降到只有1000多种,这个时候我们就可以用程序来遍历了。
import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Map.Entry; public class Caculate { //英国0 瑞典1 丹麦2 挪威3 德国4 //红色0 绿色1 白色2 蓝色3 黄色4 //鸟0 狗1 猫2 鱼3 马4 //咖啡0 牛奶1 啤酒2 茶3 水4 //Price0 Pall Mall1 Blue2 Dunhill3 混合型4 public static List makeList(){ List list = new ArrayList(); for (int i=0; i<5; i++ ){ for (int j=0; j<5; j++){ for (int k=0; k<5; k++){ for (int p=0; p<5; p++){ for (int q=0; q<5; q++){ for (int r=0; r<5; r++){ int[] lt = new int[6]; lt[0]=i; //国籍 lt[1]=j; //颜色 lt[2]=k; //宠物 lt[3]=p; //饮料 lt[4]=q; //香烟 lt[5]=r; //位置 list.add(lt); } } } } } } return list; } public static List caculateUK(){ //英国 List UK = makeList(); Iterator iterator = UK.iterator(); while (iterator.hasNext()){ int[] item = (int[])iterator.next(); //英国人 if (item[0]!=0){ iterator.remove(); continue; } //住红房子 if (item[1]!=0){ iterator.remove(); continue; } //不养狗 if (item[2] == 1){ iterator.remove(); continue; } //不和咖啡和茶 if (item[3] == 0 || item[3] == 3){ iterator.remove(); continue; } //不抽Price烟 if (item[4] == 0){ iterator.remove(); continue; } //不住第一间 if (item[5] == 0){ iterator.remove(); continue; } //抽PALL MALL烟的人养了一只鸟 if (item[2] == 0 && item[4]!=1){ iterator.remove(); continue; } if (item[4] == 1 && item[2]!=0){ iterator.remove(); continue; } //抽BLUE MASTER烟的人喝啤酒 if (item[4] == 2 && item[3]!= 2){ iterator.remove(); continue; } if (item[3] == 2 && item[4]!= 2){ iterator.remove(); continue; } //绿房子主人喝咖啡 if (item[3] == 0 && item[1]!= 1){ iterator.remove(); continue; } if (item[1] == 1 && item[3]!= 0){ iterator.remove(); continue; } //黄房子主人抽DUNHILL烟 if (item[4] == 3 && item[1]!= 4){ iterator.remove(); continue; } if (item[1] == 4 && item[4]!= 3){ iterator.remove(); continue; } //住在中间那间房子的人喝牛奶 if (item[3] == 1 && item[5]!=2){ iterator.remove(); continue; } if (item[5] == 2 && item[3]!=1){ iterator.remove(); continue; } } System.out.println(UK.size()); return UK; } public static List caculateSD(){ //瑞典 List SD = makeList(); Iterator iterator = SD.iterator(); iterator = SD.iterator(); while (iterator.hasNext()){ int[] item = (int[])iterator.next(); //瑞典人 if (item[0]!=1){ iterator.remove(); continue; } //养狗 if (item[2]!= 1){ iterator.remove(); continue; } //不喝茶 if (item[3] == 3){ iterator.remove(); continue; } //不住红房子 if (item[1] == 0){ iterator.remove(); continue; } //不抽Price烟和Pall Mall烟 if (item[4] == 0 || item[4] == 1){ iterator.remove(); continue; } //不住第一间 if (item[5] == 0){ iterator.remove(); continue; } //抽PALL MALL烟的人养了一只鸟 if (item[2] == 0 && item[4]!=1){ iterator.remove(); continue; } if (item[4] == 1 && item[2]!=0){ iterator.remove(); continue; } //抽BLUE MASTER烟的人喝啤酒 if (item[4] == 2 && item[3]!= 2){ iterator.remove(); continue; } if (item[3] == 2 && item[4]!= 2){ iterator.remove(); continue; } //绿房子主人喝咖啡 if (item[3] == 0 && item[1]!= 1){ iterator.remove(); continue; } if (item[1] == 1 && item[3]!= 0){ iterator.remove(); continue; } //黄房子主人抽DUNHILL烟 if (item[4] == 3 && item[1]!= 4){ iterator.remove(); continue; } if (item[1] == 4 && item[4]!= 3){ iterator.remove(); continue; } //住在中间那间房子的人喝牛奶 if (item[3] == 1 && item[5]!=2){ iterator.remove(); continue; } if (item[5] == 2 && item[3]!=1){ iterator.remove(); continue; } } System.out.println(SD.size()); return SD; } public static List caculateDM(){ //丹麦 List DM = makeList(); Iterator iterator = DM.iterator(); iterator = DM.iterator(); while (iterator.hasNext()){ int[] item = (int[])iterator.next(); //丹麦人 if (item[0]!=2){ iterator.remove(); continue; } //喝茶 if (item[3]!= 3){ iterator.remove(); continue; } //不养狗 if (item[2] == 1){ iterator.remove(); continue; } //不住红房子和绿房子 if (item[1] == 0 || item[1] == 1){ iterator.remove(); continue; } //不抽Price烟 if (item[4] == 0){ iterator.remove(); continue; } //不住第一间和中间 if (item[5] == 0 || item[5] == 2){ iterator.remove(); continue; } //抽PALL MALL烟的人养了一只鸟 if (item[2] == 0 && item[4]!=1){ iterator.remove(); continue; } if (item[4] == 1 && item[2]!=0){ iterator.remove(); continue; } //抽BLUE MASTER烟的人喝啤酒 if (item[4] == 2 && item[3]!= 2){ iterator.remove(); continue; } if (item[3] == 2 && item[4]!= 2){ iterator.remove(); continue; } //绿房子主人喝咖啡 if (item[3] == 0 && item[1]!= 1){ iterator.remove(); continue; } if (item[1] == 1 && item[3]!= 0){ iterator.remove(); continue; } //黄房子主人抽DUNHILL烟 if (item[4] == 3 && item[1]!= 4){ iterator.remove(); continue; } if (item[1] == 4 && item[4]!= 3){ iterator.remove(); continue; } //住在中间那间房子的人喝牛奶 if (item[3] == 1 && item[5]!=2){ iterator.remove(); continue; } if (item[5] == 2 && item[3]!=1){ iterator.remove(); continue; } } System.out.println(DM.size()); return DM; } public static List caculateNW(){ //挪威 List NW = makeList(); Iterator iterator = NW.iterator(); iterator = NW.iterator(); while (iterator.hasNext()){ int[] item = (int[])iterator.next(); //挪威人 if (item[0]!=3){ iterator.remove(); continue; } //不喝茶和牛奶 if (item[3] == 3 ||item[3] == 1){ iterator.remove(); continue; } //不养狗 if (item[2] == 1){ iterator.remove(); continue; } //不住红房子和白房子 if (item[1] == 0 || item[1] == 2){ iterator.remove(); continue; } //不抽Price烟 if (item[4] == 0){ iterator.remove(); continue; } //住在第一间 if (item[5] != 0 ){ iterator.remove(); continue; } //抽PALL MALL烟的人养了一只鸟 if (item[2] == 0 && item[4]!=1){ iterator.remove(); continue; } if (item[4] == 1 && item[2]!=0){ iterator.remove(); continue; } //抽BLUE MASTER烟的人喝啤酒 if (item[4] == 2 && item[3]!= 2){ iterator.remove(); continue; } if (item[3] == 2 && item[4]!= 2){ iterator.remove(); continue; } //绿房子主人喝咖啡 if (item[3] == 0 && item[1]!= 1){ iterator.remove(); continue; } if (item[1] == 1 && item[3]!= 0){ iterator.remove(); continue; } //黄房子主人抽DUNHILL烟 if (item[4] == 3 && item[1]!= 4){ iterator.remove(); continue; } if (item[1] == 4 && item[4]!= 3){ iterator.remove(); continue; } //住在中间那间房子的人喝牛奶 if (item[3] == 1 && item[5]!=2){ iterator.remove(); continue; } if (item[5] == 2 && item[3]!=1){ iterator.remove(); continue; } } System.out.println(NW.size()); return NW; } public static List caculateGM(){ //德国 List GM = makeList(); Iterator iterator = GM.iterator(); iterator = GM.iterator(); while (iterator.hasNext()){ int[] item = (int[])iterator.next(); //德国人 if (item[0]!=4){ iterator.remove(); continue; } //不喝茶不喝酒 if (item[3] == 3 || item[3] == 2){ iterator.remove(); continue; } //不养狗不养鸟 if (item[2] == 1 || item[2] == 0){ iterator.remove(); continue; } //不住红房子 if (item[1] == 0 ){ iterator.remove(); continue; } //抽Price烟 if (item[4] != 0){ iterator.remove(); continue; } //不住第一间 if (item[5] == 0 ){ iterator.remove(); continue; } //抽PALL MALL烟的人养了一只鸟 if (item[2] == 0 && item[4]!=1){ iterator.remove(); continue; } if (item[4] == 1 && item[2]!=0){ iterator.remove(); continue; } //抽BLUE MASTER烟的人喝啤酒 if (item[4] == 2 && item[3]!= 2){ iterator.remove(); continue; } if (item[3] == 2 && item[4]!= 2){ iterator.remove(); continue; } //绿房子主人喝咖啡 if (item[3] == 0 && item[1]!= 1){ iterator.remove(); continue; } if (item[1] == 1 && item[3]!= 0){ iterator.remove(); continue; } //黄房子主人抽DUNHILL烟 if (item[4] == 3 && item[1]!= 4){ iterator.remove(); continue; } if (item[1] == 4 && item[4]!= 3){ iterator.remove(); continue; } //住在中间那间房子的人喝牛奶 if (item[3] == 1 && item[5]!=2){ iterator.remove(); continue; } if (item[5] == 2 && item[3]!=1){ iterator.remove(); continue; } } System.out.println(GM.size()); return GM; } public static void main(String[] arg){ List UK = caculateUK(); List SD = caculateSD(); List DM = caculateDM(); List NW = caculateNW(); List GM = caculateGM(); List resultList = new ArrayList(); Iterator uki = UK.iterator(); UK: while (uki.hasNext()){ int[] uk = (int[]) uki.next(); Iterator sdi = SD.iterator(); SD: while (sdi.hasNext()){ int[] sd = (int[]) sdi.next(); //去除重复 for (int i = 1; i<6; i++){ if (uk[i] == sd[i]){ continue SD; } } Iterator dmi = DM.iterator(); DM: while (dmi.hasNext()){ int[] dm = (int[]) dmi.next(); //去除重复 for (int i = 1; i<6; i++){ if (sd[i] == dm[i]){ continue DM; } } for (int i = 1; i<6; i++){ if (uk[i] == dm[i]){ continue DM; } } Iterator nwi = NW.iterator(); NW: while (nwi.hasNext()){ int[] nw = (int[]) nwi.next(); //去除重复 for (int i = 1; i<6; i++){ if (dm[i] == nw[i]){ continue NW; } } for (int i = 1; i<6; i++){ if (sd[i] == nw[i]){ continue NW; } } for (int i = 1; i<6; i++){ if (uk[i] == nw[i]){ continue NW; } } Iterator gmi = GM.iterator(); GM: while (gmi.hasNext()){ int[] gm = (int[]) gmi.next(); //去除重复 for (int i = 1; i<6; i++){ if (nw[i] == gm[i]){ continue GM; } } for (int i = 1; i<6; i++){ if (sd[i] == gm[i]){ continue GM; } } for (int i = 1; i<6; i++){ if (dm[i] == gm[i]){ continue GM; } } for (int i = 1; i<6; i++){ if (uk[i] == gm[i]){ continue GM; } } //绿房子在白房子左边 int[] green = new int[6]; if (sd[1] == 1){ green = sd; }else if (dm[1] == 1){ green = dm; }else if (nw[1] == 1){ green = nw; }else if (gm[1] == 1){ green = gm; } int[] white = new int[6]; if (sd[1] == 2){ white = sd; }else if (dm[1] == 2){ white = dm; }else if (nw[1] == 2){ white = nw; }else if (gm[1] == 2){ white = gm; } if ((green[5] - white[5]!=-1 )){ continue GM; } //抽混合烟的人住在养猫人的旁边 int[] mix = new int[6]; if (uk[4] == 4){ mix = uk; }else if (sd[4] == 4){ mix = sd; }else if (dm[4] == 4){ mix = dm; }else if (nw[4] == 4){ mix = nw; }else if (gm[4] == 4){ mix = gm; } int[] cat = new int[6]; if (uk[2] == 2){ cat = uk; }else if (sd[2] == 2){ cat = sd; }else if (dm[2] == 2){ cat = dm; }else if (nw[2] == 2){ cat = nw; }else if (gm[2] == 2){ cat = gm; } if ((mix[5] - cat[5])!=1 && (cat[5] - mix[5])!=1){ continue GM; } //养马人住在抽DUNHILL烟的人旁边 int[] horse = new int[6]; if (uk[2] == 4){ horse = uk; }else if (sd[2] == 4){ horse = sd; }else if (dm[2] == 4){ horse = dm; }else if (nw[2] == 4){ horse = nw; }else if (gm[2] == 4){ horse = gm; } int[] dun = new int[6]; if (uk[4] == 3){ dun = uk; }else if (sd[4] == 3){ dun = sd; }else if (dm[4] == 3){ dun = dm; }else if (nw[4] == 3){ dun = nw; }else if (gm[4] == 3){ dun = gm; } if ((horse[5] - dun[5])!=1 && (dun[5] - horse[5])!=1){ continue GM; } //抽混合烟的人的邻居喝矿泉水 int[] water = new int[6]; if (uk[3] == 4){ water = uk; }else if (sd[3] == 4){ water = sd; }else if (dm[3] == 4){ water = dm; }else if (nw[3] == 4){ water = nw; }else if (gm[3] == 4){ water = gm; } if ((mix[5] - water[5])!=1 && (water[5] - mix[5])!=1){ continue GM; } //挪威人住在蓝房子旁边 int[] p2 = new int[6]; if (uk[5] == 1){ p2 = uk; }else if (sd[5] == 1){ p2 = sd; }else if (dm[5] == 1){ p2 = dm; }else if (nw[5] == 1){ p2 = nw; }else if (gm[5] == 1){ p2 = gm; } if (p2[1] != 3){ continue GM; } Map result = new HashMap(); result.put("uk", uk); result.put("sd", sd); result.put("dm", dm); result.put("nw", nw); result.put("gm", gm); resultList.add(result); } } } } } for (Object o : resultList){ Map map = (Map)o; Iterator it = map.entrySet().iterator(); while (it.hasNext()){ Entry en = (Entry)it.next(); int[] i = (int[])en.getValue(); if (i[0]==0) System.out.print("英国人 "); if (i[0]==1) System.out.print("瑞典人"); if (i[0]==2) System.out.print("丹麦人 "); if (i[0]==3) System.out.print("挪威人 "); if (i[0]==4) System.out.print("德国人 "); if (i[1]==0) System.out.print("红房子 "); if (i[1]==1) System.out.print("绿房子"); if (i[1]==2) System.out.print("白房子 "); if (i[1]==3) System.out.print("蓝房子 "); if (i[1]==4) System.out.print("黄房子 "); if (i[2]==0) System.out.print("鸟 "); if (i[2]==1) System.out.print("狗 "); if (i[2]==2) System.out.print("猫 "); if (i[2]==3) System.out.print("鱼 "); if (i[2]==4) System.out.print("马 "); if (i[3]==0) System.out.print("咖啡 "); if (i[3]==1) System.out.print("牛奶 "); if (i[3]==2) System.out.print("啤酒 "); if (i[3]==3) System.out.print("茶 "); if (i[3]==4) System.out.print("矿泉水 "); if (i[4]==0) System.out.print("Prince "); if (i[4]==1) System.out.print("Pall Mall"); if (i[4]==2) System.out.print("Blue Master"); if (i[4]==3) System.out.print("Dunhill "); if (i[4]==4) System.out.print("混合型 "); if (i[5]==0) System.out.print("第一间 "); if (i[5]==1) System.out.print("第二间"); if (i[5]==2) System.out.print("第三间 "); if (i[5]==3) System.out.print("第四间 "); if (i[5]==4) System.out.print("第五间 "); System.out.println(); } System.out.println(); } } }
输出结果是:
25 21 33 14 33 德国人 绿房子鱼 咖啡 Prince 第四间 英国人 红房子 鸟 牛奶 Pall Mall第三间 丹麦人 蓝房子 马 茶 混合型 第二间 瑞典人白房子 狗 啤酒 Blue Master第五间 挪威人 黄房子 猫 矿泉水 Dunhill 第一间
程序随手写来,并没有刻意去追求算法效率跟书写版式,相信一定会有更优的求解。 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
可能是我说的不够明白,图表里只反映出文章中列出的第一类的约束条件,目的是降低程序遍历的范围,第二类的约束条件因为比较法复杂,不作人工推理,直接用程序来判断。
比如下面这个,如果绿房子在白房子左边,那么绿房子所在的位置就比白房子小1 //绿房子在白房子左边 int[] green = new int[6]; if (sd[1] == 1){ green = sd; }else if (dm[1] == 1){ green = dm; }else if (nw[1] == 1){ green = nw; }else if (gm[1] == 1){ green = gm; } int[] white = new int[6]; if (sd[1] == 2){ white = sd; }else if (dm[1] == 2){ white = dm; }else if (nw[1] == 2){ white = nw; }else if (gm[1] == 2){ white = gm; } if ((green[5] - white[5]!=-1 )){ continue GM; } |
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
因为是编程求解,所以对人工推理的部分并不要求严格,只要把范围缩小到程序不溢出,能在合理时间范围计算出结果就可以了。上面的程序包括输出,基本上是瞬间跑完,只是程序写的繁琐了点。
|
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
高三的时候,就看见过这个题目了,唉
|
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
这是爱因斯坦出的一道题,支持一下楼主,解出来了,挺不错的,但是可以考虑一下优化一下程序,太多IF了,看着晕!
|
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
学过一门课,专门讲如何推理的。
试图回忆, 不过课的名字和内容已经完全不记得了... |
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
robertliudeqiang 写道 学过一门课,专门讲如何推理的。
试图回忆, 不过课的名字和内容已经完全不记得了... <<逻辑学>>? |
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
lenjey 写道 robertliudeqiang 写道 学过一门课,专门讲如何推理的。
试图回忆, 不过课的名字和内容已经完全不记得了... <<逻辑学>>? 真不记得了,数理逻辑? 只记得: 对这种题目,每个条件表示成一个式子,再通过简单的过程就可以得到结果。有基于推理的语言支持。 |
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
每个公司都想花最少的钱请个天才,什么都会的天才
|
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||
发表时间:2010-03-05
离散数学里讲过这样的,是太多判断了,以前是这个解的好像
A->B C->!D B->!C ==>B->D A推理出B,C推理出,不是D B推出不是C 那么B推出C |
|||||||||||||||||||||||||||||||||||||
返回顶楼 | |||||||||||||||||||||||||||||||||||||