一道爱因斯坦的思考题,爱因斯坦声称世界上只有2%的人能解出,你看呢?
/*爱因斯坦的思考题在网上看到了个有趣的逻辑推理题，爱因斯坦声称世界上只有2%的人能解出：
有五个具有五种不同颜色的房间排成一排；
每个房间里分别住着一个不同国籍的人；
每个人都在喝一种特定品牌的饮料，抽一特定品牌的烟，养一特定的宠物；
没有任意两个人在抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物。
问题：谁在养鱼作为宠物？
爱因斯坦给出如下线索：
英国人住在红色的房子里；
瑞典人养狗作为宠物；
丹麦人喝茶；
绿房子紧挨着白房子，在白房子的左边；
绿房子的主人喝咖啡；
抽Pall Mall牌香烟的人养鸟；
黄色房子里的人抽Dunhill牌香烟；
住在中间那个房子里的人喝牛奶；
挪威人住在第一个房子里面；
抽Blends牌香烟的人和养猫的人相邻；
养马的人和抽Dunhill牌香烟的人相邻；
抽BlueMaster牌香烟的人喝啤酒；
德国人抽Prince牌香烟；
挪威人和住在蓝房子的人相邻；
抽Blends牌香烟的人和喝矿泉水的人相邻。
国家 房子 宠物 饮料 香烟
挪威 黄色 猫 矿泉水 Dunhill
丹麦 蓝色 马 茶 Blends
英国 红色 鸟 牛奶 PallMall
德国 绿色 鱼 咖啡 Prince
瑞典 白色 狗 啤酒 BlueMaster
*/
/*
算法思路：
以房子的位置为主序，把国籍，颜色，宠物，饮料，香烟都作为该房子的一个成员，每一个成员都有可能
处在任何位置，为所有成员穷举每一个位置，再根据已知条件进行适当剪枝，找到唯一的解
*/
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int main(void)
{
string Title[5] = {"国籍","颜色","宠物","饮料","香烟"};
struct {
string nation;
string color;
string pet;
string drink;
string cigarette;
} House[5];//房子从左到右编号
House[0].nation = "挪威";//挪威人住在第一个房子里面
House[1].color = "蓝色";//挪威人和住在蓝房子的人相邻,即蓝房子是第2个房子
House[2].drink = "牛奶";// 住在中间那个房子里的人喝牛奶
for (int e=1; e<5; e++) //表示英国人的房子序号
for (int r=1; r<5; r++)//表示瑞典人的房子序号
for (int d=1; d<5; d++)//表示丹麦人的房子序号
for (int g=0; g<5; g++)//表示绿房子的序号
for (int p=0; p<5; p++)//表示抽Pall Mall牌香烟的人的房子序号
for (int y=0; y<5; y++)//表示黄色房子的序号
for (int b=0; b<5; b++)//表示喝啤酒人的房子序号
for (int h=0; h<5; h++)//表示养马的人的房子序号
for (int cat=0; cat<5; cat++)//表示养猫的人的房子序号
{
int Germany = 10 - 0 - e - r - d; //表示德国人的房子序号,德国人抽Prince牌香烟；
int Blends = 10 - p - y - b - Germany;//表示抽Blends牌香烟的人的房子序号
int white = 10 - 1 - e - g - y; //表示白房子的序号
int water = 10 - 2 - d - g - b; //表示喝矿泉水的人的房子序号
int fish = 10 - r - p - h - cat;//表示养鱼的人的房子序号
bool A1 = (e!=1); //英国人住在红色的房子里；根据房子和国家判断
bool A2 = (r!=e); //瑞典人养狗作为宠物；根据国家和宠物判断
bool A3 = (d!=e && d!=r && d!=2);//丹麦人喝茶；根据国家和饮料判断
bool A4 = (g!=1 && g!=2 && g!=e && g!=d);//绿房子的主人喝咖啡；根据颜色和饮料判断
bool A5 = (p!=r); //抽Pall Mall牌香烟的人养鸟；根据香烟和宠物判断
bool A6 = (y!=e && y!=1 && y!=g && y!=p);//黄色房子里的人抽Dunhill牌香烟；根据颜色和香烟判断
bool A7 = (b!=2 && b!=d && b!=g && b!=p && b!=y);//抽BlueMaster牌香烟的人喝啤酒；根据香烟和饮料判断
bool A8 = (h!=r && h!=p && (h==y+1 || h==y-1));//养马的人和抽Dunhill牌香烟的人相邻,根据香烟和宠物判断
bool A9 = (white == g + 1); //绿房子紧挨着白房子，在白房子的左边；
bool A0 = (cat==Blends-1 || cat==Blends+1);//Blends牌香烟的人和养猫的人相邻；
bool A11 = (water==Blends-1 || water==Blends+1);//抽Blends牌香烟的人和喝矿泉水的人相邻
if (A1 && A2 && A3 && A4 && A5 && A6 && A7 && A8 && A9 && A0 && A11)
{//把满足条件的序号填入结构数组
House[e].nation = "英国";
House[e].color = "红色";
House[r].nation = "瑞典";
House[r].pet = "狗";
House[d].nation = "丹麦";
House[d].drink = "茶";
House[g].color = "绿色";
House[g].drink = "咖啡";
House[p].cigarette = "Pall Mall";
House[p].pet = "鸟";
House[y].color = "黄色";
House[y].cigarette = "Dunhill";
House[b].cigarette = "BlueMaster";
House[b].drink = "啤酒";
House[h].pet = "马";
House[Germany].nation = "德国";
House[Germany].cigarette = "Prince";
House[Blends].cigarette = "Blends";
House[white].color = "白色";
House[water].drink = "矿泉水";
House[cat].pet = "猫";
House[fish].pet = "鱼";
goto end;
}
}
end:
for (int i=0; i<5; i++)
cout << Title[i] << "\t";
cout << endl << endl;
for (int i=0; i<5; i++)
{
cout << House[i].nation << "\t";
cout << House[i].color << "\t";
cout << House[i].pet << "\t";
cout << House[i].drink << "\t";
cout << House[i].cigarette << "\t";
cout << endl;
}
//输出到文件
ofstream out("爱因斯坦的思考题.txt");
for (int i=0; i<5; i++)
out << Title[i] << "\t";
out << endl << endl;
for (int i=0; i<5; i++)
{
out << House[i].nation << "\t";
out << House[i].color << "\t";
out << House[i].pet << "\t";
out << House[i].drink << "\t";
out << House[i].cigarette << "\t";
out << endl;
}
out.close();
system("pause");
return 0;
}
转http://www.programfan.com/ --------------------编程问答-------------------- 果然强～～ --------------------编程问答-------------------- 有时间再仔细看 --------------------编程问答-------------------- 顶你 --------------------编程问答-------------------- 穷举法就没什么技巧了 --------------------编程问答-------------------- 果然强～～ --------------------编程问答-------------------- 强，真强，太强了。
牛，真牛，太牛了。 --------------------编程问答-------------------- 不用剪,穷举就可以了。 --------------------编程问答-------------------- 太火星了 --------------------编程问答-------------------- 要顶 --------------------编程问答-------------------- 太火星了 --------------------编程问答-------------------- 穷举... --------------------编程问答-------------------- 爱因斯坦真是太爱因斯坦了。 --------------------编程问答-------------------- 这玩意想多了，会进大腕里的疯人院的 --------------------编程问答-------------------- 手算了一下，大约花掉40多分钟才找到结果。
ps:并不难，只要你画好表格......... --------------------编程问答-------------------- 估計愛因斯坦不懂c++
說明樓主比愛因斯坦還牛。 --------------------编程问答-------------------- 太火星了 --------------------编程问答-------------------- 又是这些烂题、、、、 --------------------编程问答-------------------- 我是那2%
哈哈,我周围好多2% --------------------编程问答-------------------- 当一回牛人路过~ --------------------编程问答-------------------- jf --------------------编程问答-------------------- 估計愛因斯坦不懂c++
說明樓主比愛因斯坦還牛。
--------------------编程问答-------------------- 据说愛因斯坦当年是用算盘算出来的 --------------------编程问答-------------------- mark --------------------编程问答-------------------- 这个问题其实看你怎么解决，用程序穷举估计一秒钟就有答案了，
要是自己画图推理估计要半个小时，
要是自己什么都没有就在那里想.......估计一般人一辈子也想不出来吧！
反正我是觉得不画图实在是比较难想的。
不知道爱因斯坦当初说这句话的意思是不是说让大家不要画图、不要写程序
什么的！ sigh。。。 --------------------编程问答-------------------- mark --------------------编程问答-------------------- 难道我是传说中的2% 一猜就对了。。。。。 --------------------编程问答-------------------- 原来爱因是个算命了 --------------------编程问答-------------------- 没有想象的那么难 手填表格ok 估计用穷举不是好算法 哪位高手开发一下新算法 --------------------编程问答-------------------- 果然强～～
--------------------编程问答-------------------- 爱因斯坦不懂C++
-----------------
我强烈同意，老家伙一天就整这玩意
难怪能搞出原子弹，太牛了
LZ，你比爱因斯坦强，呵呵
哪位老兄，给个更牛点的算法！！！ --------------------编程问答-------------------- 强。
大学的时候搞了一上午没有整出来 --------------------编程问答-------------------- 笔算了一下，20多分钟，也不是很难 --------------------编程问答-------------------- 编程题。 --------------------编程问答-------------------- 牛B --------------------编程问答-------------------- 顶 --------------------编程问答-------------------- 没有oo --------------------编程问答-------------------- 外形人！！！！！！！！！！！ --------------------编程问答-------------------- 爱兄能在没有计算机时代想出这个问题，的确属于非人类，强啊！ --------------------编程问答-------------------- nb --------------------编程问答-------------------- 爱因斯坦的意思是说。。。。
世界上有40%的人生活在贫困中，吃饭都不饱，哪有心思想这些问题～～～
剩下那60%的人里有一半不懂英文，看不明白他问的是什么，
于是剩下30%，
然后又有一半是婴幼儿和很老的老人，
于是剩下15%，里面有三分之二当时正在对抗希特勒和日本鬼子，
所以剩下5%，这里面又有四成的人对这个问题没兴趣，看都不想看。。。
于是剩下3%，又有写人看完问题就被女朋友（男朋友）拉去XXX了，没空思考～～～
于是剩下2%认真看这个问题并认真想了一段时间，终于想出来了～～ --------------------编程问答-------------------- 咱们大家都是那2%～～～ --------------------编程问答-------------------- 楼上强 --------------------编程问答-------------------- 爱因斯坦很聪明
但是他不会登录csdn 也解不了csdn上的很多问题
===============================================
DAY DAY UP --------------------编程问答-------------------- 难 --------------------编程问答-------------------- 强，太强了！ --------------------编程问答-------------------- 又是算。。。 闪 --------------------编程问答-------------------- #include <stdio.h>
#include <conio.h>
typedef enum {nBritish, nSweden, nDenmark, nNorway, nGermany} Nationality;
typedef enum {hcRed, hcGreen, hcWhite, hcYellow, hcBlue} HouseColor;
typedef enum {bTea, bCoffee, bMilk, bBeer, bWater} Beverage;
typedef enum {cPALLMALL, cDUNHILL, cBLUEMASTER, cPRINCE, cMIX} Cigarettes;
typedef enum {pDog, pBird, pCat, pHorse, pFish} Pets;
#define MAX_METHOD 120 // 5!
int main(int argc, char *argv)
{
int Method[MAX_METHOD][5];
int i;
int i0,i1,i2,i3,i4;
int (*Nat), (*Col), (*Bev), (*Cig), (*Pet);
int GreenPos, WhitePos;
i = 0;
for (i0 = 0; i0 < 5; ++i0)
{
for (i1 = 0; i1 < 5; ++i1)
{
if (i1 == i0) continue;
for (i2 = 0; i2 < 5; ++i2)
{
if ((i2 == i0) || (i2 == i1)) continue;
for (i3 = 0; i3 < 5; ++i3)
{
if ((i3 == i0) || (i3 == i1) || (i3 == i2)) continue;
for (i4 = 0; i4 < 5; ++i4)
{
if ((i4 == i0) || (i4 == i1) || (i4 == i2) || (i4 == i3)) continue;
Method[i][0] = i0;
Method[i][1] = i1;
Method[i][2] = i2;
Method[i][3] = i3;
Method[i][4] = i4;
++i;
}
}
}
}
}
for (Nat = Method[0], i0 = MAX_METHOD; i0 > 0; Nat += 5, --i0)
{
// Condition 9
if ((Nationality)(Nat[0]) != nNorway) continue;
for (Col = Method[0], i1 = MAX_METHOD; i1 > 0; Col += 5, --i1)
{
for (Bev = Method[0], i2 = MAX_METHOD; i2 > 0; Bev += 5, -- i2)
{
// Condition 8
if ((Beverage)(Bev[2]) != bMilk) continue;
for (Cig = Method[0], i3 = MAX_METHOD; i3 > 0; Cig += 5, --i3)
{
for (Pet = Method[0], i4 = MAX_METHOD; i4 > 0; Pet += 5, --i4)
{
GreenPos = 5;
WhitePos = 5;
for (i = 0; i < 5; ++i)
{
// Condition 1
if (((Nationality)(Nat[i]) == nBritish) && ((HouseColor)(Col[i]) != hcRed)) break;
if (((HouseColor)(Col[i]) == hcRed) && ((Nationality)(Nat[i]) != nBritish)) break;
// Condition 2
if (((Nationality)(Nat[i]) == nSweden) && ((Pets)(Pet[i]) != pDog)) break;
if (((Pets)(Pet[i]) == pDog) && ((Nationality)(Nat[i]) != nSweden)) break;
// Condition 3
if (((Nationality)(Nat[i]) == nDenmark) && ((Beverage)(Bev[i]) != bTea)) break;
if (((Beverage)(Bev[i]) == bTea) && ((Nationality)(Nat[i]) != nDenmark)) break;
// Condition 4
if ((HouseColor)(Col[i]) == hcGreen) GreenPos = i;
if ((HouseColor)(Col[i]) == hcWhite) WhitePos = i;
if (GreenPos > WhitePos) break;
// Condition 5
if (((HouseColor)(Col[i]) == hcGreen) && ((Beverage)(Bev[i]) != bCoffee)) break;
if (((Beverage)(Bev[i]) == bCoffee) && ((HouseColor)(Col[i]) != hcGreen)) break;
// Condition 6
if (((Cigarettes)(Cig[i]) == cPALLMALL) && ((Pets)(Pet[i]) != pBird)) break;
if (((Pets)(Pet[i]) == pBird) && ((Cigarettes)(Cig[i]) != cPALLMALL)) break;
// Condition 7
if (((HouseColor)(Col[i]) == hcYellow) && ((Cigarettes)(Cig[i]) != cDUNHILL)) break;
if (((Cigarettes)(Cig[i]) == cDUNHILL) && ((HouseColor)(Col[i]) != hcYellow)) break;
// Condition 10
if (((Cigarettes)(Cig[i]) == cMIX) && (!(((i - 1 >= 0) && ((Pets)(Pet[i - 1]) == pCat)) || ((i + 1 < 5) && ((Pets)(Pet[i + 1]) == pCat))))) break;
// Condition 11
if (((Pets)(Pet[i]) == pHorse) && (!(((i - 1 >= 0) && ((Cigarettes)(Cig[i - 1]) == cDUNHILL)) || ((i + 1 < 5) && ((Cigarettes)(Cig[i + 1]) == cDUNHILL))))) break;
// Condition 12
if (((Cigarettes)(Cig[i]) == cBLUEMASTER) && ((Beverage)(Bev[i]) != bBeer)) break;
if (((Beverage)(Bev[i]) == bBeer) && ((Cigarettes)(Cig[i]) != cBLUEMASTER)) break;
// Condition 13
if (((Nationality)(Nat[i]) == nGermany) && ((Cigarettes)(Cig[i]) != cPRINCE)) break;
if (((Cigarettes)(Cig[i]) == cPRINCE) && ((Nationality)(Nat[i]) != nGermany)) break;
// Condition 14
if (((Nationality)(Nat[i]) == nNorway) && (!(((i - 1 >= 0) && ((HouseColor)(Col[i - 1]) == hcBlue)) || ((i + 1 < 5) && ((HouseColor)(Col[i + 1]) == hcBlue))))) break;
// Condition 15
if (((Cigarettes)(Cig[i]) == cMIX) && (!(((i - 1 >= 0) && ((Beverage)(Bev[i - 1]) == bWater)) || ((i + 1 < 5) && ((Beverage)(Bev[i + 1]) == bWater))))) break;
}
if (i == 5)
{
printf("%d %d %d %d %d\n", Nat[0], Nat[1], Nat[2], Nat[3], Nat[4]);
printf("%d %d %d %d %d\n", Col[0], Col[1], Col[2], Col[3], Col[4]);
printf("%d %d %d %d %d\n", Bev[0], Bev[1], Bev[2], Bev[3], Bev[4]);
printf("%d %d %d %d %d\n", Cig[0], Cig[1], Cig[2], Cig[3], Cig[4]);
printf("%d %d %d %d %d\n\n", Pet[0], Pet[1], Pet[2], Pet[3], Pet[4]);
}
}
}
}
}
}
return 0;
}
Result:
3 2 0 4 1
3 4 0 1 2
4 0 2 1 3
1 4 0 3 2
2 3 1 4 0
3 4 0 2 1
1 4 0 3 2
1 4 2 0 3
0 3 4 1 2
1 2 3 4 0
3 4 0 2 1
1 4 0 3 2
1 4 2 0 3
0 3 4 1 2
1 4 3 2 0
3 4 1 0 2
1 4 2 0 3
1 4 2 3 0
0 3 4 2 1
1 2 0 3 4
3 4 1 0 2
1 4 3 0 2
1 4 2 3 0
4 3 1 2 0
4 2 0 3 1
3 4 1 2 0
1 4 2 3 0
1 4 2 0 3
0 3 4 1 2
1 2 0 4 3
3 4 1 2 0
1 4 2 3 0
1 4 2 0 3
0 3 4 1 2
1 4 0 2 3
--------------------编程问答-------------------- up --------------------编程问答-------------------- 不错
收藏 --------------------编程问答-------------------- 条件太多,这个题目不好玩.
穷举就可以了. --------------------编程问答-------------------- $ --------------------编程问答-------------------- 爱因斯坦不懂C++
-----------------
我强烈同意，老家伙一天就整这玩意
难怪能搞出原子弹，太牛了
LZ，你比爱因斯坦强，呵呵
哪位老兄，给个更牛点的算法！！！
爱因斯坦搞过原子弹!!!!!!! --------------------编程问答-------------------- 这题做过, 根本不需要上程序, 自己排排就出来了.
再说了, 2%也算不得什么了不起的, IQ大概在135. 老爱的智商, 大概也在150以上, 恐怕都千分之一了.
我的那些题目, http://blog.csdn.net/Kakrat/archive/2007/08/05/1727271.aspx, 比这题有意思, 难度范围也大.
--------------------编程问答-------------------- 其实真的不难 --------------------编程问答-------------------- i服了u --------------------编程问答-------------------- qiang --------------------编程问答-------------------- 有么有c#的 --------------------编程问答-------------------- 强 --------------------编程问答-------------------- mark --------------------编程问答-------------------- 果然强～～ --------------------编程问答-------------------- mark~~~~ --------------------编程问答-------------------- 9.14.8.5.4.1.7.11.12.3.2.13.6.15.10用这个序号看条件，马上解决 --------------------编程问答--------------------
楼主是旷世奇才呀,怎么没被用人组织发掘呢?多好的苗子,就这么白瞎了.
--------------------编程问答-------------------- 看的我脑壳痛。 --------------------编程问答-------------------- 2%也有一个亿了 --------------------编程问答-------------------- 很就以前就听说这个问题，不过我没答出来 --------------------编程问答-------------------- 呵呵，来看看啊。 --------------------编程问答--------------------
--------------------编程问答--------------------
我告诉你们把，爱因斯坦就是个大骗子，他说吗就是嘛，大家都爱跟着她的逻辑思维走补充：.NET技术 , 非技术区
