原帖由 gxqcn 于 2008-6-2 10:28 发表 
爱因斯坦出了一道题，他说世界上有90％的人回答不出，看看你是否属于10％。
内容:
1、在一条街上，有5座房子，喷了5种颜色。
2、每个房里住着不同国籍的人。
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物。
已知条件：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽Pall Mall香烟的人养鸟
7、黄色房子主人抽Dunhill香烟
8、住在中间房子的人喝牛奶
9、挪威人住第一间房
10、抽混合烟的人住在养猫的人隔壁
11、养马的人住在抽Dunhill香烟的人隔壁
12、抽Blue Master的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽混合烟的人有一个喝水的邻居
问题：谁养鱼？
以前看这个题目的时候，说的是98%的人都回答不出来，不知为何，现在变成了了90%。
根据题意，由于没有明确给出一个人的名字，姑且都以国籍来区别不同人的姓名，如英国人、德国人等等，那么关于人的属性中，有如下几个字段：
房子的位置：posi
名字: name
房子的颜色：color
饮料：drink
香烟：cig
宠物：pet
这里有一个问题, 就是到底该以哪一个进行编号呢? 名字? 颜色? 饮料? 香烟? 宠物? 这些都有问题, 因为他们之间没有非常明确的顺序, 最后剩下的就是房子的位置了, 把它们编成0~4号
编号: 0 1 2 3 4
posi: P0 P1 P2 P3 P4
剩下的五个字段：name、color、drink、cig、pet也需要进行编号(0~4)，但是他们的号码还未知，需要我们去推导,
name: 英国人 瑞典人 丹麦人 挪威人 德国人
color: 红 绿 白 黄 蓝
drink: 茶 咖啡 牛奶 啤酒 水
cig: PALLMAL DUNHILL 混合烟 BLUEMAS PRINCE
pet: 狗 鸟 猫 马 鱼
推导后，如果我们得出“英国人 = 0, 红 = 0, 茶 = 0，PALL = 0, 狗 = 0”，就表明了英国人住第0间的红房子，喝茶，抽PALLMALL, 养狗。
再根据条件1-15，可以得到如下方程：
1. --> 英国人 = 红 (1)
2. --> 瑞典人 = 狗 (2) <严重申明: 本人绝对没有侮辱的意思>
3. --> 丹麦人 = 茶 (3)
4. --> 绿+1 = 白 (4)
5. --> 绿 = 咖啡 (5)
6. --> PALLMAL = 鸟 (6)
7. --> 黄 = DUNHILL (7)
8. --> 牛奶 = 2 (8)
9. --> 挪威人 = 0 (9)
10 --> |混合烟-猫| = 1 (a)
11 --> |马-DUNHILL| = 1 (b)
12 --> BLUEMAS = 啤酒 (c)
13 --> 德国人 = PRINCE (d)
14 --> |挪威人-蓝| = 1 (e)
15 --> |混合烟-水| = 1 (f)
直观上，可以由(8), (9)可得：
posi: 0 1 2 3 4
name: 挪威人
color:
drink: 牛奶
cig:
pet:
消去上述用过的条件，并整理相似条件，得：
1. --> 英国人 = 红 (1)
2. --> 瑞典人 = 狗 (2) <严重申明: 本人绝对没有侮辱的意思>
3. --> 丹麦人 = 茶 (3)
5. --> 绿 = 咖啡 (5)
6. --> PALLMAL = 鸟 (6)
7. --> 黄 = DUNHILL (7)
4. --> 绿+1 = 白 (4)
12 --> BLUEMAS = 啤酒 (c)
13 --> 德国人 = PRINCE (d)
10 --> |混合烟-猫| = 1 (a)
11 --> |马-DUNHILL| = 1 (b)
14 --> |挪威人-蓝| = 1 (e)
15 --> |混合烟-水| = 1 (f)
根据(e), 得 蓝 = 1 (g)
根据(4), 现大胆假设 绿 = 2 (h)
根据(5), 知咖啡与牛奶冲突, 假设失败
根据(h), 得 绿 = 3 (i)
根据(4), 得 白 = 4 (j)
根据(5), 得 咖啡 = 3 (k)
根据(1), 得 英国人 = 红 = 2 (l)
根据(l), 得 黄 = 0 (m)
根据(7), 得 DUNHILL = 0 (n)
根据(b), 得 马 = 1 (o)
到此位置, 我们得到了如下的推断表及剩余的条件:
posi: 0 1 2 3 4
name: 挪威人 英国人
color: 黄 蓝 红 绿 白
drink: 牛奶 咖啡
cig: DUNHILL
pet: 马
2. --> 瑞典人 = 狗 (2) <严重申明: 本人绝对没有侮辱的意思>
3. --> 丹麦人 = 茶 (3)
6. --> PALLMAL = 鸟 (6)
12 --> BLUEMAS = 啤酒 (c)
13 --> 德国人 = PRINCE (d)
10 --> |混合烟-猫| = 1 (a)
15 --> |混合烟-水| = 1 (f)
根据(3), 假设 丹麦人 = 4 (p)
根据(3), 得 茶 = 4 (p-1)
根据(c), 得 BLUEMAS = 啤酒 = 1 (p-2)
根据(2), 得 瑞典人 = 狗 = 3 (p-3)
根据(6), 知无法安排它们的值, 冲突, (p)的假设失败
根据(p), 得 丹麦人 = 1 (q)
根据(3), 得 茶 = 1 (r)
根据(c), 得 BLUEMAS = 啤酒 = 4 (s)
根据(d), 得 德国人 = PRINCE = 3 (t)
根据(t)及(2), 得 瑞典人 = 狗 = 5 (u)
根据(6), 得 PALLMAL = 鸟 = 2 (v)
根据(s), 得 水 = 0 (w)
根据(v)或(f), 得 混合烟 = 1 (x)
根据(a), 得 猫= 1 (y)
根据(y), 得 鱼 = 3 (z)
最后的排列如下:
posi: 0 1 2 3 4
name: 挪威人 丹麦人 英国人 德国人 瑞典人
color: 黄 蓝 红 绿 白
drink: 水 茶 牛奶 咖啡 啤酒
cig: Dunhill 混合烟 PallMal Prince BlueMas
pet: 猫 马 鸟 鱼 狗
即德国人住第四栋(3+1)的绿房子, 喝咖啡, 抽PRINCE, 养鱼
同时由(x), 可知, 第(f)个条件是多余的. 即不要第15个条件, 照样可以推出正确的结果!
源代码如下:- /************
- * 关于爱因斯坦98%的人都回答不出来的粗浅程序, 鉴于网络上没有很好的C参考程序, \
- * 这里尝试写一个, 聊博一笑! *^_^*, 请在VC6.0以上环境编译!
- * Email: silitex@yeah.net
- * 注: 如采用原始枚举: (5!)^5 = 24,883,200,000, 在普通的电脑需运行1分钟以上, \
- * 故做一个算法优化, 在枚举时, 把已知的2个条件: 牛奶 = 2, 挪威人 = 0, \
- * 直接确定; 这样算法的枚举次数为: (4!)^2*(5!)^3 = 995,328,000.
- * 用C++的标准做法应该把所有的内容封装成类, 否则太容易因为下表取错而出错!
- ***/
- #include <iostream>
- #include <stdlib.h>
- using namespace std;
- #define N 5
- #define N_NAME 24 // Name的枚举次数
- #define N_COLOR 120 // ...
- #define N_DRINK 24 // ...
- #define N_CIG 120 // ...
- #define N_PET 120 // ...
- enum E_NAME {ENGLISH, SWEDISH, DANE, NORWEGIAN, GERMAN};
- enum E_COLOR {RED, GREEN, WHITE, YELLOW, BLUE};
- enum E_DRINK {TEA, COFFEE, MILK, BEER, WATER};
- enum E_CIGARETTE {PALLMALL, DUNHILL, BLENDS, BLUEMASTER, PRINCE}; // Cigar类?
- enum E_PET {DOG, BIRD, CAT, HORSE, FISH};
- const char *NAME[] = {"英国人", "瑞典人", "丹麦人", "挪威人", "德国人"};// 人名
- const char *COLOR[] = {"红", "绿", "白", "黄", "蓝"}; // 颜色
- const char *DRINK[] = {"茶", "咖啡", "牛奶", "啤酒", "水"}; // 饮料
- const char *CIGARETTE[] = {"PallMal", "Dunhill", "混合烟", "BlueMas", \
- "Prince"}; // 香烟
- const char *PET[] = {"狗", "鸟", "猫", "马", "鱼"}; // 宠物
- extern const int ENUM_NAME[][N];
- extern const int ENUM_DRINK[][N];
- extern const int ENUM_ALL[][N];
- int main(void)
- {
- int tmp_name[N]; // 临时数组, 以上面的枚举变量为索引, 指示在第几栋房子
- int tmp_color[N];
- int tmp_drink[N];
- int tmp_cig[N];
- int tmp_pet[N];
- int out_name[N]; // 输出数组, 以第几栋房子为位置, 记录上面的枚举变量值
- int out_color[N];
- int out_drink[N];
- int out_cig[N];
- int out_pet[N];
- int i;
- long per;
- for (int n = 0; n < N_NAME; n++)
- {
- for (i = 0; i < N; i++)
- tmp_name[ENUM_NAME[n][i]] = i;
- for (int c = 0; c < N_COLOR; c++)
- {
- for (i = 0; i < N; i++)
- tmp_color[i] = ENUM_ALL[c][i];
- for (int d = 0; d < N_DRINK; d++)
- {
- for (i = 0; i < N; i++)
- tmp_drink[ENUM_DRINK[d][i]] = i;
- for (int c2 = 0; c2 < N_CIG; c2++)
- {
- for (i = 0; i < N; i++)
- tmp_cig[i] = ENUM_ALL[c2][i];
- for (int p = 0; p < N_PET; p++)
- {
- for (i = 0; i < N; i++)
- tmp_pet[i] = ENUM_ALL[p][i];
- /* 前面的就是枚举所有可能行, 下面的工作就根据条件判断\
- * 已知我们用掉了5个初始条件, 所以这里判断10个剩余条件.
- */
- if (tmp_name[ENGLISH] != tmp_color[RED])
- continue;
- if (tmp_name[SWEDISH] != tmp_pet[DOG])
- continue;
- if (tmp_name[DANE] != tmp_drink[TEA])
- continue;
- if (tmp_color[GREEN] != tmp_drink[COFFEE])
- continue;
- if (tmp_cig[PALLMALL] != tmp_pet[BIRD])
- continue;
- if (tmp_color[YELLOW] != tmp_cig[DUNHILL])
- continue;
- if (tmp_cig[BLUEMASTER] != tmp_drink[BEER])
- continue;
- if (tmp_name[GERMAN] != tmp_cig[PRINCE])
- continue;
- #if 1 // 绿在白的左边, 且必须为邻居
- if (tmp_color[GREEN]+1 != tmp_color[WHITE])
- continue;
- #else // 绿在白的左边, 不必为邻居
- if (tmp_color[GREEN] >= tmp_color[WHITE])
- continue;
- #endif
- if (abs(tmp_cig[BLENDS]-tmp_pet[CAT]) != 1)
- continue;
- if (abs(tmp_pet[HORSE]-tmp_cig[DUNHILL]) != 1)
- continue;
- if (abs(tmp_name[NORWEGIAN]-tmp_color[BLUE]) != 1)
- continue;
- #if 1 // 这个条件多余, 可以不用.
- if (abs(tmp_cig[BLENDS]-tmp_drink[WATER]) != 1)
- continue;
- #endif
- // 如果上面的条件都满足, 则显示出来
- for (i = 0; i < N; i++)
- {
- out_name[tmp_name[i]] = i;
- out_color[tmp_color[i]] = i;
- out_drink[tmp_drink[i]] = i;
- out_cig[tmp_cig[i]] = i;
- out_pet[tmp_pet[i]] = i;
- }
- printf("\nposi: 0 1 2 3 4");
- printf("\nname: %-7s %-7s %-7s %-7s %-7s\n", \
- NAME[out_name[0]], NAME[out_name[1]], \
- NAME[out_name[2]], NAME[out_name[3]], \
- NAME[out_name[4]]);
- printf("color: %-7s %-7s %-7s %-7s %-7s\n", \
- COLOR[out_color[0]], COLOR[out_color[1]], \
- COLOR[out_color[2]], COLOR[out_color[3]], \
- COLOR[out_color[4]]);
- printf("drink: %-7s %-7s %-7s %-7s %-7s\n", \
- DRINK[out_drink[0]], DRINK[out_drink[1]], \
- DRINK[out_drink[2]], DRINK[out_drink[3]], \
- DRINK[out_drink[4]]);
- printf("cig: %-7s %-7s %-7s %-7s %-7s\n", \
- CIGARETTE[out_cig[0]], CIGARETTE[out_cig[1]], \
- CIGARETTE[out_cig[2]], CIGARETTE[out_cig[3]], \
- CIGARETTE[out_cig[4]]);
- printf("pet: %-7s %-7s %-7s %-7s %-7s\n", \
- PET[out_pet[0]], PET[out_pet[1]], \
- PET[out_pet[2]], PET[out_pet[3]], \
- PET[out_pet[4]]);
- }
- }
- }
- // 显示当前的进度
- per = ((N_COLOR*(long)n)+(long)c+1)*100/(N_NAME*N_COLOR);
- printf("\rProgress: %02d%% ", per);
- }
- }
- return 0;
- }
- const int ENUM_NAME[][N] = {
- {NORWEGIAN, ENGLISH, SWEDISH, DANE , GERMAN },
- {NORWEGIAN, ENGLISH, SWEDISH, GERMAN , DANE },
- {NORWEGIAN, ENGLISH, DANE , SWEDISH, GERMAN },
- {NORWEGIAN, ENGLISH, DANE , GERMAN , SWEDISH},
- {NORWEGIAN, ENGLISH, GERMAN , SWEDISH, DANE },
- {NORWEGIAN, ENGLISH, GERMAN , DANE , SWEDISH},
- {NORWEGIAN, SWEDISH, ENGLISH, DANE , GERMAN },
- {NORWEGIAN, SWEDISH, ENGLISH, GERMAN , DANE },
- {NORWEGIAN, SWEDISH, DANE , ENGLISH, GERMAN },
- {NORWEGIAN, SWEDISH, DANE , GERMAN , ENGLISH},
- {NORWEGIAN, SWEDISH, GERMAN , ENGLISH, DANE },
- {NORWEGIAN, SWEDISH, GERMAN , DANE , ENGLISH},
- {NORWEGIAN, DANE , ENGLISH, SWEDISH, GERMAN },
- {NORWEGIAN, DANE , ENGLISH, GERMAN , SWEDISH},
- {NORWEGIAN, DANE , SWEDISH, ENGLISH, GERMAN },
- {NORWEGIAN, DANE , SWEDISH, GERMAN , ENGLISH},
- {NORWEGIAN, DANE , GERMAN , ENGLISH, SWEDISH},
- {NORWEGIAN, DANE , GERMAN , SWEDISH, ENGLISH},
- {NORWEGIAN, GERMAN , ENGLISH, SWEDISH, DANE },
- {NORWEGIAN, GERMAN , ENGLISH, DANE , SWEDISH},
- {NORWEGIAN, GERMAN , SWEDISH, ENGLISH, DANE },
- {NORWEGIAN, GERMAN , SWEDISH, DANE , ENGLISH},
- {NORWEGIAN, GERMAN , DANE , ENGLISH, SWEDISH},
- {NORWEGIAN, GERMAN , DANE , SWEDISH, ENGLISH},
- };
- const int ENUM_DRINK[][N] = {
- {TEA , COFFEE , MILK , BEER , WATER },
- {TEA , COFFEE , MILK , WATER , BEER },
- {TEA , BEER , MILK , COFFEE , WATER },
- {TEA , BEER , MILK , WATER , COFFEE },
- {TEA , WATER , MILK , COFFEE , BEER },
- {TEA , WATER , MILK , BEER , COFFEE },
- {COFFEE , TEA , MILK , BEER , WATER },
- {COFFEE , TEA , MILK , WATER , BEER },
- {COFFEE , BEER , MILK , TEA , WATER },
- {COFFEE , BEER , MILK , WATER , TEA },
- {COFFEE , WATER , MILK , TEA , BEER },
- {COFFEE , WATER , MILK , BEER , TEA },
- {BEER , TEA , MILK , COFFEE , WATER },
- {BEER , TEA , MILK , WATER , COFFEE },
- {BEER , COFFEE , MILK , TEA , WATER },
- {BEER , COFFEE , MILK , WATER , TEA },
- {BEER , WATER , MILK , TEA , COFFEE },
- {BEER , WATER , MILK , COFFEE , TEA },
- {WATER , TEA , MILK , COFFEE , BEER },
- {WATER , TEA , MILK , BEER , COFFEE },
- {WATER , COFFEE , MILK , TEA , BEER },
- {WATER , COFFEE , MILK , BEER , TEA },
- {WATER , BEER , MILK , TEA , COFFEE },
- {WATER , BEER , MILK , COFFEE , TEA },
- };
- const int ENUM_ALL[][N] = {
- {0,1,2,3,4}, {0,1,2,4,3}, {0,1,3,2,4}, {0,1,3,4,2}, {0,1,4,2,3},
- {0,1,4,3,2}, {0,2,1,3,4}, {0,2,1,4,3}, {0,2,3,1,4}, {0,2,3,4,1},
- {0,2,4,1,3}, {0,2,4,3,1}, {0,3,1,2,4}, {0,3,1,4,2}, {0,3,2,1,4},
- {0,3,2,4,1}, {0,3,4,1,2}, {0,3,4,2,1}, {0,4,1,2,3}, {0,4,1,3,2},
- {0,4,2,1,3}, {0,4,2,3,1}, {0,4,3,1,2}, {0,4,3,2,1}, {1,0,2,3,4},
- {1,0,2,4,3}, {1,0,3,2,4}, {1,0,3,4,2}, {1,0,4,2,3}, {1,0,4,3,2},
- {1,2,0,3,4}, {1,2,0,4,3}, {1,2,3,0,4}, {1,2,3,4,0}, {1,2,4,0,3},
- {1,2,4,3,0}, {1,3,0,2,4}, {1,3,0,4,2}, {1,3,2,0,4}, {1,3,2,4,0},
- {1,3,4,0,2}, {1,3,4,2,0}, {1,4,0,2,3}, {1,4,0,3,2}, {1,4,2,0,3},
- {1,4,2,3,0}, {1,4,3,0,2}, {1,4,3,2,0}, {2,0,1,3,4}, {2,0,1,4,3},
- {2,0,3,1,4}, {2,0,3,4,1}, {2,0,4,1,3}, {2,0,4,3,1}, {2,1,0,3,4},
- {2,1,0,4,3}, {2,1,3,0,4}, {2,1,3,4,0}, {2,1,4,0,3}, {2,1,4,3,0},
- {2,3,0,1,4}, {2,3,0,4,1}, {2,3,1,0,4}, {2,3,1,4,0}, {2,3,4,0,1},
- {2,3,4,1,0}, {2,4,0,1,3}, {2,4,0,3,1}, {2,4,1,0,3}, {2,4,1,3,0},
- {2,4,3,0,1}, {2,4,3,1,0}, {3,0,1,2,4}, {3,0,1,4,2}, {3,0,2,1,4},
- {3,0,2,4,1}, {3,0,4,1,2}, {3,0,4,2,1}, {3,1,0,2,4}, {3,1,0,4,2},
- {3,1,2,0,4}, {3,1,2,4,0}, {3,1,4,0,2}, {3,1,4,2,0}, {3,2,0,1,4},
- {3,2,0,4,1}, {3,2,1,0,4}, {3,2,1,4,0}, {3,2,4,0,1}, {3,2,4,1,0},
- {3,4,0,1,2}, {3,4,0,2,1}, {3,4,1,0,2}, {3,4,1,2,0}, {3,4,2,0,1},
- {3,4,2,1,0}, {4,0,1,2,3}, {4,0,1,3,2}, {4,0,2,1,3}, {4,0,2,3,1},
- {4,0,3,1,2}, {4,0,3,2,1}, {4,1,0,2,3}, {4,1,0,3,2}, {4,1,2,0,3},
- {4,1,2,3,0}, {4,1,3,0,2}, {4,1,3,2,0}, {4,2,0,1,3}, {4,2,0,3,1},
- {4,2,1,0,3}, {4,2,1,3,0}, {4,2,3,0,1}, {4,2,3,1,0}, {4,3,0,1,2},
- {4,3,0,2,1}, {4,3,1,0,2}, {4,3,1,2,0}, {4,3,2,0,1}, {4,3,2,1,0},
- };
|
楼主: gxqcn
IP卡
狗仔卡
显身卡
发表于 2008-9-18 10:00:17
发表于 2008-9-18 15:22:19
）！引以为戒，感谢ing。