前提：1、有5栋5种颜色的房子
2、每一位房子的主人国籍都不同
3、这5个人每人只喝一个牌子的饮料，只抽一个牌子的香烟，只养一种宠物。
4、没有人有相同的宠物，抽相同的牌子的香烟，喝相同的饮料。
提示： 1、英国人住在红房子里
2、瑞典人养了一条狗
3、丹麦人喝茶
4、绿房子在白房子的左边
5、绿房子主人喝咖啡
6、抽PALL MALL烟的人养了一只鸟
7、黄房子主人抽DUNHILL烟
8、住在中间的那间房子的人喝牛奶
9、挪威人住在第一间房子
10、抽混合烟的人住在养猫的旁边
11、养马人住在抽DUNHILL烟的人旁边
12、抽BLUE MASTER烟的人喝啤酒
13、德国人抽PRING烟
14、挪威人住在蓝房子旁边
15、抽混合烟的人的邻居喝矿泉水。
问题： 谁养鱼？
但我始终会被那复杂的关系敲晕脑袋.今天再次提起^^^^^^^^^^^^^^^^^^^^
网上能找到的最多的解,共三种.
来源:http://blog.chinaunix.net/u/27166/showart_363983.html
解法：
F(n) 1 n>8 n Drink 1 2 3 4 5
烟：PM、DH、BM、PR、混=> Tobacco 1 2 3 4 5
宠物：狗、鸟、马、猫、鱼=> Pet 1 2 3 4 5
然后有：
9=>N1=挪威
14=>C2=蓝
4=>如C3=绿，C4=白，则(8)和(5)矛盾，所以C4=绿，C5=白
剩下红黄只能为C1，C3
1=>C3=红，N3=英国，C1=黄
8=>D3=牛奶
5=>D4=咖啡
7=>T1=DH
11=>P2=马
那么：
挪威 ？ 英国 ？ ？
黄 蓝 红 绿 白
？ ？ 牛奶 咖啡 ？
DH ？ ？ ？ ？
？ 马 ？ ？ ？
12=>啤酒只能为D2或D5，BM只能为T2或T5=>D1=矿泉水
3=>茶只能为D2或D5，丹麦只能为N2或N5
15=>T2=混合烟=>BM=T5，
所以剩下啤酒=D5，茶=T2=>丹麦=D2
然后：
挪威 丹麦 英国 ？ ？
黄 蓝 红 绿 白
矿泉水 茶 牛奶 咖啡 啤酒
DH 混合烟 ？ ？ BM
？ 马 ？ ？ ？
13=>德国=N4，PR=T4
所以，瑞典=N5，PM=T3
2=>狗=P5
6=>鸟=P3
10=>猫=P1
得到：
挪威 丹麦 英国 德国 瑞典
黄 蓝 红 绿 白
矿泉水 茶 牛奶 咖啡 啤酒
DH 混合烟 PM PR BM
猫 马 鸟 ？ 狗
所以，最后剩下的鱼只能由德国人养了。
有3个答案
1:德国人养鱼(2种)
1 2 3 4 5
挪 丹 英 德 瑞
黄 蓝 红 绿 白
水 茶 牛奶 咖 啤酒
dun ble pal pri blu
猫 马 鸟 鱼 狗
1 2 3 4 5
挪 德 瑞 丹 英
绿 蓝 白 黄 红
咖啡 水 牛奶 茶 啤酒
pal pri ble dun blu
鸟 鱼 狗 猫 马
2:挪威人养鱼
1 2 3 4 5
挪 德 瑞 英 丹
绿 蓝 黄 红 白
咖啡 水 牛奶 啤酒 茶
ble pri dun blu pal
鱼 猫 狗 马 鸟
3:丹麦人养鱼
1 2 3 4 5
挪 德 瑞 丹 英
绿 蓝 白 黄 红
咖啡 水 牛奶 茶 啤酒
pal pri ble dun blu
鸟 猫 狗 鱼 马
答案对了,其实还有更多的组合^^^^^^^^^^^^^^^^^^^^
头脑发热的题,丢给计算机来解决吧.
我用Digital Mars C编译成功,算法不算好吧.
#include
char*COL[]={NULL,"红","黄","绿","蓝","白"};
char*PAD[]={NULL,"狗","猫","鱼","鸟","马"};
char*DRK[]={NULL,"茶 ","牛奶","咖啡","啤酒","水 "};
char*GUO[]={NULL,"挪威","英国","德国","丹麦","瑞典"};
char*SMK[]={NULL,"Blends","BlueMaster","Dunhill","Pall Mall","Prince"};
struct{ char guojia, color, pads, drink, smoke; } aa[5];
char color[4]={1,2,3,5};
char drink[4]={1,3,4,5};
char guojia[4]={2,3,4,5};
char smoke[]={1,2,3,4,5};
char pads[5]={1,2,3,4,5};
int main()
{ int i,j,k,ans=0;
int i1,i2,i3,i4,i5;
aa[1].color=4;
aa[2].drink=2;
aa[0].guojia=1;
for(i1=0;i1<24;i1++){
aa[0].color=color[0];
aa[2].color=color[1];
aa[3].color=color[2];
aa[4].color=color[3];
rot(color,4);
for(i2=0;i2<24;i2++){
aa[0].drink=drink[0];
aa[1].drink=drink[1];
aa[3].drink=drink[2];
aa[4].drink=drink[3];
rot(drink,4);
for(i3=0;i3<24;i3++){
aa[1].guojia=guojia[0];
aa[2].guojia=guojia[1];
aa[3].guojia=guojia[2];
aa[4].guojia=guojia[3];
rot(guojia,4);
for(i4=0;i4<120;i4++){
for(i=0;i<5;i++)
aa[i].smoke=smoke[i];
rot(smoke,5);
for(i5=0;i5<120;i5++){
for(j=0;j<5;j++)
aa[j].pads=pads[j];
rot(pads,5);
if(OK()){
printf("---------------------第%d种解---------------------\n",++ans);
for(k=0;k<5;k++)
printf("第%d户: %s人 %s房子 养%s 喝%s 抽%s\n",k+1,GUO[aa[k].guojia],
COL[aa[k].color],PAD[aa[k].pads],DRK[aa[k].drink],SMK[aa[k].smoke]);
}}}}}}
return 0;
}
int OK(void)
{
int i,j;
for(i=0;i<5;i++)
if(aa[i].guojia==2 && aa[i].color==1)goto next1;
return 0;
next1:
for(i=0;i<5;i++)
if(aa[i].guojia==5 && aa[i].pads==1)goto next2;
return 0;
next2:
for(i=0;i<5;i++)
if(aa[i].guojia==4 && aa[i].drink==1)goto next3;
return 0;
next3:
for(i=0;i<5;i++)
if(aa[i].color==3)goto next3_1;
return 0;
next3_1:
for(j=i+1;j<5;j++)
if(aa[j].color==5)goto next4;
return 0;
next4:
for(i=0;i<5;i++)
if(aa[i].color==3 && aa[i].drink==3)goto next5;
return 0;
next5:
for(i=0;i<5;i++)
if(aa[i].smoke==4 && aa[i].pads==4)goto next6;
return 0;
next6:
for(i=0;i<5;i++)
if(aa[i].color==2 && aa[i].smoke==3)goto next7;
return 0;
next7:
for(i=0;i<5;i++)
if(aa[i].guojia==3 && aa[i].smoke==5)goto next10;
return 0;
next10:
for(i=0;i<5;i++)
if(aa[i].smoke==2 && aa[i].drink==4)goto next11;
return 0;
next11:
for(i=0;i<5;i++)
if(aa[i].smoke==3)goto next12_1;
next12_1:
if(i==0){if(aa[1].pads==5)goto next13;}
else if(i==4){if(aa[3].pads==5)goto next13;}
else if(aa[i-1].pads==5||aa[i+1].pads==5)goto next13;
return 0;
next13:
for(i=0;i<5;i++)
if(aa[i].smoke==1)goto next13_1;
next13_1:
if(i==0){if(aa[1].pads==2)goto next14;}
else if(i==4){if(aa[3].pads==2)goto next14;}
else if(aa[i-1].pads==2||aa[i+1].pads==2)goto next14;
return 0;
next14:
for(i=0;i<5;i++)
if(aa[i].smoke==1)goto next14_1;
next14_1:
if(i==0){if(aa[1].drink==5)goto next15;}
else if(i==4){if(aa[3].drink==5)goto next15;}
else if(aa[i-1].drink==5||aa[i+1].drink==5)goto next15;
return 0;
next15:
return 1;
}
int rot(char a[],int n)
{ int i,j,k,t;
for(k=n-1;k>0;k--)
if(a[k-1]if(k==0)
{ for(i=0,j=n-1;i{char t=a[i];
a[i]=a[j];
a[j]=t;
}
return 0;
}
t=a[k-1];i=k;
for(j=k+1;jif(ta[k-1]=a[i];a[i]=t;
for(i=k;ifor(j=k;jif(a[j]>a[j+1])
{ t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
return 1;
}
阅读(825) | 评论(0) | 转发(0) |
