00:00
好,同学们,我们来看一个分支算法的实际的最佳一一个应用案例,同学们看这里呢,有一个分支算法的经典案例叫汉洛塔,汉洛塔的传说对不对,这就不再多介绍了,说白了他就是说有一根柱子有64个黄金片,然后把这64个黄金片呢移到另外一个柱上。那么在移到另外一个柱子上的时候呢,它有一个规则,小盘不能放在大盘上,而且呢,有三根柱子之间一次只能移动一次盘,而且这个有人算过哈,假如我们每一秒钟移动一次,叫做每秒钟咱们一一次移动一个盘,那么1万这些金属片呢,一共需要这么多年。那太阳气的预期寿命据说也就是百亿年,所以说到了这个时候,其实地球早就灰飞烟灭了,这就是一个传说,那么如果让人来算,这基本上是完成不了的。完成不了的,那么同学们看,如果我们用程序来进行这个分支算法,用程序来算呢,这还是可以把它进行一个求解,来,我们来玩一把。
01:10
那么首先呢,我们来看这个汉诺塔,听起来好像挺复杂,但是你仔细一去做了,你会发现并没有那么复杂。对,我们先来给大家演示这个游戏,看看老师是怎么演示的,怎么去分析的啊好,打开我们这里,我们这有个资料,资料里面呢,我们这有数据结构经典的应用案例,我们先看汉洛塔的第一个案例。各位同学CD注意听哈,我们想一想,同学们,你汉洛塔最简单,如果用分的。这样一个思路最简单,是不是就是A塔只有一个盘?然后你要把A塔移动的C盘是一步到位,注意分析啊,待会我要总结的就是假设只有一个盘,这就是我们。64刻盘里面最简单的一个情况了吧,就是已经不能再分了,就最简单,它已经有个结果了,这个结果就是A到C,听清楚没有。
02:07
好,那么我们紧接着看,假设有两个盘,你会怎么做呢?OK,注意听假设如果有,如果我们这有两个盘,各位同学你会怎么玩呢?你的思路是什么样子呢?你的思路是不是这样子的?你的思路是假设有两个盘。那么我们实际上是把。这一个最上面这个盘,注意听,把最上面这个盘移动到B塔。是不是,然后再把AA塔的这个盘移动到C塔,再把。B塔的这个盘移动到啊,C塔也就完事了,注意听我说了三个步骤啊。八。两个盘里面,最上面这个盘移动到B塔,这是第一步。把A刚才原先这个A塔最下面这个塔移动到C塔,这是第二步,然后再把B塔这个盘移动到C塔,这是第三步完成了。
03:04
好,大家看,从这个规律,你们有没有发现,其实刚才我们就是三部曲,哪三部曲呢?就是。就是我们这个。塔的一这个A塔上不管有多少个盘,我们都可以把它看成只有两个,只有两个盘,最上面的盘和最下面这个盘。那么我们第一步实际上是要把最上面的所有的盘移动到B塔,再把A塔的最后这个盘移动到C塔,再把B塔的所有盘移动到C塔,其实就三步好,我们可以用这个思路再来解决第三个。你看是不是也就可以推出这个规律了来,朋友们,我们看是不是按照刚才老师这个思路就可以搞定呢?来玩一把,也就是说你现在应该怎么思考这个问题呢?你认为这三个盘我们认为就是两个盘。哪两个盘,上面两个盘,下面一个盘是不是整体来看相当于两个盘,那你就是相当于把上面的两个盘先移动到B塔。
04:07
是不是这个挺简单的呀。移动过来了已经,是不是第一步就完成了,再把A塔的盘移动到。C塔再把B塔的盘。移动到西塔是不是这个过程,那这个就很简单,往这边挪一下,往这挪一下,往这挪一套完事。是不样的,同学们好,我们再来看第四有四个盘,有四个盘的情况,同学们。有四个盘的情况,其实也跟刚才我们思考的过程类似。你是不是还可以这样看说,诶我们认为上面三个盘是一个盘。分成两个部分吗?然后下面有一个是不是你第一步要把上面三个盘先移动到B塔,再把A塔的下面这个盘移动到C塔,再把B塔的三个盘移动到C塔就完事了,其实还是三步,听清楚没有,那也就是说我们这个思路应该怎么办呢?先把这三个盘想办法移动到B塔。
05:07
这个难不难呐?这个难不难?其实一点都不难,移15步就够了,移动到这来,移动到这来,移动到这来。把它移动到这来,把它移动到这儿来会玩吗?把它移动到这儿来,把它移动到诶第一步完成。是不是说白了,你刚才就是把A塔的上面三个盘移动到B塔下面一步移动这。然后再把这三个盘想办法移动到C塔,这个这不就跟玩似的吗?你想一想,你要把这个B它移动出来,你先要只能先把这两个盘先移到A塔呀,是不是这个思路就很简单,往这来一下,往这来一下,往这来一下,往这儿来一下,往这儿来一下,往这儿来一下。望着那些高低。五个盘也是一样,我就不演示了啊,五个盘也是一样,那么我们现在的分析的结果其实已经有了,来根据刚才我们这个流程,其实这样子的,来同学们我把思路捋一捋,待会儿我们就写代码了,非常的简单啊,就说我们总是就这样子啊。
06:07
呃。呃,如果这样子。第一步。啊,先有个大的前提,我们。第一步啊。第一步就是如果只有只有一个盘。这个很简单,就A到C就完了,这个是最简单的一个求解。好,如果。那么这个这个词有一个派啊,假设这是第一个,第二如果。如果我们有两个,就是假设这个盘N表示大于等于二的情况。情况我们可以看作,我们可以看作是什么呢?看作是。就是总是把它看作啊,我们总是。我们总是可以看作是两个盘,哪两个盘呢?就是最下面的一个盘和最上面的所有的盘,就是看到哪两个盘呢,一个就是我们最下面的。
07:13
下边的盘,还有一个就是上面的所有盘,是不是把它看成两个部分呢?对,就是上面的。上面的盘不管有多少个,我都看这两个部分,那你该怎么做呢?第一步注意听啊,第一步先把注意听,先把这个最上面的盘从A移动到。是不是这样子的第二步。干什么呢,把最下面的最下。边。边的这个盘只有一个了,那就是从A移动到C完事,那么最后呢,把什么呢,把BB塔。因为你现在已经把。
08:01
这个最上面盘从A移到B了,那现在最上面的所有盘应该在B塔了,把B塔的。巴比塔的所有盘。从哪里呢?从这个B移动到C完事了。其实就是这样一个步骤,所以说你们对照刚才我们这个分支算法来看,这个就是最小的一个规模了,而这个呢,就是一个小的问题,而这个小的问题呢,它是一个递归的过程。大家看能不能理解,好,如果同学们理解了,那么现在呢,老师用代码给大家实现一把。我直接走代码了,同学们把代码呢打开,我们来写一把。好,呃,我们写一个啊,这个就叫分支算法,我还是新建一个包com.at硅谷点,那么这个分数算法刚才。我们用,我们就叫汉洛塔吧,好吧,就汉洛塔,汉洛塔就说,呃,这样子,既然它是一个算法,我们还是用他这个英文来写。
09:02
分支算法呢,它的英文是这样子的,Divided and control,那么这个我们就简写D。AC,好吧,我们就叫DAC DAC好的,那现在呢,我们在这里,诶这个地方没有。啊,对的对的,我们就写一个类。一个类,我们就叫什么名字呢,取个叫汉。汉诺。To。托,OK,汉洛塔,那这个地方我们把主方法勾上,我们把这个主方法勾上,好同学们,我们现在直接升代码了啊,我们直接写代码,就是我们的一个汉诺塔的一个代码。汉诺。一个呃方案,呃,那个移动方案移动。移动的方法,那么现在我们使用的是分支算法。使用分子。分制算法解决。
10:01
其实很简单,同学们看啊,我写一个public static void。注意听,然后呢,我们就叫汉。落。汉洛塔。Tall tall好,首先呢,我要知道你有多少个盘,这个没问题吧。你得告诉我你有多少个盘,第二个我们不是有三个柱子吗?那第一个就叫A,第二个就叫B,第三个就叫C,没有,没问题吧,同学们。好,现在呢,我们来看,刚才老师已经分析过了,如果只有一个。如果只有一个盘,那么A到C就解决问题了,是不是好,我就写如果只有,如果只有一个盘,那very easy very easy,那就if,我们的这个number。Number,它等于一,这个没得没什么可说,直接就是有一个求解的,那干什么呢?我就写第一个第一第一个盘怎么移动呢?OK,从好咱们打一个空格吧,加上从这个A到。
11:09
A加哪一个箭头好吧,到哪里呢?OK,到我们的这个C是不是一步就搞定你本身。你本身这边写的也是A到C嘛,那我就A到C就完事了,好的A,那A就说你这个就已经不是一个20多个了,我们刚才讲过,我们刚才已经做过这个流程了,就是如果你是如果你是N大于二的情况下,我们总是把它看成两个盘是这样子的吧。那判断两个盘,我们第一步要做什么事,刚才是不是已经分析了,第一步先把最上面的盘。移动到这,那么最上面的盘有多少个盘呢?我们刚才讲过,看到两个盘,你最下面的一个盘和上面的所有盘,应该是最下面的。
12:02
一个盘和上面的所有盘啊,应该这样理解,因为分成两个部分,对不对?好,那就开始写了,那汉诺糖递归。你现在是N减一,N减一是不是。把最上面的所有盘。从A到。A到B,那这应该写A,那这个地方就是B,将移到B中间,我们借助C。这应该怎么理解呢?就是。这样子啊把。呃,这个其实上面已经写了注释了,中间会利用到啊移动过程。移动过程会使用到哪里呢?这个C说说我把这C写到这,最终目标是A到B嘛,好,第一步做完,第二一个思路,同学们看。按照我们刚才写的,把最下边的这个盘从A移到C,是不是刚才也是这样演示的,那这个就简单了,直接说出一句话就完事了。
13:01
怎么写呢?OK,那就是应该写D,把这个number加上,因为你现在是。最下面这个盘肯定是number吗?你上面N减一,那最下面肯定是number了,好把这个盘D这个盘。干什么呢?从好的加上我们就写了啊从A干什么呀。移动到了C。是不是这样子的呀,从A移动到C,这是你A到C的一个过程,你A传进来是什么是什么,这个是哪个盘符就是那啊是哪个塔就是那个塔,就是A到C是这样子的吧,同学们。好,最后一步,第三一步,第三一步呢,各位同学就知道,我们这个时候把B塔的所有的盘移动到C,因为你刚才已经把所有的盘移动到这个B这块来了,现在要把所U盘再移从B移动C,那就已然是一个递归。是不是,那这应该是number减一是这样子的吧,那A到哪里呢?
14:06
那就是从B。到C中间借助于A,好,这个代码呢,就写完了,我就写这啊移动过程。移动过程使用到什么呀,AA塔。好,同学们,现在代码就写完了,已经写完了,我们来测一下,我们来测一下,待会儿呢,我们再验证一把,好吧。好的,现在呢,我们做一个比较复杂一点的。我们先整一个比较比较简单的吧,啊,看验证我们代码写的对不对。呃,A塔。碧塔。塔。好,同学们,如果现在我们只有一个盘,那这个就very easy了,那就一句话嘛,A到C这个我就不演示了,假设是两个盘。走一个两个盘,它是不是也很简单。第一个盘先从A,诶这个为什么没有打空格,第二个盘A到C。
15:05
Ad,我刚这地方并没有打空格啊啊,这少了一个空格,这样打一个空格就好看了啊,再来一下那对齐了吗?第一个盘从A到B没问题吧。然后第二,第二个盘是从A到COK,然后再把第一个盘从B到C,没有问题啊,同学们肯定是正确的,好,我们这次来一点难一点的五个盘。走一个这五个盘呢,你要人去做就有点复杂了,你看它整个流程是这样子的。一共多少部呢?呃,应该是三十三十多部,我们来试一试呗,这个我也没玩过啊,咱们试试看看他这个对不对,好,我这呢有个小游戏,这小游戏呢,他刚好有五个五个盘,那五个盘说实话你要动,你自己要去做的话,还是要稍微有点绕的,因为盘多了嘛,To玩一把。玩一把,我们看看到底这个算法能否呃,能否成功吧,来玩一玩。
16:02
A到C。快速的走向。A到第二盘是A到B没有问题。诶没有写过去啊,A到B,第一个盘从这个C到B。好,C到B到这来了啊,那么这个是第三个盘是A到C。没问题,第一个盘,哎呀。第一个盘。又从B到AB到AB。B到A,好,没有问题,下一个盘是A到C,又第一个盘。H。刚才是。是不是整错了?啊,重重新来一下啊,重新来一下这个这个对照这个整太太慢了,好吧,对照这个这个整太慢了,我这样子啊,我就就弄来弄去太慢了,我就让他自动演示,看看他的算法跟我是不是一样的就可以了。好,开始了啊。
17:00
好。大家看,因为我这已经写了一个算法。因为这个30多步,我这一个走太太慢了,好吧,咱就让他自动走那自动走那代码写过。好往下走,我们待会呢,看他最前面三步和最后后面三步是不是一样就可以了,对吧,就比较简单。好走,那这个还有点长呢,30多步。快了,结束了啊,同学们。搞定好,同学们看好,呃,前面三步是A。A到CA到BC到B到CA到BC到B正确的吧。啊,你可以再看A到C,这个也A到C也是正确的。也是正确的,好,前面四步都是没问题的,那么往下拉。再看后面四部是不是跟跟他一样A到C。B到C。B到A这个地方应该这样子,你们看啊。
18:00
A到C。B到C正确。到B到A好,A到CA到CC到BAC到B好的,嗯,肯定是没有问题,这样是A到BA到B也是没问题,那总共一共多少部呢?呃,应该是,嗯,31部吧,好像我记得可以把这个粘过来。转过来给我们看看步骤,是不是大家都是31步,这样就证明呃是可以成功的。好,我把这粘一下,我们看看一共多少部。我呢用这个打开。用这个打开这个呢,可以把行显示出来,好同学们看,从这里数下来一共31步对吧?好,我把这个删掉,把这个删掉过后呢,我从这边再粘过来看看是多少步。我复制过来了啊,同学们。好,也是31步正确的,好同学们,那关于这个算法肯定是没有问题的,肯定能够走出来,因为步骤太多了,我就我就没去演示自己容易把眼睛看花,好吧,肯定算法是没问题,好同学们,那关于我们这一个分支算法的经典小案例就给同学们分享到这里,那现在面呢,我把刚才讲的做一个简单的本书,我们讲了哪些内容?
19:11
对不对。呃,刚才呢,我们讲的内容其实也挺简单的,就是讲了一下分支算法的一个概念和分支算法的一个应用,我们来走一走,首先呢,给各位朋友聊了一下何为分支算法。是这样子的吧,何为分支算法?那分支算法呢?它其实最用一句话来讲就是分而知之。对,但这个分而治之说起来容易哈,呃,其实简也也不容易,为什么呢?关键是你你作为一个程序员,你要知道怎么分,这个就比较难了啊,就一般的人呢,就是遇到这个复杂的问题,他不知道怎么分,这是比较麻烦的。所以说呢,我就后面就举了一个实际的例子,把这个点上。好,我们用的哪个例子来讲的呢?我们用的是汉诺塔。对吧,多塔好,这是它的一个基本介绍,紧接着呢,给同学们聊了一下分支算法的几个步骤的基本步骤三步,哪三步呢?看到这里。
20:10
哪三部呢?好,就是分解解决和合并,合并的过程。给大家放到这,这个说完了以后,我们是不是就给大家说了一下,它的分支算法的一个设计模式大概是什么样子的,对不对,好放到这里来,好,这个应该是三号。它的一个模式呢,我就不多说了,直接把这个图给同学们板书到笔记中,同学们以后可以来复习。紧接着我们又给同学们说来一个应用,就是汉诺塔的一个应用。啊,还是属于我们分支算法对吧。Andta的一个应用。好,这个地方应该算是。哦,还是我们的标题三。好,汉洛塔的一个传说,先说了一下,然后呢,围绕这个汉诺塔呢,我们就来开始给大家做了一个演示,就是怎么玩这个游戏。
21:07
这么玩这个玩这个游戏的过程中呢,我们就把他的一个思路给各位朋友搞了一把,对吧,就说诶他是怎么玩的,怎么去怎么去分的,这个问题说了一下。就是汉洛塔游戏的一个演示和思路分析,具体来说呢,我把它分成了这么几步呀,分成这么。五步一个盘是什么情况,诶这个这个不能写字啊。这个地方应该是相当于是你写到这里看啊,第一步这样做下面上面下面对吧,一样的第一步,第二步如果是如果是有两个情况,咱们又又开始怎么走好,这也是一样的道理,好。那这个整完了以后,这个整完了以后,我们又整了一个什么呢?我们又准备了一个什么呢。我们接着,我们接着给同学们就上代码了,就是在分析完了过后,我们就把这个代码给同学们实现了一把,其实你看这个汉洛塔的代码还是特别简单,就几句话就搞定了,是不是哪几句话大家看。
22:08
是不是我相当于就把汉诺塔方法,就是按照刚才我们这个分析,把代码给他翻译了一下,就把我的思路翻译了一把而已。OK,好,这是。我们最后的汉诺塔解决方案的一个代码就是诶。代码在哪呀?在这儿是不是忘了粘过来了?放这就可以了,好吧。同学们,那关于我们分支算法的一个经典应用案例,汉洛塔就给大家介绍介绍到这里,大家呢,要通过这一个小案例,汉洛塔小案例来理解这个分支算法的精髓,其实分支算法它本身理解不难,我刚才已经讲过很多遍,最关键就是说你怎么能够把它。分解出来就你怎么知道,哎,第一盘这样做,当N大于等于二的时候,你有这个思路,这个是有一定难度的,所以说来说去就说你算法你就是学完了过后,你自身没有思想,就说你你是学了很多算法,但是你自己没有这个玩意儿。
23:11
就你自己没有思想就麻烦了,其实大家也看到你,我们这里面没有数学的东西,对不对,没有数学东西,包括我们前面讲的这一个AV l数有有数学东西吗?没有,其实就是你要聪明,你自己的一个想法。然后再把这个思想转成你的代码,其实一直在做这个事情。对,当我们,当我们这个代码能够解决一系列的问题,就是解决通用的问题,这个代码就可以称之为算法了。如果你这个代码只能解决一个问题,那不能,如果你你能解决很多很多问题,解决一个模型,一个模型,一个数学模型,或者解决一类问题,这个代码就可以称之为算法。对不对?好,同学们,那关于我们分支算法的经典案例,汉洛塔就给大家介绍到这里。
我来说两句