00:00
那下一个呢,我们就来说一下,这个递归解决的问题很多叭,如说八皇后问题,汉洛塔阶层迷宫,求和男子的这个问题,那么这里面有些谷歌的编程大赛的题,同学们有兴趣可以去做一做,在哪里呢?如果有兴趣的话,大家可以啊去看一看,这里就在这以前我们这有一些。诶,我看这个题上哪去了。啊,没没在这儿是吧,诶我以前我记得有啊。啊,是不是在这儿。看看放哪儿去了。啊,在这在这那呃,听完今天这个,今天这个课过后呢,同学们晚上可以尝试着去写一下这个一些算法,那么我们随便打打一个啊,比如说公交车问题,或者是求和篮子吧,我们打开一下它的一个题的说明,下面也有代码。那如果说同学们有,呃,确实是有兴趣,可以看看这个求篮子的问题,它是大致是这么一个啊,这有一段英文,然后呢,下面是呃它的,诶这个字怎么这么小啊,我放大一点啊,各位同学我把它放大一点啊,大体是这样子,你有几个相同的球啊,希望把它放到各个篮子里边去。
01:18
每个篮子呢,有相同的容量,给一个int类型的这个一个变量代表这个没有自动换行是吧?啊这样子就好看了啊,给给一个这个呃,一个变量int basket表示男子的这个数量,就几个男男子,然后呢,再给一个变量叫capacity,就是代表容量。表示每个篮子最大容量,然后再给一个变量叫boss,就是球的个数啊,表示归类到篮子里面的球的数量,返回值是把球归类到篮子里面的方式的数量,如果不能完全存不到函字,这个篮子里面无法划分它返回什么,返回零,篮子要不相同,所有的球要相同,因此。
02:01
要求采用的这个方式,就是说按照这个要求,按照给定这个要求,你有几种存放方式。就这这种意思,就是你有几种存放方式,这是一个问题,还有一个比较经典的呢,就是公交车问题,大家也可以看一下啊,公交车问题我们来看看他是大致说什么。公交车问题,就说你有一个这个一个数组表示城市的一个布局。啊,就是城市的一个地图,那么给给定一个位置啊,就说B是我们,呃,指定的一个位置,X是你出发的位置,然后这个地方有有很多这个。这个公交车的这个站站台,其实说白了就是问,表示你愿意去一个公交车的最大路径和最短路径。就是求这个最大路径和最短的问题,那么代码呢?这也有相应的解决方法。啊,这些方法呢,对我们将来去解决一些,呃,最大最大路径最最小路径还是很有帮助的,好,这是一个,还有什么呢,就是一个汉洛塔,汉洛塔我们在以前已经演示过了。
03:10
汉洛塔的他的一个核心观点也是用递归。比如说当时我们不是在这个地方有一个,呃,有一个这个汉诺塔的一个说明吗?我们看汉洛塔它是一个什么什么体。哦,汉罗塔。汉诺塔。汉洛塔,他是这样子一回事。啊,杭州他是这样一回事。诶,这个地方上不去网啊。呃,说白了,它是就说一个古老的传说,然后呢有三根柱子,三根柱子呢,它有64个这个圆盘,然后呢,要求始终是把这个从下面按大小顺序重新摆离在另外一个柱子里面,最后人家看这个结果很很有意思啊,后面人家算了一下。算了一下,什么算法呢?就是说假如每一秒,每每秒钟移动一个盘子,一共需要多少时间呢?就是最后算出来时间是这么多时间。
04:08
啊,就说你如果一步都不错,就把64个盘子每一秒移动一次,一共要花。这么多时间,那你想人已经超出我们人的一个运算能力了,那这个时候如果我们写段程序,实际上是可以把他的一个步骤整理出来的。所以说这里面也用到一个递归,如果你不接触递归。其实我们这个人就做不了了。所以你你你们在做这个代码的时候,你们发现有一个特别有意思的现象,什么现象呢?就说计算机它到底能帮我们做什么事呢?计算机它其实只能帮我们做人会做的事。大家知道这意思吧,就说你人要会做,你才能告诉计算机去做。只是计算机有一个能力是人没有的,他可以干什么呢?他做的很快。
05:01
他其实只是做的很快而已。如果说你人都不会做这个事儿,你就别指望计算机帮你干。这个所以说为什么有些人说说老师,我学完过后为什么,呃,感觉好像也做不了,就是因为你自己不会做,肯定计算机是帮你做不了,他只是帮你做的更快。而已,好同学们注意这个啊,好,那这个这个逻辑呢,我们就不再多说,大家看这个我们不再把韩罗场跑一遍啊,跑一遍跑一遍,我们今天晚上的任务就是今天晚上呢,我给大家一个任务,就是你们能够把这个汉诺塔的代码。或者说这段核心的这个这个代码能够把它写出来,你看我们假如现在我简单测试一下,我把三个移过去啊,我这次只移三个,你看这个地方。这个地方啊,这个还。呃,再移到这边来,你看我们人移三个很快。我我就一三个过去。你看这个就过来了,然后诶这个移到这边来可以是吧,这个移到这来,这个移到这来,这个移到这来,你看我三个盘一下就移动完了,你看你只要会移动三个盘。
06:08
那你五个盘,五个盘必然也会移。那你64个盘也会移,只是你那个时候脑袋就转不过来了,所以你只要三个,就说刚才老师已经演示了一个三个盘移动过去的过程,你只需要把刚才老师写的这一个。顺序或者这个算法整理成一段递归代码就可以了。那当然有一种说我三个盘都移,移动不过去,那肯定就挤不出来。老师,我三个盘移动不来,那你肯定跑不起来的。所以说你首先要做这个题呢,你要怎么办呢?同学们,你首先先尝试着把三课盘移过去啊,其实挺简单的,你看。对吧,你看这个地方移动过来,把这个移动这来,然后这边移过来,然后这边移过来,这边移过来,这边移过来,诶这个移到这边来,然后把这个最大的要移过去,然后这边移过来,这边移过来,这边移过来,看三个就过来了,但你只要把刚才我们这个操作。
07:06
把它写成一个递归啊,只是把这个数变成五就可以了,晚上同学们尝试写一写啊,我今天就讲迷宫同学们晚上的任务呢,把这个汉诺塔写一写,那如果说同学们确实写不出来,把这个代码打开,这边也有算法,但是我希望同学们先自己写一写。其实代码并不难啊,并不难,但是就需要你们动动脑筋,你看核心算法并不多啊,核心算法可能在这里面啊,叫hello。啊,反正反正呢,自己要去动脑筋,好,这是我们演示的这么一一个解决的问题,那么递归他在这边要遵循的原则我就不再多说了,比如说呃,它的变量是独立的,而且递归要向退出递归的条件逼进等等等等执行完毕过后,它会遇到return就会返回,如果没有遇到return,当函数执行完毕也会返回。
08:00
OK,好,这是这么一段说明,那现在呢,我们就来正式的写这个代码了。我们就来写这段代码了,来,同学们,我们我先截段视频。
我来说两句