爱因斯坦谜题解答(三种算法比较)

爱因斯坦谜题解答(三种算法比较)爱因斯坦谜题：在一条街上有颜色互不相同的五栋房子，不同国籍的人分别住在这五栋房子力，每人抽不同品牌的香烟，喝不同的饮料，养不同的宠物。已知如下情况：1. 英国人住红色房子里。2. 瑞典人养狗。3. 丹麦人喝茶。4. 绿色房子坐落在白色房子的左面。5. 绿色房子的主人喝咖啡。6. 抽PallMall香烟的人养鸟。7. 黄色房子的主人抽Dunhill香烟。8. 挪威人住第一间房子。9. 五座房子中间的那座的主人喝牛奶。10.抽Blends香烟的住在养猫人的隔壁。11.养马的人住在抽Dunhill香烟者的隔壁。12...

爱因斯坦谜题：在一条街上有颜色互不相同的五栋房子，不同国籍的人分别住在这五栋房子力，每人抽不同品牌的香烟，喝不同的饮料，养不同的宠物。已知如下情况：1. 英国人住红色房子里。2. 瑞典人养狗。3. 丹麦人喝茶。4. 绿色房子坐落在白色房子的左面。5. 绿色房子的主人喝咖啡。6. 抽PallMall香烟的人养鸟。7. 黄色房子的主人抽Dunhill香烟。8. 挪威人住第一间房子。9. 五座房子中间的那座的主人喝牛奶。10.抽Blends香烟的住在养猫人的隔壁。11.养马的人住在抽Dunhill香烟者的隔壁。12.抽BlueMaster香烟的喝啤酒。13.德国人抽Prince香烟。14.挪威人住的房子在蓝色房子的隔壁。15.抽Blends香烟的人有一个喝水的邻居。问：谁养鱼？谜题的英文原文：Letusassumethattherearefivehousesofdifferentcolorsnexttoeachotheronthesameroad.Ineachhouselivesamanofadifferentnationality.Everymanhashisfavoritedrink,hisfavoritebrandofcigarettes,andkeepspetsofaparticularkind.1.TheEnglishmanlivesintheredhouse.2.TheSwedekeepsdogs.推荐精选推荐精选推荐精选3.TheDanedrinkstea.4.Thegreenhouseisjusttotheleftofthewhiteone.5.Theownerofthegreenhousedrinkscoffee.6.ThePallMallsmokerkeepsbirds.7.TheowneroftheyellowhousesmokesDunhills.8.Themaninthecenterhousedrinksmilk.9.TheNorwegianlivesinthefirsthouse.10.TheBlendsmokerhasaneighborwhokeepscats.11.ThemanwhosmokesBlueMastersdrinksbier.12.ThemanwhokeepshorseslivesnexttotheDunhillsmoker.13.TheGermansmokesPrince.14.TheNorwegianlivesnexttothebluehouse.15.TheBlendsmokerhasaneighborwhodrinkswater.Thequestiontobeansweredis:Whokeepsfish? 这道迷题出自1981年柏林的德国逻辑思考学院。据说世界上只有2%的人能出答案。就连大名鼎鼎的爱因斯坦也成为此题大伤脑筋，所以这道题也经常被国内外知名公司用做面试题目，相信许多朋友都只做出过一个答案，今天就用计算机来看看答案： C#代码（代码来源：http://tech.ccidnet.com/art/322/20040304/94061_1.html，在此感谢原作者）：using System;namespace netsafe.math{ public class ayst { ///

/// 问题中的所有元素 ///

string[,] data = { {"黄房子","蓝房子","白房子","红房子","绿房子"}, {"挪威人","英国人","德国人","丹麦人","瑞典人"}, {"DUNHILL","PRINCE","推荐精选推荐精选推荐精选混合烟", "PALL MALL","BLUE MASTER"}, {"咖啡","矿泉水","茶","牛奶"," 啤酒 "}, {"鱼"," 恐龙","马", "鸟","狗"} }; ///

/// answer用来存放答案 ///

int[,] answer = new int[6, 6]; int[,] ALL = new int[6, 122]; int count = 1; int nLevel = 0; int[] List = new int[6]; public static void Main(string[] args) { ayst c = new ayst(); c.p(); ///生成全排列到all c.run(); Console.Read(); /// 按任意键继续 } void run() { int i1, i2, i3, i4, i5;///通过逻辑条件顺序的有效选择来优化程序 for (i1 = 1; i1 <= 120; i1++)///房子 { ///9 、挪威人住第一间房子 ///14 、挪威人住在蓝房子旁边 ///不满足条件就短路 /// if (ALL[2, i1] != 2) continue; for (int j = 0; j < 5; j++, answer[j, 1] = ALL[j, i1]) ; for (i2 = 1; i2 <= 120; i2++)///人种推荐精选推荐精选推荐精选 { for (int j = 0; j < 5; j++, answer[j, 2] = ALL[j, i2]) ; ///9 、挪威人住第一间房子 if (ALL[1, i2] != 1) continue; ///1、英国人住在红房子里 /// if (find(1, 4) != find(2, 2)) continue; ///4 、绿房子在白房子左边 /// if (find(1, 5) > find(1, 3)) continue; for (i3 = 1; i3 <= 120; i3++)///烟 { for (int j = 0; j < 5; j++, answer[j, 3] = ALL[j, i3]) ; ///13、德国人抽PRINCE烟 /// if (find(2, 3) != find(3, 2)) continue; ///7 、黄房子主人抽DUNHILL烟 /// if (find(1, 1) != find(3, 1)) continue; for (i4 = 1; i4 <= 120; i4++)///饮料 { for (int j = 0; j < 5; j++, answer[j, 4] = ALL[j, i4]) ; ///8 、住在中间那间房子的人喝牛奶 /// if (ALL[3, i4] != 4) continue; ///5 、绿房子主人喝咖啡 /// if (find(1, 5) != find(4, 1)) continue; ///3 、丹麦人喝茶 /// 推荐精选推荐精选推荐精选 if (find(2, 4) != find(4, 3)) continue; ///15 、抽混合烟的人的邻居喝矿泉水 if (Math.Abs(find(3, 3) - find(4, 2)) != 1) continue; ///12 、抽BLUE MASTER烟的人喝啤酒 /// if (find(3, 5) != find(4, 5)) continue; for (i5 = 1; i5 <= 120; i5++)///宠物 { for (int j = 0; j < 5; j++, answer[j, 5] = ALL[j, i5]) ; ///10 、抽混合烟的人住在养鱼人的旁边 /// if (Math.Abs(find(3, 3) - find(5, 1)) != 1) continue; ///2 、瑞典人养了一条狗 /// if (find(2, 5) != find(5, 5)) continue; ///6 、抽PALL MALL烟的人养了一只鸟 /// if (find(3, 4) != find(5, 4)) continue; ///11 、养马人住在DUNHILL烟的人旁边 /// if (Math.Abs(find(5, 3) - find(3, 1)) != 1) continue; /// ///能活到这里的data,当然是答案喽 /// write_answer(); } } } } } }推荐精选推荐精选推荐精选 ///

/// 非常典型的用递归实现排列组合算法。 ///

public void p() { int nCount, nJudge, key; nLevel++; if (nLevel > 5) { writeall();///有一种排列就写到All数组里 nLevel--; return; } for (nCount = 1; nCount <= 5; nCount++) { key = 0; for (nJudge = 0; nJudge <= nLevel - 1; nJudge++) if (nCount == List[nJudge]) { key = 1; break; } if (key == 0) { List[nLevel] = nCount; p(); } } nLevel--; }推荐精选推荐精选推荐精选 ///

/// 写入all数组 ///

void writeall() { int i; for (i = 1; i <= 5; i++) { ALL[i, count] = List[i]; } count++; } int find(int i, int j) { int k; for (k = 0; k <= 5; k++) { if (answer[k, i] == j) { return k; } } return -1; } ///

/// 将答案打印出来 ///

void write_answer() { 推荐精选推荐精选推荐精选for (int i = 1; i <= 5; i++) { for (int j = 1; j <= 5; j++) { Console.Write(data[i - 1, answer[j, i] - 1] + ","); } Console.WriteLine(); } Console.WriteLine(); } }}运行以后结果是：　推荐精选推荐精选推荐精选　可以看出答案并不唯一，有许多组合理的答案。还有一种暴力破解的算法C#代码如下（代码来源：http://www.pconline.com.cn/pcedu/empolder/net/cs/0509/acc/05-09-21-e-2.txt，感谢原作者提供代码让我们学习）：using System;using System.Collections.Generic;using System.Text;推荐精选推荐精选推荐精选namespace 爱因斯坦迷题1{ enum 国籍 { 英国, 瑞典, 丹麦, 挪威, 德国 }; enum 颜色 { 红, 绿, 蓝, 黄, 白 }; enum 宠物 { 鸟, 猫, 马, 鱼, 狗 }; enum 饮料 { 水, 牛奶, 咖啡, 茶, 啤酒 }; enum 香烟 { blends, blue, prince, dunhill, pall }; public class ProTable { private const string rule = @" 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香烟的人有一个喝水的邻居 "; public string Rule { get { return rule; } } private enum T { 国籍 = 0, 颜色, 宠物, 饮料, 香烟 }; private const int N = 5; //求排列 private static int[,] aid = new int[120, N]; static ProTable() { int k = 0; for (int i0 = 0; i0 < N; i0++) { for (int i1 = 0; i1 < N; i1++) { if (i1 == i0) continue; for (int i2 = 0; i2 < N; i2++) { if (i2 == i1 || i2 == i0) continue; for (int i3 = 0; i3 < N; i3++) { if (i3 == i2 || i3 == i1 || i3 == i0) continue; for (int i4 = 0; i4 < N; i4++) { if (i4 == i3 || i4 == i2 || i4 == i1 || i4 == i0) continue; aid[k, 0] = i0; aid[k, 1] = i1; aid[k, 2] = i2; aid[k, 3] = i3; aid[k, 4] = i4; k++;推荐精选推荐精选推荐精选 } } } } } } //判断矩阵 // 国籍,颜色,宠物,饮料,香烟 //1 //2 //3 //4 //5 private int[,] array = new int[N, N]; //根据排列数组生成 private void replace(int i, int j) { for (int k = 0; k < N; k++) { array[k, i] = aid[j, k]; } } //通过getXX得到相应的行号 private int get香烟(香烟 n) { 推荐精选推荐精选推荐精选for (int i = 0; i < array.Length; i++) if (array[i, (int)T.香烟] == (int)n) return i; return -1; } private int get饮料(饮料 n) { for (int i = 0; i < array.Length; i++) if (array[i, (int)T.饮料] == (int)n) return i; return -1; } private int get宠物(宠物 n) { for (int i = 0; i < array.Length; i++) if (array[i, (int)T.宠物] == (int)n) return i; return -1; } private int get国籍(国籍 n) { for (int i = 0; i < array.Length; i++) if (array[i, (int)T.国籍] == (int)n) return i; return -1; } private int get颜色(颜色 n) { for (int i = 0; i < array.Length; i++) if (array[i, (int)T.颜色] == (int)n) 推荐精选推荐精选推荐精选return i; return -1; } //规则： //1、英国人住红色房子 //2、瑞典人养狗 //3、丹麦人喝茶 //4、绿色房子在白色房子左面 //5、绿色房子主人喝咖啡 //6、抽Pall Mall 香烟的人养鸟 //7、黄色房子主人抽Dunhill 香烟 //8、住在中间房子的人喝牛奶 //9、挪威人住第一间房 //10、抽Blends香烟的人住在养猫的人隔壁 //11、养马的人住抽Dunhill 香烟的人隔壁 //12、抽Blue Master的人喝啤酒 //13、德国人抽Prince香烟 //14、挪威人住蓝色房子隔壁 //15、抽Blends香烟的人有一个喝水的邻居 //1、英国人住红色房子 private bool assert1() { if (!( array[get国籍(国籍.英国), (int)T.颜色] == (int)颜色.红 )) return false; 推荐精选推荐精选推荐精选return true; } //2、瑞典人养狗 private bool assert2() { if (!( array[get国籍(国籍.瑞典), (int)T.宠物] == (int)宠物.狗 )) return false; return true; } //3、丹麦人喝茶 private bool assert3() { if (!( array[get国籍(国籍.丹麦), (int)T.饮料] == (int)饮料.茶 )) return false; return true; } //4、绿色房子在白色房子左面 private bool assert4() { if (!( get颜色(颜色.绿) == (get颜色(颜色.白) - 1) //另一种理解get颜色(颜色.绿) < get颜色(颜色.白) )) return false;推荐精选推荐精选推荐精选 return true; } //5、绿色房子主人喝咖啡 private bool assert5() { if (!( array[get颜色(颜色.绿), (int)T.饮料] == (int)饮料.咖啡 )) return false; return true; } //6、抽Pall Mall 香烟的人养鸟 private bool assert6() { if (!( array[get香烟(香烟.pall), (int)T.宠物] == (int)宠物.鸟 )) return false; return true; } //7、黄色房子主人抽Dunhill 香烟 private bool assert7() { if (!( array[get颜色(颜色.黄), (int)T.香烟] == (int)香烟.dunhill )) return false;推荐精选推荐精选推荐精选 return true; } //8、住在中间房子的人喝牛奶 private bool assert8() { if (!( array[2, (int)T.饮料] == (int)饮料.牛奶 )) return false; return true; } //9、挪威人住第一间房 private bool assert9() { int i = get国籍(国籍.挪威); if (!( i == 0 || i == 4 )) return false; return true; } //10、抽Blends香烟的人住在养猫的人隔壁 private bool assert10() { int t1 = get香烟(香烟.blends), t2 = get宠物(宠物.猫); if (!( t1 == (t2 + 1) || t1 == (t2 - 1) ))推荐精选推荐精选推荐精选 return false; return true; } //11、养马的人住抽Dunhill 香烟的人隔壁 private bool assert11() { int t1 = get宠物(宠物.马); int t2 = get香烟(香烟.dunhill); if (!( t1 == (t2 + 1) || t1 == (t2 - 1) )) return false; return true; } //12、抽Blue Master的人喝啤酒 private bool assert12() { if (!( array[get香烟(香烟.blue), (int)T.饮料] == (int)饮料.啤酒 )) return false; return true; } //13、德国人抽Prince香烟 private bool assert13() { if (!( array[get推荐精选推荐精选推荐精选国籍(国籍.德国), (int)T.香烟] == (int)香烟.prince )) return false; return true; } //14、挪威人住蓝色房子隔壁 private bool assert14() { int t1 = get国籍(国籍.挪威); int t2 = get颜色(颜色.蓝); if (!( t1 == (t2 + 1) || t1 == (t2 - 1) )) return false; return true; } //15、抽Blends香烟的人有一个喝水的邻居 private bool assert15() { int t1 = get香烟(香烟.blends); int t2 = get饮料(饮料.水); if (!( t1 == (t2 + 1) || t1 == (t2 - 1) )) return false; return true; } 推荐精选推荐精选推荐精选private bool assert() { return assert1() && assert2() && assert3() && assert4() && assert5() && assert6() && assert7() && assert8() && assert9() && assert10() && assert11() && assert12() && assert13() && assert14() && assert15(); } /*纯暴力算法以作比较 public void Solve_() { for (int i0 = 0; i0 < aid.GetUpperBound(0); i0++) { replace(0, i0); for (int i1 = 0; i1 < aid.GetUpperBound(0); i1++) { replace(1, i1); for (int i2 = 0; i2 < aid.GetUpperBound(0); i2++) { replace(2, i2); for (int i3 = 0; i3 < aid.GetUpperBound(0); i3++) { replace(3, i3); for (int i4 = 0; i4 < aid.GetUpperBound(0); i4++) { replace(4, i4); if (assert()) { Console.WriteLine(this); } } }推荐精选推荐精选推荐精选 } } } } */ public void Solve() { //解号 int sn = 1; //逐步生成判别表的算法 for (int i0 = 0; i0 < aid.GetUpperBound(0); i0++) { replace((int)T.国籍, i0); if (!assert9()) continue; for (int i1 = 0; i1 < aid.GetUpperBound(0); i1++) { replace((int)T.饮料, i1); if (!assert8()) continue; if (!(assert3())) continue; for (int i2 = 0; i2 < aid.GetUpperBound(0); i2++) { replace((int)T.颜色, i2); if (!assert4()) continue; 推荐精选推荐精选推荐精选if (!(assert1() && assert14() && assert5())) continue; for (int i3 = 0; i3 < aid.GetUpperBound(0); i3++) { replace((int)T.宠物, i3); if (!(assert2())) continue; for (int i4 = 0; i4 < aid.GetUpperBound(0); i4++) { replace((int)T.香烟, i4); if (!(assert6() && assert7() && assert10() && assert11() && assert12() && assert15() && assert13())) continue; if (assert()) { Console.WriteLine("解：" + sn++); Console.WriteLine(this); } } } } } } } //国籍=0,颜色,宠物,饮料,香烟 public override string ToString() { StringBuilder sb = new StringBuilder(); for (int i = 0; i < 5; i++) { sb.Append((i + 1).ToString() + ": ");推荐精选推荐精选推荐精选 sb.Append(Enum.GetName(typeof(国籍), array[i, (int)T.国籍]) + ", "); sb.Append(Enum.GetName(typeof(颜色), array[i, (int)T.颜色]) + ", "); sb.Append(Enum.GetName(typeof(宠物), array[i, (int)T.宠物]) + ", "); sb.Append(Enum.GetName(typeof(饮料), array[i, (int)T.饮料]) + ", "); sb.Append(Enum.GetName(typeof(香烟), array[i, (int)T.香烟]) + "\n"); } return sb.ToString(); } } class Program { static void Main(string[] args) { ProTable t = new ProTable(); t.Solve(); } }}运行的结果是：推荐精选推荐精选推荐精选这个结果和第一种算法的结果有点出入，只有两种答案，但仔细看，这两组答案是完全相同的，等于只有唯一的一种答案，这种解答的方法，算法还需要研究学习的．另外也有人用ｊａｖａ实现了该算法，收录的代码如下（代码出处：http://www.matrix.org.cn/resource/article/2005-11-10/java_43941.html同样在此感谢原作者）：/* * Created on 2005-11-8 * * TODO To change the template for this generated file go to * Window - Preferences - Java - Code Style - Code Templates */package com.netengine.test;/** * @author cds * * TODO To change the template for this generated type comment go to * Window - Preferences - Java - Code Style - Code Templates */public class WhoFeedsFish { private static final String problem = "爱因斯坦的推理题：\n\n"+ "1．有5栋5种颜色的房子\n"+ "2．每一位房子的主人国籍都不同\n"+ "3．这五个人每人只喝一个牌子的饮料，只抽一个牌子的香烟，只养一种宠物\n"+ "4．没有人有相同的宠物，抽相同牌子的烟，喝相同牌子的饮料\n\n"+ "已知条件：\n"+ "1．英国人住在红房子里\n"+ "2．瑞典人养了一条狗\n"+ "3推荐精选推荐精选推荐精选．丹麦人喝茶\n"+ "4．绿房子在白房子的左边\n"+ "5．绿房子主人喝咖啡\n"+ "6．抽pallmall烟的人养了一只鸟\n"+ "7．黄房子主人抽dunhill烟\n"+ "8．住在中间房子的人喝牛奶\n"+

                    本文档为【爱因斯坦谜题解答(三种算法比较)】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

爱因斯坦谜题解答(三种算法比较)

你可能还喜欢