前提:
- 有五栋五种颜色的房子
- 每一位房子的主人国际都不同
- 这五个人每人只喝一种饮料,只抽一种牌子的香烟,只养一种宠物
- 没有人有相同的宠物,抽相同的香烟,喝相同的饮料
提示:
- 英国人住在红房子里
- 瑞典人养了一条狗
- 丹麦人喝茶
- 绿房子在白房子左边
- 绿房子主人喝咖啡
- 抽PALL MALL烟的人养了一只鸟
- 黄房子主人抽DUNHILL烟
- 住在中间那间房子的人喝牛奶
- 挪威人住第一间房子
- 抽混合烟的人住在养猫人的旁边
- 养马人住在抽DUNHILL烟人的旁边
- 抽BLUE MASTER烟的人喝啤酒
- 德国人抽PRINCE烟
- 挪威人住在蓝房子旁边
- 抽混合烟的人的邻居喝矿泉水
问题是: 谁养鱼?
使用遍历的方法
先把0-4所有的组合遍历出来,共120种情况,存到一个120x5的template的数组里面;然后将这个数组的每种情况分别应用到房子颜色、国籍、饮料、烟、宠物里面去,也就是一共有120^5中情况,然后判断哪一种情况符合提示描述。
如果单线程执行,时间有点长,所以根据可用线程数启用多线程并发计算。
开始是从0-120正序跑的,实际跑的时候,直到接近完成的时候才跑出结果。所以我把程序改成倒序120-0跑,但是我没有再跑程序。
这个log跑出来的时候没有加间隔时间的代码,所以没有打印出来具体执行的时间。大概执行时间为2-3个小时左右。
机器最大支持 4 线程并发
线程Thread-4-33开始计算(4-33)的情况
线程Thread-33-62开始计算(33-62)的情况
线程Thread-62-91开始计算(62-91)的情况
线程Thread-91-120开始计算(91-120)的情况
当前进度:0.01%
当前进度:0.02%
当前进度:0.03%
...略去进度的log...
当前进度:99.41%
当前进度:99.42%
当前进度:99.43%
找到一个结果:
挪威人,住黄色房子,喝矿泉水,抽DUNHILL,养猫
丹麦人,住蓝色房子,喝茶,抽混合烟,养马
英国人,住红色房子,喝牛奶,抽PALL MALL,养鸟
德国人,住绿色房子,喝咖啡,抽PRINCE,养鱼
瑞典人,住白色房子,喝啤酒,抽BLUE MASTER,养狗
德国人养鱼
---------------------
当前进度:99.44%
当前进度:99.45%
当前进度:99.46%
...略去进度的log...
参考穷举和推理:用C++程序求解“谁养鱼”上面的说明,如果在循环的时候先剔除条件,可以大幅度提高计算效率,只需要几百毫秒就可以计算出结果。我又改了一版V2版本,执行了37ms就执行出了结果,果真穷举也不能无脑穷举,为了多线程增加了代码复杂度还没有效率。
代码实现类是WhoOwnFishV2.java
。
找到一个结果:
挪威人,住黄色房子,喝矿泉水,抽DUNHILL,养猫
丹麦人,住蓝色房子,喝茶,抽混合烟,养马
英国人,住红色房子,喝牛奶,抽PALL MALL,养鸟
德国人,住绿色房子,喝咖啡,抽PRINCE,养鱼
瑞典人,住白色房子,喝啤酒,抽BLUE MASTER,养狗
德国人养鱼
---------------------
执行时间:37ms
挪威 | 丹麦 | 英国 | 德国 | 瑞典 |
---|---|---|---|---|
住黄色房子 | 住蓝色房子 | 住红色房子 | 住绿色房子 | 住白色房子 |
喝矿泉水 | 喝茶 | 喝牛奶 | 喝咖啡 | 喝啤酒 |
抽DUNHILL | 抽混合烟 | 抽PALL MALL | 抽PRINCE | 抽BLUE MASTER |
养猫 | 养马 | 养鸟 | 养鱼 | 养狗 |