注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Bioinformatics home

 
 
 

日志

 
 

爱因斯坦谜题:谁养鱼(C#版) 1  

2009-09-29 12:40:52|  分类: C# |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一个偶然的机会再次接触到了爱因斯坦谜题,一时来了兴致,用C#做了一个程序,看看到底是谁养鱼(大学毕业后接触过这道题,不过很遗憾,那时的我没有成为2%的人,所以不知道是谁在养鱼)?

这道迷题出自1981年柏林的德国逻辑思考学院,据说世界上只有2%的人能出答案,就连大名鼎鼎的爱因斯坦也成为此题大伤脑。爱因斯坦谜题的中文表述是这样的:

1. 有5栋5种颜色的房子

2. 每一位房子的主人国籍都不同

3. 这五个人每人只喝一个牌子的饮料,只抽一个牌子的香烟,只养一种宠物

4. 没有人有相同的宠物,抽相同牌子的烟,喝相同牌子的饮料

已知条件:

1. 英国人住在红房子里

2. 瑞典人养了一条狗

3. 丹麦人喝?

4. 绿房子在白房子的左边

5. 绿房子主人喝咖啡

6. 抽pallmall烟的人养了一只鸟

7. 黄房子主人抽dunhill烟

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

9. 挪威人住在第一间房子

10.抽混合烟的人住在养猫人的旁边

11.养马人住在抽dunhill烟人的旁边

12.抽bluemaster烟的人喝啤酒

13.德国人抽prince烟

14.挪威人住在蓝房子旁边

15.抽混合烟的人的邻居喝矿泉水

问题:谁养鱼?

很遗憾的是,这个中文表述有问题,至少有以下几方面的歧义:

一、如何区分左右?二、已知条件中的第4条,绿房子在白房子的左边,是紧邻?还是可以分开?三、第一个房子,从什么方向开始算起,左,还是右?

如果仅把上面的第二点提到的绿房子在白房子的左边,不限于紧邻,则会出现7组符合条件的组合,3个答案:丹麦人养鱼(3组)、德国人养鱼(3组)、挪威人养鱼(1组)。

这显然不符合爱因斯坦谜题的本意,所以又查了查英文原题,结果真相大白,其严谨的表述有效的消除了以上的歧义。那最终的结果究竟又如何呢?

英文原题:

The Einstein Puzzle

 

There are 5 houses in five different colors. They are lined up in a row side by side.

In each house lives a person with a different nationality.

These 5 owners drink a certain drink, smoke a certain brand of tobacco and keep a certain pet.

No owners have the same pet, smoke the same tobacco, or drink the same drink.

As you look at the 5 houses from across the street, the green house is adjacent(woog注释:adjacent adj,毗连的,邻近的,接近的;n,近邻) to the left of the white house

The Big Question is:

Who owns the Fish?

 

CLUES:

1、The Brit lives in the red house

2、The Swede keeps dogs as pets

3、The Dane drinks tea

4、The green house is on the immediate left of the white house as you stare at the front of the 5 houses

5、The green house owner drinks coffee

6、The person who smokes Pall Mall raises birds

7、The owner of the yellow house smokes Dunhill

8、The man living in the house right in the center drinks milk

9、The Norwegian lives in the first house

10、The man who smokes Blends lives next to the one who keeps cats

11、The man who keeps horses lives next to the one who smokes Dunhill

12、The owner who smokes Bluemaster drinks juice

13、The German smokes Prince

14、The Norwegian lives next to the blue house

15、The man who smokes Blend has a neighbor who drinks water.

 

相关代码如下(考虑了两种情况,当#define FastCompute时,仅有一组答案):

 

view plaincopy to clipboardprint?
//[叶帆工作室] http://blog.csdn.net/yefanqiu  
#define FastCompute       
using System;  
using System.Collections.Generic;  
using System.ComponentModel;  
using System.Data;  
using System.Drawing;  
using System.Text;  
using System.Windows.Forms;  
using System.Diagnostics;      
 
namespace Einstein  
{  
    public partial class frmMain : Form  
    {  
        public frmMain()  
        {  
            InitializeComponent();  
        }  
 
        private void btnRun_Click(object sender, EventArgs e)  
        {                                                    
            Arithmetic arithmetic = new Arithmetic();        
            DateTime dt = DateTime.Now;  
            string  result = arithmetic.DoResult();  
            MessageBox.Show(result + "\r\n耗时:" + (DateTime.Now - dt).TotalSeconds.ToString() + "秒");  
        }             
    }  
 
    public class Arithmetic  
    {  
        string[] people   = new string[] { "英国", "瑞典", "丹麦", "挪威", "德国" };  
        string[] house = new string[] { "红", "绿", "白", "黄", "蓝" };  
        string[] drink = new string[] { "茶", "咖啡", "牛奶", "啤酒", "水" };  
        string[] smoke = new string[] { "Pall Mall", "Dunhill", "Blends", "Blue Master", "Prince" };  
        string[] pet = new string[] { "狗", "鸟", "猫", "马", "鱼" };  
 
        List<string[]> lstCombination = new List<string[]>();   //存放全部结果(预删减后的结果)  
        List<string[]> lstCombination0 = new List<string[]>();  
        List<string[]> lstCombination1 = new List<string[]>();  
        List<string[]> lstCombination2 = new List<string[]>();  
        List<string[]> lstCombination3 = new List<string[]>();  
        List<string[]> lstCombination4 = new List<string[]>();  
                                
        public string DoResult()  
        {  
            string[,] result = new string[5, 5];  
 
            //生成全部的组合  
            MakeCombination();  
            //预剔除不符合条件的组合  
            EliminateCombination();  
            //获得有可能的组合0  
            EliminateCombination0();  
            //获得有可能的组合1  
            EliminateCombination1();  
            //获得有可能的组合2  
            EliminateCombination2();  
            //获得有可能的组合3  
            EliminateCombination3();  
            //获得有可能的组合4  
            EliminateCombination4();  
 
            string strInfo = "";  
            int intNum = 0;  
 
            for (int i = 0; i < lstCombination0.Count; i++)      
            {  
                ToCombination(result, 0, lstCombination0,i);  
                for (int j =0; j < lstCombination1.Count; j++)    
                {  
                    ToCombination(result, 1, lstCombination1,j);  
                    for (int k = 0; k < lstCombination2.Count; k++)   
                    {  
                        ToCombination(result,  2,lstCombination2, k);  
                        for (int l =0; l < lstCombination3.Count; l++)    
                        {  
                            ToCombination(result,  3,lstCombination3, l);  
                            for (int m =0; m < lstCombination4.Count; m++)   
                            {  
                                ToCombination(result, 4,lstCombination4, m);  
 
                                bool Flag=true;  
                                for (int e = 0; e < 5; e++)  
                                {  
                                    if (result[0, e] == result[1, e] || result[0, e] == result[2, e] || result[0, e] == result[3, e] || result[0, e] == result[4, e] ||  
                                        result[1, e] == result[2, e] || result[1, e] == result[3, e] || result[1, e] == result[4, e] ||  
                                        result[2, e] == result[3, e] || result[2, e] == result[4, e] ||  
                                        result[3, e] == result[4, e])  
                                    {  
                                        Flag = false;  
                                        break;  
                                    }  
                                }  
    
                                //判断组合是否成立  
                                if (Flag && Judge(result))  
                                {  
                                    strInfo += "---------------- " + (++intNum).ToString()+" ----------------\r\n";  
                                    for (int ii = 0; ii < 5; ii++)  
                                    {  
                                        for (int jj = 0; jj < 5; jj++)  
                                        {  
                                            strInfo += result[ii, jj] + " ";  
                                        }  
                                        strInfo += "\r\n";  
                                    } 
#if FastCompute  
                                    strInfo += "------------------------------------\r\n";  
                                    return strInfo; 
#endif  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
 
            strInfo += "------------------------------------\r\n";  
            return strInfo;             
        }  
 
        private void ToCombination(string[,] result,int index, List<string[]>  lst,int num)  
        {  
            for (int i = 0; i < 5; i++)  
            {  
                result[index, i] = lst[num][i];  
            }  
        }  
 
        //生成全部的组合  
        private void MakeCombination()  
        {  
            string[] combination = new string[5];  
 
            //5*5*5*5*5=3125  
            for (int i = 0; i < 5; i++) //国籍  
            {  
                combination[0] = people[i];  
                for (int j = 0; j < 5; j++)  //房子  
                {  
                    combination[1] = house[j];  
                    for (int k = 0; k < 5; k++)  //饮料  
                    {  
                        combination[2] = drink[k];  
                        for (int l = 0; l < 5; l++)  //香烟  
                        {  
                            combination[3] = smoke[l];  
                            for (int m = 0; m < 5; m++)  //宠物  
                            {  
                                combination[4] = pet[m];  
                                lstCombination.Add((string[])combination.Clone());  
                            }  
                        }  
                    }  
                }  
            }  
        }  
 
        //剔除组合的判断条件  
        private bool JudgeCombination(string[] combination)  
        {  
            //1、英国住红房子  
            if (combination[0] == "英国" && combination[1] != "红") return false;  
            //2、瑞典养狗  
            if (combination[0] == "瑞典" && combination[4] != "狗") return false;  
            //3、丹麦喝茶  
            if (combination[0] == "丹麦" && combination[2] != "茶") return false;  
            //5、绿房子主喝咖啡  
            if (combination[1] == "绿" && combination[2] != "咖啡") return false;  
            //6、抽Pall Mall香烟的养鸟  
            if (combination[3] == "Pall Mall" && combination[4] != "鸟") return false;  
            //7、黄房子主抽Dunhill香烟  
            if (combination[1] == "黄" && combination[3] != "Dunhill") return false;  
            //12、抽Blue Master的喝啤酒  
            if (combination[3] == "Blue Master" && combination[2] != "啤酒") return false;  
            //13、德国抽Prince香烟  
            if (combination[0] == "德国" && combination[3] != "Prince") return false;  
            return true;  
        }  
 
        //预剔除不符合条件的组合  
        private void EliminateCombination()  
        {  
            string[] combination=new string[5];  
            int num=lstCombination.Count;  
            int index = 0;  
            while ((num--)>0)  
            {  
                if (!JudgeCombination(lstCombination[index]))  
                {  
                    lstCombination.RemoveAt(index);  
                }  
                else 
                {  
                    index++;  
                }                  
            }  
        }  
 
        //创建组合0  
        private void EliminateCombination0()  
        {  
            lstCombination0.Clear();   
            foreach (string[] combination in lstCombination)  
            {  
                //combination[1] != "红" && combination[1] != "蓝" && combination[1] != "白" && combination[1] != "绿" 
#if FastCompute  
                if (combination[0] == "挪威" && combination[1] == "黄" && combination[2] != "牛奶" && combination[2] != "茶" && combination[3] != "Prince" && combination[4] != "狗") 
#else  
                if (combination[0] == "挪威" && combination[1] != "红" && combination[1] != "蓝" && combination[1] != "白"  && combination[2] != "牛奶" && combination[2] != "茶" && combination[3] != "Prince" && combination[4] != "狗") 
#endif  
                {            
                    lstCombination0.Add(combination);  
                }                                                                         
            }      
        }  
 
        //创建组合1  
        private void EliminateCombination1()  
        {  
            lstCombination1.Clear();  
            foreach (string[] combination in lstCombination)  
            {  
                if (combination[0] != "挪威" &&  combination[1] == "蓝" && combination[2] != "牛奶")  
                {  
                    lstCombination1.Add(combination);  
                }  
            }  
        }  
 
        //创建组合2  
        private void EliminateCombination2()  
        {  
            lstCombination2.Clear();  
            foreach (string[] combination in lstCombination)  
            { 
#if FastCompute  
                if (combination[0] != "挪威" && combination[0] != "丹麦" && combination[1] != "蓝" && combination[1] != "黄" && combination[1] != "白" && combination[2] == "牛奶") 
#else                 
                if (combination[0] != "挪威" && combination[0] != "丹麦" && combination[1] != "蓝"  && combination[2] == "牛奶") 
#endif  
                {  
                    lstCombination2.Add(combination);  
                }  
            }  
        }  
 
        //创建组合3  
        private void EliminateCombination3()  
        {  
            lstCombination3.Clear();  
            foreach (string[] combination in lstCombination)  
            { 
#if FastCompute  
                if (combination[0] != "挪威" && combination[1] != "黄" && combination[1] != "蓝" && combination[2] != "牛奶") 
#else  
                if (combination[0] != "挪威" && combination[1] != "蓝" && combination[2] != "牛奶") 
#endif  
                {  
                    lstCombination3.Add(combination);  
                }  
            }  
        }  
 
        //创建组合4  
        private void EliminateCombination4()  
        {  
            lstCombination4.Clear();  
            foreach (string[] combination in lstCombination)  
            { 
#if FastCompute  
                if (combination[0] != "挪威" && combination[1] != "黄" && combination[1] != "蓝" && combination[1] != "绿" && combination[2] != "牛奶") 
#else                 
                if (combination[0] != "挪威" && combination[1] != "蓝" && combination[1] != "绿" && combination[2] != "牛奶") 
#endif  
                {  
                    lstCombination4.Add(combination);  
                }  
            }  
        }  
       
        //判断  
        private static bool Judge(string[,] combination)  
        {             
            for (int index = 0;index < 5; index++)  
            {  
                //4、绿房子在白房子左面 
#if FastCompute  
                if (index > 0 && combination[index, 1] == "白" && combination[index - 1, 1] != "绿") return false; 
#else  
                if (combination[index, 1] == "白")  
                {  
                    for (int i = index + 1; i < 5; i++)  
                    {  
                        if (combination[i, 1] == "绿")  //绿房子不可能出现在白房子的右边  
                            return false;  
                    }   
                } 
#endif          
                //8、住在中间的喝牛奶  
                if (combination[2, 2] != "牛奶") return false;  
                //9、挪威住第一间房  
                if (combination[0, 0] != "挪威") return false;  
                //10、抽Blends香烟的住在养猫的隔壁  
                if (combination[index, 3] == "Blends")  
                {  
                    if(!((index>0 && combination[index-1,4]=="猫") || (index<4 && combination[index+1,4]=="猫")))  
                    {  
                         return false;  
                    }  
                }  
                //11、养马住在抽Dunhill香烟的隔壁  
                if (combination[index, 4] == "马")  
                {  
                    if (!((index > 0 && combination[index - 1, 3] == "Dunhill") || (index < 4 && combination[index + 1, 3] == "Dunhill")))  
                    {  
                        return false;  
                    }  
                }  

  评论这张
 
阅读(788)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017