| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3808 人关注过本帖
标题:波瓦松分酒问题
只看楼主 加入收藏
soulmate1023
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:6
帖 子:256
专家分:831
注 册:2014-9-23
结帖率:91.67%
收藏
已结贴  问题点数:20 回复次数:15 
波瓦松分酒问题
RT;
某人有12品脱的啤酒一瓶,想从中倒出6品脱,但他没有6 品脱的容器,他只有8品脱和5品脱的两个容器,怎样到才可以将12品脱的酒分为两个6品脱的?
我觉得像是汉诺塔问题,就是递归,但是我不知道这个递归的出口该怎么写?智商有限。
求大神指教。
搜索更多相关主题的帖子: 啤酒 一瓶 
2014-11-07 23:00
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:7 
仍然是状态的遍历。这类问题一般是用广度优先搜索不用递归,但不是不能用递归。但不管怎样,必须做的一件事情是记录已遍历的状态。

递归的结束条件是:

1、当前状态已经是要求的终止状态(分成了两个6品脱),返回成功信息;

2、下一级递归返回了成功信息,返回成功信息;

3、当着状态可以到达的下一级状态都已经遍历过,返回失败信息。

重剑无锋,大巧不工
2014-11-08 07:58
ditg
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:16
帖 子:852
专家分:1937
注 册:2014-4-10
收藏
得分:7 
有点难,俺手工已经排出三种答案了,可能还有……

梦想拥有一台龙芯3A-4000
2014-11-08 11:55
ditg
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:16
帖 子:852
专家分:1937
注 册:2014-4-10
收藏
得分:0 
又排出一种,可能还有……俺承认已经败鸟……哈哈

梦想拥有一台龙芯3A-4000
2014-11-08 12:28
soulmate1023
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:6
帖 子:256
专家分:831
注 册:2014-9-23
收藏
得分:0 
回复 2 楼 beyondyf
自己找资料学到了一种不用递归的,也挺简单,就是没有到要求就一直循环,每个循环中都有很多判断进行分酒,但自己还是没写出来递归的代码,大神能不能再指导下,跪求。。。万分感谢
2014-11-08 14:30
soulmate1023
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:6
帖 子:256
专家分:831
注 册:2014-9-23
收藏
得分:0 
回复 3 楼 ditg
嗯,其实我觉得就一种,但这一种可以扩展很多;
A-12  B-8  C-5
12   0    0
4    8    0
4    3    5
9    3    0
9    0    3
1    8    3
1    6    5
6    6    0
我试出来的都最后都回归这个了,不知是不是我考虑不周,那你对这题的解法有什么想法吗?
2014-11-08 14:46
ditg
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:16
帖 子:852
专家分:1937
注 册:2014-4-10
收藏
得分:0 
至少在这个方向上有如下分支:

A-12  B-8  C-5
12   0    0
4    8    0
0    8    4
8    0    4
8    4    0
3    4    5
3    8    1
11   0    1
11   1    0
6    1    5
6    6    0

梦想拥有一台龙芯3A-4000
2014-11-08 15:17
soulmate1023
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:6
帖 子:256
专家分:831
注 册:2014-9-23
收藏
得分:0 
回复 7 楼 ditg
嗯,是我没考虑全,谢谢
2014-11-08 15:34
ditg
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:16
帖 子:852
专家分:1937
注 册:2014-4-10
收藏
得分:0 
我认为通用解法应该很难表达,主要是解的结构复杂,不算中间跳转,前后冗余也能增加解的数量(不用研究数据相关性都能找到十种左右的合法解)。

递归俺也没想出递归啥东东,你手工排一次再研究一下倒的顺序,估计程序也就出来了。

梦想拥有一台龙芯3A-4000
2014-11-08 15:53
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 5 楼 soulmate1023
倒酒方法肯定不止一种。找最快的方法(倒腾次数最少)广搜(BFS)是最适合的,找所有可行的方法深搜(DFS)倒更适合。

有兴趣的话我抽时间再写一篇分析

重剑无锋,大巧不工
2014-11-08 21:59
快速回复:波瓦松分酒问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.050693 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved