两个小孩去打油,一人带了一个一斤的空瓶,另一个带了一个七两、一个三两的空瓶。原计划各打一斤油,可是由于所带的钱不够,只好两人合打了一斤油,在回家的路上,二人想平分这一斤油,可是又没有其它工具。试仅用三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。
问题分析:
用向量(a,b,c)表示状态——a表示1斤瓶中的油量,b表示0.3斤瓶中的油量,c表示0.7斤瓶中的油量。
问题的起始状态:(1,0,0)。
问题的目标状态:(0.5,0.2,0.3)或者(0.5,0.3,0.2)或者(0.5,0.5,0)。
确定算法,用以表示变化状态的规则。由于总共油量为1斤,而1斤的瓶可以装满所有的油,因此把1斤的瓶当作一个大油桶,因此在描述变化状态的时候只需给出0.7、0.3瓶的状态即可,1瓶的状态即为1-a-b的油量。可是由于在程序处理上的一致性,在程序的实现上我还是把1、0.3、0.7的瓶子统一处理,而不是用两个状态表示。
倒退法:1斤油桶设为a,0.3斤油桶设为b,0.7斤油桶设为c
算法1:(传统算法,逐个遍历)
假设油已经倒出完毕,那么a,b,c三个桶里面的油,肯定有一个桶是0.5斤油,而肯定不是b,因为b最多能装0.3斤油,也就是说0.5斤的油肯定不是在a中就是在b中,又因为总共有1斤,所以可以肯定的是ac各0.5斤油,而b则为0
下面是具体的倒油过程:
初始阶段:a=1,b=0,c=0 (提示:一定要有一个瓶子是空的,顺序倒油,1=0.3+0.7)
1.从a桶向b桶中倒油,直到b桶倒满为止,这时a桶剩下a=1-0.3=0.7,而b桶则为b=0.3,c=0,
2.从b桶向c桶倒油,直到b桶的油倒完或者c桶的油满了,此时c=0.3,而b=0,a=0.7,
3.从a桶向b桶中继续倒油,直到b桶满了或者a桶的油已经倒完,此时a=0.7-0.3=0.4,而b=0.3,c=0.3;
4.从b桶向c桶中倒油,直到c桶满了或者b桶的油倒完,这时c=0.3+0.3=0.6,而b=0,a=0.4;
5.从a桶向b桶中继续倒油,直到b桶满了或者a桶的油已经倒完,此时a=0.4-0.3=0.1,而b=0.3,c=0.6;
6,从b桶向c桶中倒油,直到c桶满了或者b桶的油倒完,这时c=0.6+0.1=0.7,而b=0.2,a=0.1;
7.从c桶向a桶中倒油,直到a桶满了或者c桶的油倒完,这时c=0.7-0.7=0,而b=0.2,a=0.8;(因为a,b,c此时都有油,所有反过来倒向a,直到有空桶)
8.从b桶向c桶中倒油,直到c桶满了或者b桶的油倒完,这时c=0.2,而b=0,a=0.8;(因为c桶为空,所以b继续向c中倒油)
9.从a桶向b桶中继续倒油,直到b桶满了或者a桶的油已经倒完,此时a=0.8-0.3=0.5,而b=0.3,c=0.2;(此时a桶满足要求)
10.从b桶向c桶中倒油,直到c桶满了或者b桶的油倒完,这时c=0.5,而b=0,a=0.5;(此时a桶满足要求,c桶满足要求,停止算法)
分享到:
相关推荐
分油问题 搜索算法 分油问题 搜索算法 分油问题 搜索算法 分油问题 搜索算法分油问题 搜索算法 分油问题 搜索算法
小孩分油问题(广度优先搜索算法)实验报告,附带c++代码,详细流程及流程图
程序实现了下列小孩分油问题:两个小孩去打油,一人带了一个一斤的空瓶,另一个带了一个七两、一个三两的空瓶。原计划各打一斤油,可是由于所带的钱不够,只好两人合打了一斤油,在回家的路上,两人想平分这一斤油,...
用队列数据结构实现分油问题
分油问题C语言.pdf
有个人用可装10千克油的桶装了一桶油去卖,正好来了两个买油的,每人要5千克,但是没有秤,只有两只空桶,可以分别装7千克和3千克油.请你想个好办法,利用这三个桶分出5千克的油.
要求程序寻找一种最少的分油步聚,在某个油桶中分出5升油 校园购物网www.school-mall.com诚招校园代理/兼职人员,联系QQ1580727012。主营产品有虚拟产品、数码产品、美容护肤品、流行服饰、首饰精品、配饰用品、...
小孩分油问题实验报告及源代码,c++程序
小孩分油问题:两个小孩去打油,一人带了一个一斤的空瓶,另一个带了一个七两、一个三两的空瓶。原计划各打一斤油,可是由于所带的钱不够,只好两人合打一斤油,在回家的路上,两人想平分这一斤油,可是又没有其他...
【计算智能】用深度优先搜索算法求解分油问题
NULL 博文链接:https://irwenqiang.iteye.com/blog/1497140
开始时,第一个油桶装满油,另外两个油桶为空,要求找出一种步骤最少的分油方法,在某一个油桶上分出targ公斤油。 输入:三个油桶的装油量(例如分别为80、50、30公斤)和需要分出的油量targ公斤(例如为40公斤);
设有大小不等、无刻度的三个油桶,它们的容量分别为x、y、z公升。初始时第一个油桶装满油x公升,其它两个油桶为空。寻找一种最少步骤的分油方案,能在其中一个油桶中分出m公升油...试用C#编写程模拟实现解决分油问题。
设有大小不等、无刻度的三个油桶,它们的容量分别为x、y、z公升。初始时第一个油桶装满油x公升,其它两个油桶为空。寻找一种最少步骤的分油方案,能在其中一个油桶中分出m公升油...试用C#编写程模拟实现解决分油问题。
问题7:分油问题 19 问题8:矩阵的排列 23 问题9:FBZ串 25 问题10:单词接龙 26 问题11:3*n方格问题 27 问题12:数串 28 问题13:求最长公共子串 30 问题14:求关键点和桥 30 问题15:士兵排队问题 33
将储油罐中油品体积分 为 和 两部分,通过取不同体积微元,积分计算无变位时的容积量对油高的 表达式。考虑影响时,通过转化,将此时容积转化为另一高度的无变位容积,利用已计算出的无变位公式求解。发生横向偏转...
本文以大规模成品油二次配送路径规划为对象,研究了具有成品油物流特征的多车场带时间窗的车辆路径问题的数学模型,提出了新的基于子问题分解的两阶段优化算法....