数学研发论坛

 找回密码
 欢迎注册
楼主: mathematica

[提问] 三只水杯的倒水问题!!!

[复制链接]
发表于 2012-8-30 00:14:48 | 显示全部楼层
一条可行的路径可以由解不定方程 12+8x+5y=6 得到。 这个方程的意思是B12只用B8和B5定量出入,从而得到6.
方程的一种解是(-2,2),表示要从B12中倒出两杯B8, 倒入两杯B5. 这刚好是演进树中的最短路径。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-8-30 00:57:30 | 显示全部楼层
有三个酒杯,其中两个大酒杯每个可以装8两酒,一个可以装3两酒。现在两个大酒杯都装满了酒,只用这三个杯子怎么把酒平均的分给4个人喝。

3个杯子,4个人,怎么喝?两人或者多人用一只杯子?如果是这样就无解。
按基本的卫生常识,得假定每人有一个不计量的、3两以上的酒杯。作用是可以暂存酒,否则,分给各人的酒只能直接入口立即喝掉。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-8-30 01:10:40 | 显示全部楼层
每人有一个不计量的、2两以上的酒杯也行。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-8-30 02:35:49 | 显示全部楼层
口算的,可能不是最优的,利用好8-11这一段,这部分等价于有一个无限大的空杯子。

8 8 0 -> 0 0 0 0
8 5 3 -> 0 0 0 0
8 5 0 -> 3 0 0 0
8 2 3 -> 3 0 0 0
8 0 3 -> 3 2 0 0
8 3 0 -> 3 2 0 0
5 3 3 -> 3 2 0 0
5 6 0 -> 3 2 0 0
2 6 3 -> 3 2 0 0
2 8 1 ->  3 2 0 0
2 8 0 -> 3 2 1 0
0 8 2 -> 3 2 1 0
0 7 3 -> 3 2 1 0
3 7 0 -> 3 2 1 0
3 4 3 -> 3 2 1 0
6 4 0 -> 3 2 1 0
6 1 3 -> 3 2 1 0
6 0 3 -> 3 2 1 1
8 0 1 -> 3 2 1 1
8 0 0 -> 4 2 1 1
5 0 3 -> 4 2 1 1
5 0 0 -> 4 2 4 1
2 0 3 -> 4 2 4 1
2 0 0 -> 4 2 4 4
0 0 0 -> 4 4 4 4

评分

参与人数 1经验 +4 鲜花 +4 收起 理由
hujunhua + 4 + 4 既然存在路径,喝过的杯子洗一下就好

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-8-30 08:38:39 | 显示全部楼层
litaoye说得有道理。为了得到最短的到达路径,状态Hash的演进遵循最短路径原则,按此原则作出的演进图如下:
4206
共是25个状态Hash, 幸运的是包括(6,6,0),到达(6,6,0)的最短路径长度为7,2#给出的并不是最短路 ...
hujunhua 发表于 2012-8-29 23:39



大哥,你终于露手了!!!!!!!!!!
能说下你的图片用什么制作的吗??
我感觉不错!
还有,这类问题一定会是树吗???????
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-8-30 08:40:52 | 显示全部楼层
10# hujunhua


不是只有一条路吗?
为什么你会说2楼的不是最短的???????
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-8-30 09:38:11 | 显示全部楼层
15# mathematica
图是用几何画板作的。
演进图即使按照最短路径原则也不一定会是树。

按照最短路径原则生成的演进图不包括那些迂回的路径。作图时各条分枝是同步生长的,向下、斜向下或者水平的箭头都被“最短路径原则”滤掉了。所以2楼的那条迂回路径在10#的演进图上是看不到的。那条路径是从第2条(从左到右)支路的顶端横向第1支路的顶端,然后向下走一步。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-8-30 20:55:14 | 显示全部楼层
可以用Mathematica解出所有的状态Hash:
  1. {x,y,z}/.Solve[x+y+z==12&&yz(8-y)(5-z)==0&&0<=x<=12&&0<=y<=8&&0<=z<=5,{x,y,z},Integers]
复制代码

输出:
  1. {{0,7,5},{0,8,4},{1,6,5},{1,8,3},{2,5,5},{2,8,2},{3,4,5},{3,8,1},{4,3,5},{5,2,5}, {5,7,0},{6,1,5},{6,6,0},{7,5,0},{8,0,4},{8,4,0},{9,0,3},{9,3,0},{10,0,2}, {10,2, 0},{11,0,1}, {11,1,0},{4,8,0},{7,0, 5},{12,0,0}}
复制代码

刚好25个。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-8-31 01:30:27 | 显示全部楼层
14# litaoye 是最短路径。其中082-3210可以替换为253-3210,603-3211可以替换为811-3210,所以共是4条最短路径。

演进图不是树。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-8-31 11:43:29 | 显示全部楼层
2#给出的并不是最短路 ...
hujunhua 发表于 2012-8-29 23:39

道理是一样的。
8-2=6(减2意味需要2升容器)
5-3=2
8-5=3

B12      B8    B5
12        0     0
4         8     0
4         3     5
9         3     0
9         0     3(这样就产生了2升容器)
1         8     3
1         6     5
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-10-16 03:29 , Processed in 0.103138 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表