360_尚硅谷_Go核心编程_数据结构和算法-约瑟夫问题分析.avi原创

好，同学们，我们接着上次课的内容哈，继续为大家讲解。上次课的的内容继续为大家讲解。那上次课咱们讲了一个环形的单项链表，对不对，讲了单项链表的这个添加，还有他的一个便利，以及它的一个删除。那么我们讲这个环形单向量表呢，咱们没有讲它的一个应用，也就是说用到哪个地方咱们没有说啊，用到哪个地方咱们没有说好。好，同学们，我们接着往下看啊，接着往下看，那么我们就用这个环形的单向列表来做一个应用实例，那么环形单项链表一个很经典的应用实例是什么呢？就是解决一个约瑟夫问题，也就是说，呃，这个叫什么呢？丢手帕的问题，我们先来看一下这个问题，它是一个什么问题哈。我们先来看一下这个问题。呃，他是这样子的，他这样子的，他说，呃，设一个编号为一到N的这么一个人，这些人这N个人呢，围成一圈，约定编号为K，这个人开始报数。

那这个K这个人呢，他有个要求，就是他必须在一到N之间。你想想吧，对吧，你不能大于这个N嘛，然后呢，从这个地方开始报数，数到M的那一个人就出列，就这个人就出去了，出去过后呢，他的下一位，注意他的说的话啊，他的下一位又从一开始报数。直数到M的那个人又出列，以此类推，直到所有人出列，由此产生一个出队列的序号，出出队编号的一个序列，就是问最后剩下的人是谁，那么他就这么一个意思，嗯，那么这个地方我们想一想这个思路怎么解决哈，我们看一下这我给了一个提示。

那么对于这样的问题，或者类似这样的问题，咱们怎么解决呢？比较经典的一种方式就是模拟它的这样一个实际的一个场景，你看啊，它围成一圈，你看这个一圈跟我们的这个环形链表其实是非常相似的，对吧？啊，它是非常相似的，那这样子的话呢，我们就可以这样做。用一个不带头节点的环形链表来处理约束风问题，怎么做呢？第一步，第一步咱们先构建一个有N个节点的单循环的列表，这第一步，第二步呢，然后由DK个节点，就是从DK个节点开始报数，数到M，计数到M。那么对应的节点就从这个链表中删除，但你要想一想怎么删掉，我们讲过环形链表，尤其是单向链表，它的删除呢，必须要在前面有一个辅助节点，如果你没这个辅助节点，你是干不掉它的，除非你是双向的。

对不对，但是我们这说单向环形列表，那你听到这句话，你的脑海里面就应该闪现出这么一个场景，就是说有一个节点在那不停的数，有一个另外一个节点在他屁股后面跟着跑。跟着跑，当前面那个节点数到M，数到那个M的时候，那么就用后面那个辅助节点想办法删掉。数到M的那个节点，以此类推，最后呢，就形成一个出队列的，一个一个排序啊，111个顺序，好，那这样子呢，我们画一个图来简单说一下他是怎么玩的啊，他怎么玩的，那么老师呢，也画一个图，待会呢，我们根据这个图来完成我们的这个案例啊，来完成我们这个案例这样子的。好的好的，那现在呢，老师画一个示意图，这个叫约瑟夫的一个示意图。好，我们来看一下。A。

这个地方啊，啊，约瑟夫。约瑟夫啊，约瑟夫的一个问题。好的，那同学们想一想啊，假设我们有五个人，待会我先把它描述清楚，有五个人啊，听清楚了，这是一个人。啊，这是一个人，那么我现在复制五个点，12345。好，我复制了五项啊，复制了五项。好，复制五项呢，我们把这几个人排好啊，待会明白老师想做什么事啊，五个人还多了一个人，这个人呢，干干掉就行了啊，干掉就行了，好，现在呢，我来描述一下他的一个场景，他这样子的，这是第一个人啊，先把这个意思表达清楚，这是我们的第二个人。这第二个人，但这个是我们的第三个人，这是第四个人，编号可能不一定完全是顺序编号，他也可能跳着跳着编，但现在呢，我们假设有这么一个场景啊，听我说先把这个意思说清楚，现在呢，有五个人啊，我们现在看一个场景。

一个实际实际应用的场景，这个题它是一个很经典的面试题，同学们啊，很经典面试题，那么第一步呢，我们假设有五个人围成一圈，五个人，五个人，五人啊，五人围成一圈。围成一圈。那这个这个相当于这个N就是跑到这儿呢，这个N就相当于五。啊，那你要想到这N等于五了。N等于五，然后呢，我们假设从第几个人开始数呢？从第二个人开始数第二个人。第二个，第二个人开始报数啊，开始报数。嗯，他报数的话报几个呢？哎，比如说我们报报两下吧把，比如报数两下，比如说数两下。两下它数两下的话呢，这就代表我们这个M呢，就相当于说是二啊，相当于等于二，就是相当于这个意思了，看这啊啊二数二。

那么从第几个人开始数呢？第二个人，那第二个人又数两下，干脆我们数三下吧，不要两个人都一样，那如果说从第二个人开始数的话，这个K就相当于二。K就相当于二，好，那么看看这个出列顺序是怎样的呢？好，先把你的这一个指针。先指到第二个人。先指到第二个，我们看一下它这个它一个顺序啊，那么指到第二个数几下，数三下一下啊，它本身要数一下啊同学们，它本身是要数一下的咯，好一下。两下三下好，相当于说第四个人先出列，第四个人出完列过后，谁接着数呢？同学们是第五个人接着数，下一个人接不是前面这个人啊，那就说第五个人又开始报数了，数几下呢？一一下，两下三下好，第二个人又出列，然后呢，这个他下一个第三个人又接着数，第三个人数一下，两下三下好，相当于说这个时候数到一了，一又出列，紧接着他的下一个人，第三个人又开始数三下，那只有两个人。

它属先要不够怎么办呢？因为它是环形的，所以说他说一二又一。那他自己又输了一，那这个呃，数到三了啊，就123啊，他数到三了，他又出列，他出列过后呢，第五个人，第五个人其实就是最后一个人了啊，第五个人肯定最后出列的，因为他他虽然只有一个节点，他仍然是一个环形的，所以他会相对于自数一二三都是他一个人数，最后他也处理，那么这个顺序就应该是2135。好，这样的问题呢，我们要用一个编程的方式来解决，大家其实应该感觉到这个还是很有意思的，因为这种类似的这种应用还是很多的，好，那么我把这个题给说清楚以后呢，同学们，我们就来用代码将其实现啊，我们用代码将其实现来吧，我们想想这个东西怎么解决啊，这是老师画的一个示意图啊，就按照。

按照。按照。按照老师刚才的分析。刚才的这个分析的分析，那么使用编程，使用这个单向的，我们写单向的环形环形链表链表来解决。来解决好的，这是我的示意图，那么我们进行一个简单的板书。好，我们来看一下这个问题的描述啊，首先呢，我们说了一下单向环啊，环形单向链表的一个应用实例，给它进行一个板书到这儿，这是我们的第三个对不对？好具体来说呢，呃，我们刚才说了这么这么几个问题啊。好，我把它进行一个简单的板书，约瑟夫问题的一个描述，对，它是一个什么含义，第二个呢，我给了一个提示，第三一个呢，我画了一个示意图，并且把我解题的思路做了一个图示的说明，好的同学们，我把这个刚才的示意图呢拿过来。

有了这个东西过后呢，我们就用代码将其实现来把它保存到这里啊好了，呃，同学们，刚才呢，就是我们对约瑟夫问题的一个分析，先说到这里。