|
锁定老帖子 主题：一道应聘智力题的编程求解
精华帖 (0) :: 良好帖 (9) :: 新手帖 (0) :: 隐藏帖 (0)
|
|||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 作者 | 正文 | ||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
最怕碰到这样的题目，我开始想到的解法就是便利所有可能，但却是数据量太大了
|
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
有两种答案，直接推理就好了！
|
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
gaoqs1984 写道 离散数学里讲过这样的，是太多判断了，以前是这个解的好像
A->B C->!D B->!C ==>B->D A推理出B，C推理出，不是D B推出不是C 那么B推出C 对对，就是离散数学讲的。 
|
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
kevindude 写道
请编程解决如下难题:
遇到这样的题目，一般思路是遍历所有可能，再根据给出的条件约束一一排除，最后得到正确结果。但是如果仔细算一下就会发现直接遍历的方法不可取，因为根据排列组合的公式算一下如果不排除任何约束条件大约有40亿（40^6=40亿，高中学的公式，不一定记的准确）种可能，显然直接遍历的话肯定会溢出（没测试过），所以正确的方法是首先排除掉一些可能，使遍历的长度尽可能的小。
仔细观察题目给出的条件，我个人认为可以分为两类：
第一类： 1、英国人住在红房子里 6、抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟 7、黄房子主人抽ＤＵＮＨＩＬＬ烟 8、住在中间那间房子的人喝牛奶 9、挪威人住第一间房子 13、德国人抽ＰＲＩＮＣＥ烟
第二类： 4、绿房子在白房子左边 10、抽混合烟的人住在养猫人的旁边 14、挪威人住在蓝房子旁边
如果我们画一张二维图表的话，第一类的约束条件可以直接反映出来，而第二类无法直接反映，需要间接推理。
这里具体的推理就不列出来了，相信大部分的朋友应该都能看的明白。这样一来，图表里的每一列的可能性分别降低到了25、21、33、14、33种，但是如果不去除重复的项，经过排列组合后所有的可能性仍旧高达超过800万种，所以在具体编程计算中，还要去掉重复的项。去掉重复的项后可能性聚降到只有1000多种，这个时候我们就可以用程序来遍历了。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class Caculate {
//英国0 瑞典1 丹麦2 挪威3 德国4
//红色0 绿色1 白色2 蓝色3 黄色4
//鸟0 狗1 猫2 鱼3 马4
//咖啡0 牛奶1 啤酒2 茶3 水4
//Price0 Pall Mall1 Blue2 Dunhill3 混合型4
public static List makeList(){
List list = new ArrayList();
for (int i=0; i<5; i++ ){
for (int j=0; j<5; j++){
for (int k=0; k<5; k++){
for (int p=0; p<5; p++){
for (int q=0; q<5; q++){
for (int r=0; r<5; r++){
int[] lt = new int[6];
lt[0]=i; //国籍
lt[1]=j; //颜色
lt[2]=k; //宠物
lt[3]=p; //饮料
lt[4]=q; //香烟
lt[5]=r; //位置
list.add(lt);
}
}
}
}
}
}
return list;
}
public static List caculateUK(){
//英国
List UK = makeList();
Iterator iterator = UK.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();
//英国人
if (item[0]!=0){
iterator.remove();
continue;
}
//住红房子
if (item[1]!=0){
iterator.remove();
continue;
}
//不养狗
if (item[2] == 1){
iterator.remove();
continue;
}
//不和咖啡和茶
if (item[3] == 0 || item[3] == 3){
iterator.remove();
continue;
}
//不抽Price烟
if (item[4] == 0){
iterator.remove();
continue;
}
//不住第一间
if (item[5] == 0){
iterator.remove();
continue;
}
//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 && item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 && item[2]!=0){
iterator.remove();
continue;
}
//抽ＢＬＵＥ ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 && item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 && item[4]!= 2){
iterator.remove();
continue;
}
//绿房子主人喝咖啡
if (item[3] == 0 && item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 && item[3]!= 0){
iterator.remove();
continue;
}
//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 && item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 && item[4]!= 3){
iterator.remove();
continue;
}
//住在中间那间房子的人喝牛奶
if (item[3] == 1 && item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 && item[3]!=1){
iterator.remove();
continue;
}
}
System.out.println(UK.size());
return UK;
}
public static List caculateSD(){
//瑞典
List SD = makeList();
Iterator iterator = SD.iterator();
iterator = SD.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();
//瑞典人
if (item[0]!=1){
iterator.remove();
continue;
}
//养狗
if (item[2]!= 1){
iterator.remove();
continue;
}
//不喝茶
if (item[3] == 3){
iterator.remove();
continue;
}
//不住红房子
if (item[1] == 0){
iterator.remove();
continue;
}
//不抽Price烟和Pall Mall烟
if (item[4] == 0 || item[4] == 1){
iterator.remove();
continue;
}
//不住第一间
if (item[5] == 0){
iterator.remove();
continue;
}
//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 && item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 && item[2]!=0){
iterator.remove();
continue;
}
//抽ＢＬＵＥ ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 && item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 && item[4]!= 2){
iterator.remove();
continue;
}
//绿房子主人喝咖啡
if (item[3] == 0 && item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 && item[3]!= 0){
iterator.remove();
continue;
}
//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 && item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 && item[4]!= 3){
iterator.remove();
continue;
}
//住在中间那间房子的人喝牛奶
if (item[3] == 1 && item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 && item[3]!=1){
iterator.remove();
continue;
}
}
System.out.println(SD.size());
return SD;
}
public static List caculateDM(){
//丹麦
List DM = makeList();
Iterator iterator = DM.iterator();
iterator = DM.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();
//丹麦人
if (item[0]!=2){
iterator.remove();
continue;
}
//喝茶
if (item[3]!= 3){
iterator.remove();
continue;
}
//不养狗
if (item[2] == 1){
iterator.remove();
continue;
}
//不住红房子和绿房子
if (item[1] == 0 || item[1] == 1){
iterator.remove();
continue;
}
//不抽Price烟
if (item[4] == 0){
iterator.remove();
continue;
}
//不住第一间和中间
if (item[5] == 0 || item[5] == 2){
iterator.remove();
continue;
}
//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 && item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 && item[2]!=0){
iterator.remove();
continue;
}
//抽ＢＬＵＥ ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 && item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 && item[4]!= 2){
iterator.remove();
continue;
}
//绿房子主人喝咖啡
if (item[3] == 0 && item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 && item[3]!= 0){
iterator.remove();
continue;
}
//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 && item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 && item[4]!= 3){
iterator.remove();
continue;
}
//住在中间那间房子的人喝牛奶
if (item[3] == 1 && item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 && item[3]!=1){
iterator.remove();
continue;
}
}
System.out.println(DM.size());
return DM;
}
public static List caculateNW(){
//挪威
List NW = makeList();
Iterator iterator = NW.iterator();
iterator = NW.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();
//挪威人
if (item[0]!=3){
iterator.remove();
continue;
}
//不喝茶和牛奶
if (item[3] == 3 ||item[3] == 1){
iterator.remove();
continue;
}
//不养狗
if (item[2] == 1){
iterator.remove();
continue;
}
//不住红房子和白房子
if (item[1] == 0 || item[1] == 2){
iterator.remove();
continue;
}
//不抽Price烟
if (item[4] == 0){
iterator.remove();
continue;
}
//住在第一间
if (item[5] != 0 ){
iterator.remove();
continue;
}
//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 && item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 && item[2]!=0){
iterator.remove();
continue;
}
//抽ＢＬＵＥ ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 && item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 && item[4]!= 2){
iterator.remove();
continue;
}
//绿房子主人喝咖啡
if (item[3] == 0 && item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 && item[3]!= 0){
iterator.remove();
continue;
}
//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 && item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 && item[4]!= 3){
iterator.remove();
continue;
}
//住在中间那间房子的人喝牛奶
if (item[3] == 1 && item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 && item[3]!=1){
iterator.remove();
continue;
}
}
System.out.println(NW.size());
return NW;
}
public static List caculateGM(){
//德国
List GM = makeList();
Iterator iterator = GM.iterator();
iterator = GM.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();
//德国人
if (item[0]!=4){
iterator.remove();
continue;
}
//不喝茶不喝酒
if (item[3] == 3 || item[3] == 2){
iterator.remove();
continue;
}
//不养狗不养鸟
if (item[2] == 1 || item[2] == 0){
iterator.remove();
continue;
}
//不住红房子
if (item[1] == 0 ){
iterator.remove();
continue;
}
//抽Price烟
if (item[4] != 0){
iterator.remove();
continue;
}
//不住第一间
if (item[5] == 0 ){
iterator.remove();
continue;
}
//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 && item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 && item[2]!=0){
iterator.remove();
continue;
}
//抽ＢＬＵＥ ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 && item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 && item[4]!= 2){
iterator.remove();
continue;
}
//绿房子主人喝咖啡
if (item[3] == 0 && item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 && item[3]!= 0){
iterator.remove();
continue;
}
//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 && item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 && item[4]!= 3){
iterator.remove();
continue;
}
//住在中间那间房子的人喝牛奶
if (item[3] == 1 && item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 && item[3]!=1){
iterator.remove();
continue;
}
}
System.out.println(GM.size());
return GM;
}
public static void main(String[] arg){
List UK = caculateUK();
List SD = caculateSD();
List DM = caculateDM();
List NW = caculateNW();
List GM = caculateGM();
List resultList = new ArrayList();
Iterator uki = UK.iterator();
UK:
while (uki.hasNext()){
int[] uk = (int[]) uki.next();
Iterator sdi = SD.iterator();
SD:
while (sdi.hasNext()){
int[] sd = (int[]) sdi.next();
//去除重复
for (int i = 1; i<6; i++){
if (uk[i] == sd[i]){
continue SD;
}
}
Iterator dmi = DM.iterator();
DM:
while (dmi.hasNext()){
int[] dm = (int[]) dmi.next();
//去除重复
for (int i = 1; i<6; i++){
if (sd[i] == dm[i]){
continue DM;
}
}
for (int i = 1; i<6; i++){
if (uk[i] == dm[i]){
continue DM;
}
}
Iterator nwi = NW.iterator();
NW:
while (nwi.hasNext()){
int[] nw = (int[]) nwi.next();
//去除重复
for (int i = 1; i<6; i++){
if (dm[i] == nw[i]){
continue NW;
}
}
for (int i = 1; i<6; i++){
if (sd[i] == nw[i]){
continue NW;
}
}
for (int i = 1; i<6; i++){
if (uk[i] == nw[i]){
continue NW;
}
}
Iterator gmi = GM.iterator();
GM:
while (gmi.hasNext()){
int[] gm = (int[]) gmi.next();
//去除重复
for (int i = 1; i<6; i++){
if (nw[i] == gm[i]){
continue GM;
}
}
for (int i = 1; i<6; i++){
if (sd[i] == gm[i]){
continue GM;
}
}
for (int i = 1; i<6; i++){
if (dm[i] == gm[i]){
continue GM;
}
}
for (int i = 1; i<6; i++){
if (uk[i] == gm[i]){
continue GM;
}
}
//绿房子在白房子左边
int[] green = new int[6];
if (sd[1] == 1){
green = sd;
}else if (dm[1] == 1){
green = dm;
}else if (nw[1] == 1){
green = nw;
}else if (gm[1] == 1){
green = gm;
}
int[] white = new int[6];
if (sd[1] == 2){
white = sd;
}else if (dm[1] == 2){
white = dm;
}else if (nw[1] == 2){
white = nw;
}else if (gm[1] == 2){
white = gm;
}
if ((green[5] - white[5]!=-1 )){
continue GM;
}
//抽混合烟的人住在养猫人的旁边
int[] mix = new int[6];
if (uk[4] == 4){
mix = uk;
}else if (sd[4] == 4){
mix = sd;
}else if (dm[4] == 4){
mix = dm;
}else if (nw[4] == 4){
mix = nw;
}else if (gm[4] == 4){
mix = gm;
}
int[] cat = new int[6];
if (uk[2] == 2){
cat = uk;
}else if (sd[2] == 2){
cat = sd;
}else if (dm[2] == 2){
cat = dm;
}else if (nw[2] == 2){
cat = nw;
}else if (gm[2] == 2){
cat = gm;
}
if ((mix[5] - cat[5])!=1 && (cat[5] - mix[5])!=1){
continue GM;
}
//养马人住在抽ＤＵＮＨＩＬＬ烟的人旁边
int[] horse = new int[6];
if (uk[2] == 4){
horse = uk;
}else if (sd[2] == 4){
horse = sd;
}else if (dm[2] == 4){
horse = dm;
}else if (nw[2] == 4){
horse = nw;
}else if (gm[2] == 4){
horse = gm;
}
int[] dun = new int[6];
if (uk[4] == 3){
dun = uk;
}else if (sd[4] == 3){
dun = sd;
}else if (dm[4] == 3){
dun = dm;
}else if (nw[4] == 3){
dun = nw;
}else if (gm[4] == 3){
dun = gm;
}
if ((horse[5] - dun[5])!=1 && (dun[5] - horse[5])!=1){
continue GM;
}
//抽混合烟的人的邻居喝矿泉水
int[] water = new int[6];
if (uk[3] == 4){
water = uk;
}else if (sd[3] == 4){
water = sd;
}else if (dm[3] == 4){
water = dm;
}else if (nw[3] == 4){
water = nw;
}else if (gm[3] == 4){
water = gm;
}
if ((mix[5] - water[5])!=1 && (water[5] - mix[5])!=1){
continue GM;
}
//挪威人住在蓝房子旁边
int[] p2 = new int[6];
if (uk[5] == 1){
p2 = uk;
}else if (sd[5] == 1){
p2 = sd;
}else if (dm[5] == 1){
p2 = dm;
}else if (nw[5] == 1){
p2 = nw;
}else if (gm[5] == 1){
p2 = gm;
}
if (p2[1] != 3){
continue GM;
}
Map result = new HashMap();
result.put("uk", uk);
result.put("sd", sd);
result.put("dm", dm);
result.put("nw", nw);
result.put("gm", gm);
resultList.add(result);
}
}
}
}
}
for (Object o : resultList){
Map map = (Map)o;
Iterator it = map.entrySet().iterator();
while (it.hasNext()){
Entry en = (Entry)it.next();
int[] i = (int[])en.getValue();
if (i[0]==0) System.out.print("英国人 ");
if (i[0]==1) System.out.print("瑞典人");
if (i[0]==2) System.out.print("丹麦人 ");
if (i[0]==3) System.out.print("挪威人 ");
if (i[0]==4) System.out.print("德国人 ");
if (i[1]==0) System.out.print("红房子 ");
if (i[1]==1) System.out.print("绿房子");
if (i[1]==2) System.out.print("白房子 ");
if (i[1]==3) System.out.print("蓝房子 ");
if (i[1]==4) System.out.print("黄房子 ");
if (i[2]==0) System.out.print("鸟 ");
if (i[2]==1) System.out.print("狗 ");
if (i[2]==2) System.out.print("猫 ");
if (i[2]==3) System.out.print("鱼 ");
if (i[2]==4) System.out.print("马 ");
if (i[3]==0) System.out.print("咖啡 ");
if (i[3]==1) System.out.print("牛奶 ");
if (i[3]==2) System.out.print("啤酒 ");
if (i[3]==3) System.out.print("茶 ");
if (i[3]==4) System.out.print("矿泉水 ");
if (i[4]==0) System.out.print("Prince ");
if (i[4]==1) System.out.print("Pall Mall");
if (i[4]==2) System.out.print("Blue Master");
if (i[4]==3) System.out.print("Dunhill ");
if (i[4]==4) System.out.print("混合型 ");
if (i[5]==0) System.out.print("第一间 ");
if (i[5]==1) System.out.print("第二间");
if (i[5]==2) System.out.print("第三间 ");
if (i[5]==3) System.out.print("第四间 ");
if (i[5]==4) System.out.print("第五间 ");
System.out.println();
}
System.out.println();
}
}
}
输出结果是：
25 21 33 14 33 德国人 绿房子鱼 咖啡 Prince 第四间 英国人 红房子 鸟 牛奶 Pall Mall第三间 丹麦人 蓝房子 马 茶 混合型 第二间 瑞典人白房子 狗 啤酒 Blue Master第五间 挪威人 黄房子 猫 矿泉水 Dunhill 第一间
程序随手写来，并没有刻意去追求算法效率跟书写版式，相信一定会有更优的求解。
以前csdn上这道题有sql版本，JAVA版本的还是算了吧。 |
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
以前就不太喜欢这种类型题目
|
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
robertliudeqiang 写道 lenjey 写道 robertliudeqiang 写道 学过一门课，专门讲如何推理的。
试图回忆， 不过课的名字和内容已经完全不记得了... <<逻辑学>>？ 
真不记得了，数理逻辑？ 只记得： 对这种题目，每个条件表示成一个式子，再通过简单的过程就可以得到结果。有基于推理的语言支持。 离散数学吧 |
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
记得看drools的时候，看到过类似的问题。应该用规则引擎可以更好的解决这个问题吧
|
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
好像是离散数学的题目。。。
|
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
这个属于有约束条件的编程constraint programming
可以有一个叫choco的java库来解http://choco.sourceforge.net/first.html 基本思路就是设定一组变量，确实变量的范围，然后写约束条件，最后让程序求解 要是不用程序解的话，可以用回溯的算法手写去解 |
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
|
发表时间：2010-03-05
最后修改：2010-03-08
我也写了一个解法（约 100 行），不过不适合发 Java 版，放在综合版了：
http://www.iteye.com/topic/609049 基本思路便是回溯。不需要预先人为的去画表限定范围。效率应该比 lz 的解法高一些。 |
||||||||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||||||||
