/who_own_fish

谁养鱼问题编程解决

Primary LanguageJava

谁养鱼问题编程解决

问题描述:

前提:

  1. 有五栋五种颜色的房子
  2. 每一位房子的主人国际都不同
  3. 这五个人每人只喝一种饮料,只抽一种牌子的香烟,只养一种宠物
  4. 没有人有相同的宠物,抽相同的香烟,喝相同的饮料

提示:

  1. 英国人住在红房子里
  2. 瑞典人养了一条狗
  3. 丹麦人喝茶
  4. 绿房子在白房子左边
  5. 绿房子主人喝咖啡
  6. 抽PALL MALL烟的人养了一只鸟
  7. 黄房子主人抽DUNHILL烟
  8. 住在中间那间房子的人喝牛奶
  9. 挪威人住第一间房子
  10. 抽混合烟的人住在养猫人的旁边
  11. 养马人住在抽DUNHILL烟人的旁边
  12. 抽BLUE MASTER烟的人喝啤酒
  13. 德国人抽PRINCE烟
  14. 挪威人住在蓝房子旁边
  15. 抽混合烟的人的邻居喝矿泉水

问题是: 谁养鱼?

方案V1

使用遍历的方法

先把0-4所有的组合遍历出来,共120种情况,存到一个120x5的template的数组里面;然后将这个数组的每种情况分别应用到房子颜色、国籍、饮料、烟、宠物里面去,也就是一共有120^5中情况,然后判断哪一种情况符合提示描述。

如果单线程执行,时间有点长,所以根据可用线程数启用多线程并发计算。

开始是从0-120正序跑的,实际跑的时候,直到接近完成的时候才跑出结果。所以我把程序改成倒序120-0跑,但是我没有再跑程序。

正序运行log

这个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...

改良方案V2

参考穷举和推理:用C++程序求解“谁养鱼”上面的说明,如果在循环的时候先剔除条件,可以大幅度提高计算效率,只需要几百毫秒就可以计算出结果。我又改了一版V2版本,执行了37ms就执行出了结果,果真穷举也不能无脑穷举,为了多线程增加了代码复杂度还没有效率。

代码实现类是WhoOwnFishV2.java

运行log

找到一个结果:
挪威人,住黄色房子,喝矿泉水,抽DUNHILL,养猫
丹麦人,住蓝色房子,喝茶,抽混合烟,养马
英国人,住红色房子,喝牛奶,抽PALL MALL,养鸟
德国人,住绿色房子,喝咖啡,抽PRINCE,养鱼
瑞典人,住白色房子,喝啤酒,抽BLUE MASTER,养狗
德国人养鱼
---------------------
执行时间:37ms

答案

挪威 丹麦 英国 德国 瑞典
住黄色房子 住蓝色房子 住红色房子 住绿色房子 住白色房子
喝矿泉水 喝茶 喝牛奶 喝咖啡 喝啤酒
抽DUNHILL 抽混合烟 抽PALL MALL 抽PRINCE 抽BLUE MASTER
养猫 养马 养鸟 养鱼 养狗