主题:[原创]编程解爱因斯坦难题正式版
if007
[专家分:650] 发布于 2006-04-21 22:23:00
/*************************************************************
简介:
传说下面是爱因斯坦在20世纪初出的一道测试题。他说世界上有99%的人回答不出这道题,
看看你是否属于另外的1%?题目如下:
前提:
1 有五栋五种颜色的房子
2 每一位房子的主人国籍都不同
3 这五个人每人只喝一种饮料,只抽一种牌子的香烟,只养一种宠物
4 没有人有相同的宠物,抽相同牌子的香烟,喝相同的饮料
条件:
1 英国人住在红房子里
2 瑞典人养了一条狗
3 丹麦人喝茶
4 绿房子在白房子左边
5 绿房子主人喝咖啡
6 抽PALL MALL烟的人养了一只鸟
7 黄房子主人抽DUNHILL烟
8 住在中间那间房子的人喝牛奶
9 挪威人住第一间房子
10 抽BLENDS烟的人住在养猫人的旁边
11 养马人住在DUNHILL烟的人旁边
12 抽BLUE MASTER烟的人喝啤酒
13 德国人抽PRINCE烟
14 挪威人住在蓝房子旁边
15 抽BLENDS烟的人的邻居喝矿泉水
问题:谁养鱼?
**************************************************************/
/*=============================================================
文件描述: 解养鱼问题
创建人: 陈泽丹 ,2006-4-20, QQ:82314038
文件号: 2
修改次数:
=============================================================*/
/*------------------------------------------------------------
算法描述:
(图是任意选定的)
--------------------------------
下标(国籍):0 1 2 3 4
对应(国籍):英 瑞 挪 德 丹
--------------------------------
数组值: 0 1 2 3 4
对应(房号) 0 1 2 3 4
对应(房色) 红 白 黄 蓝 绿
对应(宠物) 狗 马 鸟 猫 鱼
对应(饮料) 咖 茶 奶 水 酒
对应(香烟) pal dun blu pri ble
---------------------------------
依照上表,以人为线索(下标),排列人的属性的各种组合,符合题目条
件者,最后输出结果。
--------------------------------------------------------------*/
回复列表 (共31个回复)
沙发
if007 [专家分:650] 发布于 2006-04-21 15:26:00
#include <iostream.h>
const int len=5;
const int Max=120;
int number[len]={0,1,2,3,4};
int M[Max][len];
int p=0;
int home[len],drink[len],cigarette[len],pet[len],color[len];
int cd1()
{ //英国人住红房
return color[0] !=0;
}
int cd2()
{ //瑞士人养狗
return pet[1] !=0;
}
int cd3()
{ //丹麦人喝茶
return drink[4] != 1;
}
int cd4()
{ //绿房在白房左边
for (int i=0; i<len; i++)
{ if (color[i] == 4) break; }
for (int j=0; j<len; j++)
{ if (color[j] == 1) break; }
int b=0;
if (home[i] != home[j]-1 ) b=1;
return b;
}
int cd5()
{ //绿房人喝咖啡
for (int i=0; i<len; i++)
{ if (color[i] == 4) break; }
return drink[i] != 0;
}
int cd6()
{ //抽pall Mall人养鸟
for (int i=0; i<len; i++)
{ if ( cigarette[i] == 0) break; }
return pet[i] !=2;
}
int cd7()
{ //黄房人抽dunhill烟
for (int i=0; i<len; i++)
{ if ( color[i] == 2) break; }
return cigarette[i] != 1;
}
int cd8()
{ //中间屋主喝牛奶
for (int i=0; i<len; i++)
{ if (home[i] == 2) break; }
return drink[i] != 2;
}
int cd9()
{ //挪威人住第一间
return home[2] != 0;
}
int cd10()
{ //抽blend人住养猫人隔壁
for (int i=0; i<len; i++)
{ if ( cigarette[i] == 4) break; }
for (int j=0; j<len; j++)
{ if ( pet[j] == 3 ) break; }
int b=0;
if ( (home[i] != home[j]+1) && (home[i] != home[j]-1) ) b=1;
return b;
}
int cd11()
{ //抽Dunhill人住养马人隔壁
for (int i=0; i<len; i++)
{ if (cigarette[i] == 1) break; }
for (int j=0; j<len; j++)
{ if (pet[j] == 1) break; }
int b=0;
if (home[i]!=home[j]+1 && home[i]!=home[j]-1) b=1;
return b;
}
int cd12()
{ //抽blue Master人喝酒
for (int i=0; i<len; i++)
{ if (cigarette[i] == 2) break; }
return drink[i] != 4 ;
}
int cd13()
{ //德国人抽prince
return cigarette[3] != 3 ;
}
int cd14()
{ //挪威人住蓝房旁边
int b=0;
for (int i=0; i<len; i++)
{ if (color[i] == 3) break; }
if (home[2] != home[i]+1 && home[2] != home[i]-1) b=1;
return b;
}
int cd15()
{ //抽blend的喝开水的隔壁
for (int i=0; i<len; i++)
{ if (cigarette[i] == 4) break; }
for (int j=0; j<len; j++)
{ if (drink[j] == 3) break; }
int b=0;
if (home[i]!=home[j]+1 && home[i]!=home[j]-1) b=1;
return b;
}
void order(int n)
{ //求五个元素的任意组合情况
int i,temp;
if(n==len)
{
for (i=0; i<len; i++)
M[p][i]=number[i];
p++;
}
else
for(i=n; i<len; i++)
{
temp = number[i]; number[i] = number[n]; number[n] = temp;
order(n+1);
temp = number[i]; number[i] = number[n]; number[n] = temp;
}
}
板凳
if007 [专家分:650] 发布于 2006-04-21 15:26:00
void output()
{ //测试排列情况
int i, j;
for(i=0; i<Max; i++)
{
for (j=0; j<len; j++)
cout<<M[i][j];
cout<<endl;
}
}
void answer(int(* M)[len])
{ //求解
int i;
//求房间号组合
for (int a=0; a<Max; a++)
{
for (i=0; i<len; i++)
home[i]=M[a][i];
if ( cd9()) continue; //9,挪威人住第一间房
//求宠物组合(已知前提:房间号组合)
for (int b=0; b<Max; b++)
{
for (i=0; i<len; i++)
pet[i]=M[b][i];
if ( cd2()) continue; //2,瑞士人养狗
//求饮料组合(已知前提:房间号组合,宠物组合)
for (int c=0; c<Max; c++)
{
for (i=0; i<len; i++)
drink[i]=M[c][i];
if ( cd3()) continue; //3,丹麦人喝茶
if ( cd8()) continue; //8, 中间屋主喝牛奶
//求香烟组合(已知前提:房间号组合,宠物组合,饮料组合)
for (int d=0; d<Max; d++)
{
for (i=0; i<len; i++)
cigarette[i]=M[d][i];
/*就是这里原先打成cigarette[i]=M[d][len];运行结果让俺大吃一惊,不过百折不挠的检查后还是让俺发现了它的老窝,哈*/
if ( cd6()) continue; //6,抽屉pall Mall人养鸟
if ( cd10()) continue; //10,抽blend人住养猫人隔壁
if ( cd11()) continue; //11,养马人在抽dunhill人隔壁
if ( cd12()) continue; //12,抽blue master人喝酒
if ( cd13()) continue; //13,德抽prince香烟
if ( cd15()) continue; //15,喝开水人住抽blend烟人隔壁
//求房间色彩组合(已知前提:房间号组合,宠物组合,饮料组合,香烟组合)
for (int e=0; e<Max; e++)
{
for (i=0; i<len; i++)
color[i]=M[e][i];
if ( cd1()) continue; //1,英国人住红房子
if ( cd4()) continue; //4,绿房在白房左边
if ( cd5()) continue; //5,绿房的喝咖啡
if ( cd7()) continue; //7,黄房子人抽dunhill烟
if ( cd14())continue; //14,挪威人住蓝房旁边
for (i=0; i<len; i++)
{
if (pet[i]==4)
cout<<"养鱼人"<<i<<endl;
}
}
}
}
}
}
}
void main()
{
order(0);
output();
answer(M);
}
3 楼
if007 [专家分:650] 发布于 2006-04-21 15:31:00
实在汗颜.
这是我第二次做这题了.第一次做时以房子号为线索编程解出过.
前几天又见这曾在我上一年刚学C++时折磨了我不少时间的题,就想着再解一次,不过这次我换了以人物国籍为线索.
原想很容易就出的...没想到第二次解这题时反解不出了...
呵呵,汗颜,汗颜...(倒霉的是,上次重装电脑时把俺的程序又全被弄掉了,想看下以前的记录也没法了.)
而且我还找不出错在那,可能当局者迷.
请高手来找错啊. ^_^。
4 楼
if007 [专家分:650] 发布于 2006-04-21 22:15:00
晕,最后还是靠自已找出了错误哈.
修改地方有三:
1.//绿房在白房左边
第一版时理解成只要是左边就行,而不是邻近的左边.结果出了好些答案.
2.//挪威人住蓝房旁边
纯属代码打错.
3.//cigarette[i]=M[d][len];
纯属代码打错.
哈,已对原版作了修改,可以正常运行出结果了.
以下是正式版.
5 楼
if007 [专家分:650] 发布于 2006-04-21 22:19:00
/*************************************************************
简介:
传说下面是爱因斯坦在20世纪初出的一道测试题。他说世界上有99%的人回答不出这道题,
看看你是否属于另外的1%?题目如下:
前提:
1 有五栋五种颜色的房子
2 每一位房子的主人国籍都不同
3 这五个人每人只喝一种饮料,只抽一种牌子的香烟,只养一种宠物
4 没有人有相同的宠物,抽相同牌子的香烟,喝相同的饮料
条件:
1 英国人住在红房子里
2 瑞典人养了一条狗
3 丹麦人喝茶
4 绿房子在白房子左边
5 绿房子主人喝咖啡
6 抽PALL MALL烟的人养了一只鸟
7 黄房子主人抽DUNHILL烟
8 住在中间那间房子的人喝牛奶
9 挪威人住第一间房子
10 抽BLENDS烟的人住在养猫人的旁边
11 养马人住在DUNHILL烟的人旁边
12 抽BLUE MASTER烟的人喝啤酒
13 德国人抽PRINCE烟
14 挪威人住在蓝房子旁边
15 抽BLENDS烟的人的邻居喝矿泉水
问题:谁养鱼?
**************************************************************/
/*=============================================================
文件描述: 解养鱼问题
创建人: 陈泽丹 (2006-4-21 , QQ:82314038)
文件号: 2.5
修改次数:
=============================================================*/
/*------------------------------------------------------------
算法描述:
(表任意选定)
--------------------------------
下标(国籍):0 1 2 3 4
对应(国籍):英 瑞 挪 德 丹
--------------------------------
数组值: 0 1 2 3 4
对应(房号) 0 1 2 3 4
对应(房色) 红 白 黄 蓝 绿
对应(宠物) 狗 马 鸟 猫 鱼
对应(饮料) 咖 茶 奶 水 酒
对应(香烟) pal dun blu pri ble
---------------------------------
依照上表,以人为线索(下标),排列人的属性的各种组合,符合题目条
件者,最后输出结果。
--------------------------------------------------------------*/
6 楼
if007 [专家分:650] 发布于 2006-04-21 22:20:00
#include <iostream.h>
#include <iomanip.h>
const int len=5;
const int Max=120;
int number[len]={0,1,2,3,4};
int M[Max][len];
int p=0;
int home[len],drink[len],cigarette[len],pet[len],color[len];
int cd1()
{ //英国人住红房
return color[0] !=0;
}
int cd2()
{ //瑞士人养狗
return pet[1] !=0;
}
int cd3()
{ //丹麦人喝茶
return drink[4] != 1;
}
int cd4()
{ //绿房在白房左边
for (int i=0; i<len; i++)
{ if (color[i] == 4) break; }
for (int j=0; j<len; j++)
{ if (color[j] == 1) break; }
int b=0;
if (home[i] != home[j]-1 ) b=1;
return b;
}
int cd5()
{ //绿房人喝咖啡
for (int i=0; i<len; i++)
{ if (color[i] == 4) break; }
return drink[i] != 0;
}
int cd6()
{ //抽pall Mall人养鸟
for (int i=0; i<len; i++)
{ if ( cigarette[i] == 0) break; }
return pet[i] !=2;
}
int cd7()
{ //黄房人抽dunhill烟
for (int i=0; i<len; i++)
{ if ( color[i] == 2) break; }
return cigarette[i] != 1;
}
int cd8()
{ //中间屋主喝牛奶
for (int i=0; i<len; i++)
{ if (home[i] == 2) break; }
return drink[i] != 2;
}
int cd9()
{ //挪威人住第一间
return home[2] != 0;
}
int cd10()
{ //抽blend人住养猫人隔壁
for (int i=0; i<len; i++)
{ if ( cigarette[i] == 4) break; }
for (int j=0; j<len; j++)
{ if ( pet[j] == 3 ) break; }
int b=0;
if ( (home[i] != home[j]+1) && (home[i] != home[j]-1) ) b=1;
return b;
}
int cd11()
{ //抽Dunhill人住养马人隔壁
for (int i=0; i<len; i++)
{ if (cigarette[i] == 1) break; }
for (int j=0; j<len; j++)
{ if (pet[j] == 1) break; }
int b=0;
if (home[i]!=home[j]+1 && home[i]!=home[j]-1) b=1;
return b;
}
int cd12()
{ //抽blue Master人喝酒
for (int i=0; i<len; i++)
{ if (cigarette[i] == 2) break; }
return drink[i] != 4 ;
}
int cd13()
{ //德国人抽prince
return cigarette[3] != 3 ;
}
int cd14()
{ //挪威人住蓝房旁边
int b=0;
for (int i=0; i<len; i++)
if (color[i] == 3) break;
if (home[2] != home[i]+1 && home[2] != home[i]-1) b=1;
return b;
}
int cd15()
{ //抽blend的邻居喝开水
for (int i=0; i<len; i++)
{ if (cigarette[i] == 4) break; }
for (int j=0; j<len; j++)
{ if (drink[j] == 3) break; }
int b=0;
if (home[i]!=home[j]+1 && home[i]!=home[j]-1) b=1;
return b;
}
7 楼
if007 [专家分:650] 发布于 2006-04-21 22:21:00
void order(int n)
{ //求五个元素的任意组合情况
int i,temp;
if(n==len)
{
for (i=0; i<len; i++)
M[p][i]=number[i];
p++;
}
else
for(i=n; i<len; i++)
{
temp = number[i]; number[i] = number[n]; number[n] = temp;
order(n+1);
temp = number[i]; number[i] = number[n]; number[n] = temp;
}
}
void display(int n, int h, int c, int p, int d, int ce)
{
char *pn[5]={"英国人","瑞士人","挪威人","德国人","丹麦人"};
char *ph[5]={"1号房","2号房","3号房","4号房","5号房"};
char *pc[5]={"红色","白色","黄色","蓝色","绿色"};
char *pp[5]={"狗","马","鸟","猫","鱼"};
char *pd[5]={"咖啡","茶","牛奶","水","酒"};
char *pce[5]={"PALL MALL烟","DUNHILL烟","BLUE MASTER烟","PRINCE烟","BLENDS烟"};
cout<<setw(6)<<*(pn+n)<<"住"<<*(pc+c)<<"的"<<*(ph+h)<<",";
cout<<setw(8)<<"抽"<<setw(15)<<*(pce+ce)<<",";
cout<<setw(10)<<"爱喝"<<setw(4)<<*(pd+d)<<",";
cout<<setw(8)<<"养"<<*(pp+p)<<".";
}
void answer(int(* M)[len])
{ //求解
int i;
//求房间号组合
for (int a=0; a<Max; a++)
{
for (i=0; i<len; i++)
home[i]=M[a][i];
if ( cd9()) continue; //9,挪威人住第一间房
//求宠物组合(已知前提:房间号组合)
for (int b=0; b<Max; b++)
{
for (i=0; i<len; i++)
pet[i]=M[b][i];
if ( cd2()) continue; //2,瑞士人养狗
//求饮料组合(已知前提:房间号组合,宠物组合)
for (int c=0; c<Max; c++)
{
for (i=0; i<len; i++)
drink[i]=M[c][i];
if ( cd3()) continue; //3,丹麦人喝茶
if ( cd8()) continue; //8, 中间屋主喝牛奶
//求香烟组合(已知前提:房间号组合,宠物组合,饮料组合)
for (int d=0; d<Max; d++)
{
for (i=0; i<len; i++)
cigarette[i]=M[d][i];
if ( cd6()) continue; //6,抽屉pall Mall人养鸟
if ( cd10()) continue; //10,抽blend人住养猫人隔壁
if ( cd11()) continue; //11,养马人在抽dunhill人隔壁
if ( cd12()) continue; //12,抽blue master人喝酒
if ( cd13()) continue; //13,德抽prince香烟
if ( cd15()) continue; //15,喝开水人住抽blend烟人隔壁
//求房间色彩组合(已知前提:房间号组合,宠物组合,饮料组合,香烟组合)
for (int e=0; e<Max; e++)
{
for (i=0; i<len; i++)
color[i]=M[e][i];
if ( cd1()) continue; //1,英国人住红房子
if ( cd4()) continue; //4,绿房在白房左边
if ( cd5()) continue; //5,绿房的喝咖啡
if ( cd7()) continue; //7,黄房子人抽dunhill烟
if ( cd14())continue; //14,挪威人住蓝房旁边
for (i=0; i<len; i++)
{
display(i,home[i],color[i],pet[i],drink[i],cigarette[i]);
cout<<endl;
}
cout<<endl;
}
}
}
}
}
}
void main()
{
order(0);
answer(M);
}
8 楼
木木丛林 [专家分:4030] 发布于 2006-04-21 22:26:00
高中用逻辑我们全班大部分都做出来了.不是99%,是98%的人答不出来.
9 楼
if007 [专家分:650] 发布于 2006-04-21 22:34:00
你说得对,这题说有那么多人解不了确实是很夸张了.
人工解答很快就可以出答案.
哈,编编程序锻炼一下身手也不错,能锻炼一下把推理化成计算机语言的能力.
10 楼
mingzhentanq [专家分:60] 发布于 2006-04-30 16:13:00
不错不错! 我问一下楼主,你第一次大概用多少时间来编?
我来回复