00:00
同学们,我们继续来完成约瑟夫问题的最后一个,就是关于这个出圈的一个队列顺序的问题。我们留下这个问题啊,产生一个出对列出对编号的序列,还是老规矩,我们先做一个思路分析,然后呢再代码实现,我说了思路分析特别的重要,我们就以这个为例。我们就以这个为例。好,同学们,那同学们看上看看老师这个思路啊,那为了好讲解呢,我把这个部分拿过来。放到下边去,待会儿呢,我们好截图对不对,好截图。好,同学们,看我怎么来做这个出圈的一个处理呢?来看我的思路。就是啊,就是根据。就是根据用户的输入啊,生成生成一个小孩出圈。出圈的一个顺序。
01:03
对不对?好,我的思路是这样子的,同学们。首先呢,注意听讲啊,第一步。我第一步大家都知道,首先这有个指针,就是first,它指向这里的这个大家没有怀疑吧,就是你这个环形链表一旦形成,这有个first。这个first,那么那么现在的问题是,当我们出圈的时候,怎么把这个人从这一个环形列表里面去掉呢?我们需要一个辅助支针。而且它是环形的,因此呢,这个辅助指针它需要是指在哪里呢?它需要只在这一个带删除节点的前一个节点,是不是以前讲过这个事情呢?所以说我们现在呢,要做这样一件事情,先做这样一个事情,好,我们这样子啊,我们需要需要创建一个。辅助指针。
02:01
啊,当然你也可以解释是一个辅助的变量。那么为为了好讲解呢?我把这个辅助人叫做Harper。那么这个指针它事先应该指向哪里呢?注意听这句话啊,事先事先应该指向,指向first。First节点的应该这样写啊,应该指向环形,环形链表的最后这个节点。先要把它指向这里,那为什么呢?因为我们不是讲过吗?待会你first要数,那first数了几下过后我们把它出圈,是不是它后面有一个节点,后面有一个变量才能把它出圈呢?大家理解我的意思吧,也就是说我们先前呢,需要有一个指针,先让它指向。五这一个节点。注意听讲啊,这个地方还是有一点绕。Harper。
03:00
也就是说,我们让her指向这里,指向这里过后呢,同学们看第二句话,你不是要数几下吗?比如说我按我们按我们原先这个方法是这样的一个规定。是不是我们就一个具体的一个需求来讲,可能容易接受一下,现在。K等于一,从第一个人开始报数,数两下。数两下好,那么你从第一个人数两下数数数两下,其实他自己要数一下对不对。他自己要报数嘛,所以说他自己数一下的话呢,实际上他只是移动几位呢,移动一位。因为他他报数,他报他报二,其实他自己数一下做一二是不是第二个人在这儿,因此你的指针呢,应该怎这样走了,好把这个first。移动到这来,那移动到这来,同时呢,Harper我们也让它。一直跟在这个first后面,因此第二个动作呢,是当数数时,当小孩报数时。
04:04
报数时让谁让first?First和Harper。这个指针是吧,指针同时的。同时的。这个移动。同时移动,移动多少多少呢,移动K。哎,就是M啊,因为你不是倒数是M吗?M减一次。注意啊,不是移动M次,而是移动M减一次,因为你自己要数一下。所以说你虽然数了是2000,但实际上我们只移动移动了一次。好,移动完了,移动到这个位置,第三步就可以考虑出圈了。考虑。这时。这时就可以可以将谁呢?将first指向的指向的这个小孩节点。节点。这个把它就是first指这个节点,其实就是要出圈的嘛,把first指向这个小孩节点出圈。
05:05
那么你怎么样让它出圈呢?同学们想一想。你怎么让,你怎么让他出圈呢。其实非常的简单,其实非常简单,我们可以这样去出圈,我们可以这样去出圈,就说。我们让这个first。往前面移动一下。也就是说,先让这个first往前移动一次。大家理解我的意思吧,就是说他第一个动作呢,让这个first。等于first.next。是不是这个动作就刚才老师画的这条线就就做过来了,做过来以后让Harper。的next指向什么?指向这个first就可以了,指向这个最新的first,那下一步就应该是让Harper。Hep har next。
06:03
指向哪里呢?指向first。那也就是说这条线。就知道这儿来。能理解这意思吧,你看当我们这样做完了以后,你们看是不是这个二号,二号的这个节点就出圈了。因为你下次报数就从这个地方节点报一报的话,你看其实二号节点已经没有任何引用了,这时就会成为一个垃圾被回收好,当这样做了以后呢,就是就是这个节点,就是原先原来原来这个first。指向的,指向的这个就是该节点的啊就是。就就这样说啊,就就这个节点怎么描述呢?就原来first指向的这个节点就没有没有任何引用了。没有任何引用,那没有没有任何引用,呃,没有任何引用,那么就会什么呢?就会被回收,就会被垃圾回收机制回收是吧,就相当于出圈了嘛,呃,被回收。
07:06
好了,同学们,这就是出圈顺序的一个思路,大家听懂了没有?好的,那既然明白这个思路,老师就开始用代码将其实现,那现在呢,我们把这一个出圈的这个动作写到这里来。好,现在我们写一段代码啊,就是呃,让根据根据这样写啊,根据用户的输入。根据用户的输入啊,然后呢,行程或者或者计算都可以啊,计算出计算出出圈的一个顺序。小孩出圈的一个顺序非常的简单,老师开始写代码了,Public。Public void好,比如说我们就叫count boy属小孩。啊数小孩,那现在呢,我们先定一个变量大的no,就是这个代表你是从哪个地从第一个小孩开始数的。
08:04
是不是前面有一个这个值啊,然后呢,我们再定义一个变量叫count number。Color number呢,就代表你数几下,还有一个呢,你得告诉我一共有多少个小孩,因为我要我要做一个校验,好,我把这个地方做一个简单的简单的注释啊,同学们start number表示从。第几个小孩开始数数?那么count number表示数几项,表示数几项能理解吧?好,这个number表示什么呢?表示共有最初啊,应该是表示最初。最先前吧,最初。最初有多少小孩在圈?在这个圈中。能理解啊,那下面老师就开始来做校验先对。先对这个数据数据进行一个校验,就是至少呢,它要有一些合理性,对吧,我们做一个小小的建议啊,啊,如果。
09:10
如果什么呢?如果我们这个first。等于空说明什么问题?说明目前这一个队列,呃,这个环形队列什么都没有,所以说也就没谈不上去出圈的问题了,再比如说我们start number no。他如果小于一其实也没有必要来玩了,比如说你要人家问你从第几个小孩说,你说从。第零个小孩没有第零个小孩对吧,你至少要从第一个小孩吗。那么同时呢,我们这个number对吧,如果它大于了这个numbers,这也是不合理的,比如说我统共有五个小孩,但是呢,你要你告诉我要从第六个小孩,你你最多充第五个吗?就你你比如说你比如说我从第五个小孩是可以的,但是你不能说我从第六个小孩,因此十大number大于这个值就不行,等于还可以。
10:02
对吧,好,那现在呢,我们就提示这样一句话,就说你的参数输入有误。参数输入有误啊,请雄器输入请。请重新重新输入明白,然后这个时候就不玩了,直接。对不对,好,如果说他的数据没有问题呢,下面呢,我们是不是就要开始来根据老师刚才分析,先搞一个Harper。这个辅助指针对不对,好,我们先来创建。创建一个辅助指针。帮助什么呢?帮助我们。帮助完成小孩出圈。小孩出圈。没问题吧,好,现在呢,我们开始完成这段代码,Boy Harper,那这个就我就快速的写一下啊,先让他使用first。没有问题吧,然后呢,下边呢,我们就开始Y循环第一步。
11:01
是不是指向完了我们第一步要做的事情,先先要做什么事情,先让这个Harper指向我们这个队列的。这个。就是与最初的这个环形链表的最后这个节点,是不是这个刚才是不是完成这个事情了。也也就是说,我们第一个要要做的事情是事先。让它指向最后这个节点。那这个同学们。怎么怎么来完成呢?肯定是个Y循环嘛,那就Y循环了啊处,我就直接写代码啊处,那么你等于处如果Harper。就这个它的这个next。他的下一个等于了first说明什么问题,说明它到最后了,说明。说明这个Harper指向了指向最后一个节点,最后小孩节点能理解吧。好,然后呢,这个就break了,否则我让这个Harper怎么样呢,继续往下走。
12:04
对吧,让这个Harper继续往下走的话呢,我们可以这样去写,Harper等于harper.get next。因为我这个next指针为什么用的是方法,因为我这用的是私有的,不像以前以前我们直接点nextx就完了,现在是私有的,所以说用个方法返回的下一个。这个next的值。明白好,当他这个Y循环结束过后,是不是这个事情就搞定了。对吧,这个事情就搞定了,好,我们可以把它格式化一下啊,这样好看一点。老师换一下诶。格式化一下。好看一点好,呃,那么这个这这个动作做完了以后,下一步我们要完成的事情是什么呢?就是这个事情。对不对,报数,当小孩报数时,让这个first和孩子先报数,报数之前啊前他在报数之前呢,先让他定位,是这意思吧。
13:01
先让他定位,移动到他该去的地方啊,移动到K位我忘了啊,这地方有一个问题,我们这还有一个问题,因为它它还有一个问题啊,就是说你我们原先这个这个题出的刚好K,就等于一还没有移动还有问题呢。就是说你在报数之前,就是报数时这样子的。报数之前还有一个,还有一个工作,大家知道什么吗?在报数之前还要先移动到这个K这个这个位置,能理解我意思吧,这还有一个过程啊,我们这补充一下,刚才呃,刚才呢,分析的时候也没有错,是因为刚好我们就从第一个来报数,不需要移动,那假如这个K不是一,你是不是先要让Harper和这个,让这个first Harper先移动到。K,这个节点啊,是不是是不是好,这里还有个东西,先让报数前小孩报数。
14:02
报数前先移动,先让。先让这个first。First。和和谁呢?和Harper Harper移动。移动多少次呢?移动K减一次。这个大家明白我什么意思吧,就是先移动到。K,这个小孩这来。能能理解我在说什么吗?好,那现在呢,我把这个代码呢,就可以写到这里来了。好,那这个移动其实特别的简单,我直接负循环就可以了,负循环那NT解等于零对解小于什么呢?因为你移动是这个K,其实在这是大的number,是不是移动多少次减一次解加加跟上我的思路啊。好,这个时候移动,当然其实是特别简单的一件事情,是不是那这两个都要移动啊,First。
15:02
等于什么呢?First等于first的下一个。对不对?当然Harper呢,也是如法炮制。Harper是不是也要等于它的下一个呀?是不是这样子,就报数前都移动到。K减一次就移动到大的number,如果是针对这个题,就移动到大的number。呃,Number这个人了,好,这个做完了以后,是不是才开始完成我们这个动作。先移动了数到开始报数了。试一试吧。当小孩报数时,先让它移动,那么移动和这个移动到多少,多少次过后呢?然后出圈。然后除权。同学们想,这个移动多少次出圈,是不是一个循环的操作?因为你移动过后就出圈,移动过后就出圈嘛,因此它是一个循环啊,这里这里是一个循环的操作。
16:03
循环操作,直到什么呢,直到。直到圈中只有一个节点。那老师开始写这这段代码了,好,那现在开始Y循环。外循环处。对不对,跟上我的思路啊,有点这个有点绕好死循环,那首先呢,我们先判什么时候是圈中只有一个人呢,大家先告诉我什么时候圈中只有一个人,是不是当我们的这个Harper。它等于了first。说明只有一个人了,因为你你们想一想,他不停的出圈,就是不停的出,不停的出,最后Harper和first肯定指向同一个节点了。能理解我的意思吧,所以说当这个条件满足的时候,说明只有一个人了,说明圈。中。中只有一人。只有一个节点,那这个时候我们就应该。
17:05
Break,那否则我们应该怎么办呢?好,否则是不是先移动这么多次,然后出圈呢?啊,那否则就应该这样子啊,就应该是什么样呢,让。让。First,同时移动这么多次,多少次呢?在这儿来讲就应该是。这这么多次。能理解我的意思吧,因为这个变量,我这这个M变量在这是count number的意思,对应的意思,移动这么多次,然后除去。然后出去。先移动啊,再出圈,那移动这么多次是不是跟刚才很像啊,那开始就写代码了,Int结怎么还是零。结小于多少呢?Count number。减一减加加。不然啊,不然同学们跟上老师思路都OK,是不是先移动,移动到这个位置怎么移动呢?两个都要移动,是不是相当于是这段代码的。
18:04
一个复制啊。好,这个时候同学们,这个时候我问大家first first指向的这个节点是不是就是要出圈的这个小孩?能能理解吗?这时啊,这时,这时first指向的这个节点就是要出圈的小孩节点,那你可以把信息打出来了。能理解我的意思吧,好,小孩挤出圈呢,小孩把它编号打出来,出圈了。那么这个是为了好看呢,我们格式化一下。那么这个小孩的编号是哪?哪一个呢?就是first,刚才我已经分析过了啊。不可能每次我们都重新分析一遍first.get number。是不是这个小孩出圈,出圈完了过后是不是要把这个小孩。弄出去呀。好,这时,这时将first指向的小孩出圈。
19:05
First指向的小孩,小孩节点出圈。那么出圈是不是刚才老师已经分析了,就是这两个动作?是不是就这两个动作好,老师呢,把这个代码写一下啊,那出圈的时候呢,其实非常的简单,首先让first.first指向first下一个。也就是说这一句话就是106这句话。其实它的作用就是让。原先这个first。他比如说二号啊,原因这个分是指向了哪里呢。指向了这个三号节点,就原先是三嘛,你你最初的时候不是这样子的吗。啊,这样子啊,把这个。最初不是这样子的吗?最就说你刚开始的时候是Harper指向这里,First指向这里吗?是不是这个道理,然后我让first往下移一下,不是first指到这来了。
20:00
这个位置吗?也就是说这一句话,同学们看这句话就是达到了刚才那个效果,那这个还没用完,你还需要一个动作,就是让这条线。指向这里。就像这里能能理解我的意思吧,好,这这条线怎么构建起来呢?非常的简单,就是我们的这个Harper。Her它应该等于什么呢?Herper它应该是给它一个值,就是her,注意听啊。这这个地方是让her the next指向这个first啊,不是让Harper移动。再说一遍,这个是让her next域指向。最新的这个first不是让her移动,因此这个动作应该是这样写的,怎么写的呢?相当于是next等于first。对,但是因为我这个next呢是私有的,你没有办法这样去操作,因此我们这个地方应该改成Harper。
21:04
点site next first,好,就这么来的。好,这句话就是同学们看到107这句话,它的作用就是相当于构建成了这条线。我把它标粗这条线好,那这样做完了以后,这样做完以后不停的做,不停的做,不停的做,同学们想是不是最后他就break了。是不是就不然后呢,我我们我们做一句话啊,当他退出这个Y循环的时候,其实圈中只有一个节点了。好,那现在呢,我们把最后打出来,就是最后留在圈中的,最后留在我们也把它干掉啊,留在圈中的小孩编号是多少呢?把它打出来。对不对,小孩编号打出来斜杠N。同样我们进行一个格式化,把这个编号打出来,这个编号怎么取呢?就是first。
22:00
first.get他的number。当然,有些同学老师我用来get number可不可以一样的?所以这个时候,Harper和first其实他们都执行同一个节点了。好,同学们,那关于这个算法我们就写完了。是不是有有一点点绕啊,有一点绕,同学们呢,也可以考虑有没有更简单的方法啊,这个方法呢,反思是比较稳定的,好同学们,那现在我们就来玩一把呗,看看代码是否OK,是否OK来测试。这是一把这个小孩出圈,出圈是否正确?非常的简单。点什么呢,我们就以。就以我们分析的这个案例来做测试,不然待会我还得把这个顺序重新搞一遍,太累了啊,我们知道按照512这个顺序,它的出出圈啊,这写错了,出圈。出圈的。
23:00
出圈的一个顺序是这样子的。我们把它写到这儿来。出圈过形成了一个队列嘛,也可以这样理解啊,叫24153,最后留在圈里面的是三号。来,朋友们,我们先把第一个写成一。数几下,数两下,一共有几个五个?好,它对应的这一个顺序刚才已然分析过了,就是24153。那么是不是这样子的呢?运行字。啊,运行值大家看24153正确,当然这个时候我们可以把这个数据调的更大一点,比如说周老师假设我这我这有这个25个。25个好,这样子呢,你看如果我们用机器来算的话,一下就能算出来19号最后。对不对,你也可以把它改成125个人,125个人对吧,你也可以改从第十个人开始数20下,那也是可以的。对吧,那这个呢,就是63号,幸运者是63号。
24:02
同学们,那关于这道题我们就给大家讲到这里啊,重点还是要去理解他的思路,好,同学们,我们把这个题的板书给各位朋友走一下,那刚才我们讲的是什么呢?好,我们首先讲的是约瑟夫问题的一个示意,示意图是讲完了是吧,然后呢,我们把这个题整理一下。呃,约瑟夫问题的一个描述,再把描述和提示先整一下啊,描述和提示写到这来。哦,约瑟夫问题的一个描述。在这儿约瑟夫问题的一个提示在这,然后呢,下面呢,我们有约瑟夫问题的分析啊,就是约瑟夫约瑟夫。问题。怎么做图解呢?先是创建。创建环形。环形链表。链表的一个思路图解。
25:04
是不是思路图解啊。好,我把这个图解呢给同学们先放到这来,是这个图。是不是根据这个图我们来玩的呀?把这个图呢给各位朋友板书到这里。没问题吧,也就是说他的思路就是我们按照这个这个方式来给大家分析的。这是他的第。第一个就是创建的一个思路,紧接着我们又给他分析了约瑟夫问题,它的一个什么呀?就是他出圈形成这个队列的一个思路分析。就是出圈,小孩出圈。我写到这啊,小孩出圈。出圈的一个,呃,一个思路分析图。那这个图在哪里呢?这个图就是老师讲的这个图。啊,我也是一步一步给同学们分析过来的。对不对,好,那也也就是说具体就是老师这分析的一个流程。
26:04
啊,第一步。第二步第三步第四步啊,但这个补充呢,是因为我第一次设的K等于一,刚好就不需要移动,因为一嘛,它不用需要移动,但是KK它不是不是一的话,那就有移动的这个逻辑在里面,对不对?好,我把这个呢给同学们板书到笔记中去。这是他出圈的一个思路分析题。那最后这个约瑟夫问题的一个代码就写到这啊,那么就写一个。啊,约瑟夫,约瑟夫。问题的代码实现。代码实现呢,我直我直接就写到这里来了。好,这是双向链表,给他来一个标题二,标题二这样子。诶,写错了啊。呃,编一号,编一个号,然后我把代码呢,直接给同学们板书到我们的笔记中去就可以了。这段代码整体。
27:01
拷贝到。鼻祖。好,同学们,那关于用环单向的环形链表来解决这个约瑟夫问题呢?就给同学们评讲到这里。
我来说两句