当前位置:大学毕业论文> 论文范文>材料浏览

关于韩信论文范文写作 用回溯法求韩信分油问题所有解相关论文写作资料

主题:韩信论文写作 时间:2024-02-19

用回溯法求韩信分油问题所有解,本论文为您写韩信毕业论文范文和职称论文提供相关论文参考文献,可免费下载。

韩信论文参考文献:

韩信论文参考文献 婚姻家庭法论文文献综述法求是杂志社社长求论文

摘 要:回溯法是一种常用的计算机程序设计方法.使用回溯法解决“韩信分油问题”也称“泊松分酒问题”,在算法中保存每一步执行的中间结果,程序扩展前,判斷程序是否进入“循环圈”,程序一旦进入“循环圈”,就不需要往下扩展,开始回溯了.如果能合理设计扩展的条件,防止程序陷入“循环圈”可以提高程序的效率.

关键词:算法;回溯法;泊松分酒;循环圈

中图分类号:TP311 文献标识码:A 文章编号:1009-3044(2017)34-0248-03

Abstract: Backtracking is a commonly used method of computer programming. The use of backtracking method to solve the "Han oil" also known as the " Poisson wine problem", se every step of execution of the intermediate results in the algorithm, the expansion of the program before the procedure to determine whether to enter the "circle", once the program into the circle, do not need to expand down and start backtracking. if can design reasonable expansion conditions to prevent the program into a "circle" can improve the efficiency of the program.

Key words: algorithm; backtracking method; Poisson wine; cycle ring

1 背景

韩信是家喻户晓的汉朝名将,聪明过人.传说有一天他骑马路过街市,见有二人争吵,下马细问,原来是一个卖油的只带了十斤、七斤、五斤三个油壶,十斤油壶装满了油,七斤、五斤油壶空的,没有带秤具,对方只想买一半,正为无法分出五斤油成交争执.韩信略加思考,立马给出了解决办法.

这其实是一个利用二个空的小容器将一个满的大容器均分的问题.法国数学家、物理学家和力学家泊松曾提出并研究该类问题,所以也称“泊松分酒问题”.

2 解题算法分析

计算机解决该类问题当然不需要用泊松研究的数学方法,只要利用自身强大快速的计算能力将所有的情况遍历,从而找出问题的所有解.

“韩信分油问题”的解是一步一步的步骤,例如韩信当时给出的分油办法如图1所示.

韩信的方法总共八步,当然解题方法不止一种,而且步骤可能是八步,也可能是九步、十步、...,由于每个解的步骤不相同,使用普通的穷举法无法实现,只能使用回溯法来穷举实现.

我们用a代表十斤油壶,b代表七斤油壶,c代表三斤油壶.进行下一步操作共有如下六种可能:

1) a倒入b;

2) a倒入c;

3) b倒入a;

4) b倒入c;

5) c倒入a;

6) c倒入b.

求解的每一步都市这六种可能的穷举,就这样一部一部扩展,直到某个油壶正好是要分的一半五斤油,就找到了一个解.

不过扩展到哪一步为止?然后回溯,正式文本论述的关键所在.普通的回溯法都是扩展到某一固定层数就开始回溯.分油问题因为每个解步数不相同,所以无法扩展到某一固定步数就开始回溯.当然可以规定到了足够多的n步开始回溯,但是n就不好定了,太小了可能漏掉解,太大了如n等于50,就要穷举6的50次方,费事太长,普通的电脑短时间无法找到所有解.

当进行到某一步时三个油壶的油量与前面经历的某一步相同,可以称之为进入“循环圈”.一步一步扩展下去,如果没有找到解停下并回溯,肯定会进入“循环圈”.一旦进入“循环圈”,就不需要往下扩展,就可以回溯了.这样做,不但合理地设定了扩展的终止条件,而且大大提高了求解的效率,因为跳过了很多无聊的步骤,如一个油壶倒入另一油壶,立马又倒回来.

3 C语言完整程序

4 结束语

通过运行上面程序,可以求出“韩信分油问题”共有十七个不同的解,最长步骤的解要十七步,最短步骤的解只需要八步,也就是韩信给出的办法.

参考文献:

[1] 李青, 张军, 张学军. 解决排班问题的多目标优化模型及算法研究[J]. 北京航空航天大学学报, 2003(10).

[2] 谢玉庚. 用回溯法编程求解爱因斯坦谜题[J]. 电脑与电信, 2016(10).

[3] 徐永琳, 巫青山, 林川. 递归回溯法求解整数线性规划及MATLAB实现[J]. 兰州文理学院学报:自然科学版, 2014(7).

结论:关于本文可作为相关专业韩信论文写作研究的大学硕士与本科毕业论文韩信论文开题报告范文和职称论文参考文献资料。

韩信分油
国外有“巴逊分牛奶”,中国则有“韩信分油”。思考方法其实是一样的,我们一起来看看吧!韩信是汉高祖刘邦手下的大将,不但善于用兵打仗,而且精通天文。

做统率金钱的韩信
我一位高中同学今年才30岁,手上已有两套房子,还一直把眼光瞄准其他城市的房产,大有随时入手第三套的态势。当同学们都在群里艳羡地称赞他有米时,他。

试析韩信气质性格对其命运影响
摘 要:本文根据史料记载的韩信早年事例并结合心理学知识首次提出韩信气质类型属于抑郁质。韩信的抑郁型气质对其矛盾性格、建功立业及悲剧结局都有重大影。

二次双溶剂冷冻结晶法分离纯化橡胶籽油中α—亚麻酸
摘 要:以橡胶籽油为原材料,皂化得混合脂肪酸,经冷冻结晶得脂肪酸Ⅰ,最佳条件是通过低温结晶法从纯双橡胶溶剂中分离α-亚麻酸的响应面方法建立的。基。

论文大全