|
下面的問題相信很多人都聽過：
1 有五棟五種顏色的房子
2 每一位房子的主人國籍都不同
3 這五個人每人只喝一種飲料，只抽一種牌子的香煙，只養(yǎng)一種寵物
4 沒有人有相同的寵物，抽相同牌子的香煙，喝相同的飲料
提示：
1、 英國人住在紅房子里
2 、瑞典人養(yǎng)了一條狗
3 、丹麥人喝茶
4 、綠房子在白房子左邊
5 、綠房子主人喝咖啡
6 、抽PALL MALL煙的人養(yǎng)了一只鳥
7 、黃房子主人抽DUNHILL煙
8 、住在中間那間房子的人喝牛奶
9 、挪威人住第一間房子
10 、抽混合煙的人住在養(yǎng)魚人的旁邊
11 、養(yǎng)馬人住在DUNHILL煙的人旁邊
12 、抽BLUE MASTER煙的人喝啤酒
13、 德國人抽PRINCE煙
14 、挪威人住在藍(lán)房子旁邊
15 、抽混合煙的人的鄰居喝礦泉水
問題是： 誰養(yǎng)魚？
這道迷題出自1981年柏林的德國邏輯思考學(xué)院。據(jù)說世界上只有2%的人能出答案。就連大名鼎鼎的愛因斯坦也成為此題大傷腦筋，所以這道題也經(jīng)常被國內(nèi)外知名公司用做面試題目，相信許多朋友都只做出過一個答案，如果碰巧你屬于那98%該怎么辦呢。沒關(guān)系，如果這個問題用電腦來解決就非常easy了。
程序代碼如下：
using System;
namespace netsafe.math
{
public class ayst
{
/// <summary>
/// 問題中的所有元素
/// </summary>
string[,] data= {{"黃房子", "藍(lán)房子", "白房子", "紅房子", "綠房子"},
{"挪威人", "英國人", "德國人", "丹麥人", "瑞典人"},
{"DUNHILL", "PRINCE", "混合煙", "PALL MALL", "BLUE MASTER"},
{"咖 啡", "礦泉水", "茶", "牛奶", " 啤酒 "},
{"魚", " 恐龍", "馬", "鳥", "狗"}};
/// <summary>
/// answer用來存放答案
/// </summary>
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(); /// 按任意鍵繼續(xù)
}
void run()
{
int i1,i2,i3,i4,i5;
///通過邏輯條件順序的有效選擇來優(yōu)化程序
for (i1=1;i1<=120;i1++) ///房子
{
/// 9 、挪威人住第一間房子
/// 14 、挪威人住在藍(lán)房子旁邊
/// 不滿足條件就短路
///
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 、抽混合煙的人住在養(yǎng)魚人的旁邊
///
if(Math.Abs(find(3,3)-find(5,1))!=1)continue;
/// 2 、瑞典人養(yǎng)了一條狗
///
if(find(2,5)!=find(5,5))continue;
/// 6 、抽PALL MALL煙的人養(yǎng)了一只鳥
///
if(find(3,4)!=find(5,4))continue;
/// 11 、養(yǎng)馬人住在DUNHILL煙的人旁邊
///
if(Math.Abs(find(5,3)-find(3,1))!=1)continue;
///
///能活到這里的data,當(dāng)然是答案嘍
///
write_answer();
}
}
}
}
}
}
/// <summary>
/// 非常典型的用遞歸實現(xiàn)排列組合算法。
/// </summary>
public void p()
{
int nCount,nJudge,key;
nLevel++;
if(nLevel>5)
{
writeall();///有一種排列就寫到All數(shù)組里
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--;
}
/// <summary>
/// 寫入all數(shù)組
/// </summary>
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;
}
/// <summary>
/// 將答案打印出來
/// </summary>
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#，在Microsoft Visual Studio.net下編譯執(zhí)行通過。如果你沒有Microsoft Visual C# 需要安裝Microsoft(r) .NET Framework SDK ,把上述代碼保存到ayst.cs,然后在命令行模式下執(zhí)行csc ayst.cs ,然后執(zhí)行ayst.exe也可以。這個程序是很久之前寫的。當(dāng)時只是為了得到答案，所以程序?qū)懙谋容^亂。讓同行見笑了。以下是程序的運(yùn)行結(jié)果（答案一總7種，沒想到吧）：
黃房子,藍(lán)房子,紅房子,綠房子,白房子,
挪威人,丹麥人,英國人,德國人,瑞典人,
DUNHILL,混合煙,PALL MALL,PRINCE,BLUE MASTER,
礦泉水,茶,牛奶,咖 啡, 啤酒 ,
魚,馬,鳥, 恐龍,狗,
綠房子,藍(lán)房子,黃房子,紅房子,白房子,
挪威人,德國人,瑞典人,英國人,丹麥人,
混合煙,PRINCE,DUNHILL,BLUE MASTER,PALL MALL,
咖 啡,礦泉水,牛奶, 啤酒 ,茶,
恐龍,魚,狗,馬,鳥,
綠房子,藍(lán)房子,白房子,黃房子,紅房子,
挪威人,德國人,瑞典人,丹麥人,英國人,
PALL MALL,PRINCE,混合煙,DUNHILL,BLUE MASTER,
咖 啡,礦泉水,牛奶,茶, 啤酒 ,
鳥,魚,狗, 恐龍,馬,
綠房子,藍(lán)房子,白房子,黃房子,紅房子,
挪威人,德國人,瑞典人,丹麥人,英國人,
PALL MALL,PRINCE,混合煙,DUNHILL,BLUE MASTER,
咖 啡,礦泉水,牛奶,茶, 啤酒 ,
鳥, 恐龍,狗,魚,馬,
綠房子,藍(lán)房子,白房子,紅房子,黃房子,
挪威人,德國人,瑞典人,英國人,丹麥人,
PALL MALL,PRINCE,混合煙,BLUE MASTER,DUNHILL,
咖 啡,礦泉水,牛奶, 啤酒 ,茶,
鳥,魚,狗,馬, 恐龍,
綠房子,藍(lán)房子,紅房子,黃房子,白房子,
挪威人,德國人,英國人,丹麥人,瑞典人,
PALL MALL,PRINCE,混合煙,DUNHILL,BLUE MASTER,
咖 啡,礦泉水,牛奶,茶, 啤酒 ,
鳥,魚,馬, 恐龍,狗,
綠房子,藍(lán)房子,紅房子,黃房子,白房子,
挪威人,德國人,英國人,丹麥人,瑞典人,
PALL MALL,PRINCE,混合煙,DUNHILL,BLUE MASTER,
咖 啡,礦泉水,牛奶,茶, 啤酒 ,
鳥, 恐龍,馬,魚,狗,
|
