谷歌网站关键词优化,网站开发工资淄博,网站怎么搬家,网站建设排名前言#xff1a;
据说著名犹太历史学家Josephus有过如下故事#xff1a;
在罗马人占领乔塔帕特后#xff0c;39个犹太人和Josephus及他的朋友躲进一个洞里#xff0c;39个犹太人决定宁愿死也不要被敌人抓到#xff0c;于是决定了一个自杀方式#xff0c;41个人排成一个…前言
据说著名犹太历史学家Josephus有过如下故事
在罗马人占领乔塔帕特后39个犹太人和Josephus及他的朋友躲进一个洞里39个犹太人决定宁愿死也不要被敌人抓到于是决定了一个自杀方式41个人排成一个圆圈。
由第一个人开始报数报数到3的人就自杀再由下一个人重新报1报数到3的人就自杀这样依次下去知道剩下最后一个人时那个人可以自由选择自己的命运。
这就是著名的约瑟夫问题。现在请用单向链表描述该结构并呈现整个自杀过程。 目录
题目
示例
图例
题目解析
约瑟夫问题的本质
图例
删除节点
未删除继续报数 代码演示 题目 编号为1到n的n 个人围成一圈。从编号为 1 的人开始报数报到 m 的人离开下一个人继续从 1开始报数。 n-1 轮结束以后只剩下一个人问最后留下的这个人编号是多少 示例 输入: 5 2返回值: 3 说明 : 开始 5 个 人 他们的编号分别是 12345 从1开始报数1-12-2 编号为2的人离开剩下1345从3开始报数3-14-2编号为4的人离开剩下135从5开始报数5-11-2编号为1的人离开剩下35从3开始报敷3-15-2编号为5的人离开最后留下人的编号是3 图例 通过图例和题目要求让我们想到了一种链表带环链表。带环链表之所以叫带环链表是因为最后面的节点内的指针指向了头节点也就是头尾相连了。 且带环链表的创建和单链表的创建是一样的只不过带环链表多了一步尾节点的指针 next 指向了头节点。 题目解析
首先因为题目的要求需要拥有两个数一个是指定的次数一个是节点的个数。 其次我们要创建链表的节点而创造链表的节点需要开辟空间这里需要使用malloc函数并将开辟的空间交予头节点指针以此形成第一个节点。 在进行开辟空间后需要形成链表而链表中节点的个数和之前的输入值有关所以需要进行循环创建节点对此要和上面开辟节点的函数形成调用联动。而且为了使得变成一个环形链表我们需要在所有节点开辟后并形成单链表的最后将链表的最后一个节点内部的指针指向头节点。 在形成节点后我们则进入约瑟夫问题。 约瑟夫问题的本质 如上图所示我们可以知道约瑟夫问题的本质实际上就是删除指定位置的节点。
而对于删除指定位置的节点我们需要两个指针进行遍历解决。 链表——单链表的简单介绍-CSDN博客https://blog.csdn.net/2301_76445610/article/details/133811446?spm1001.2014.3001.5501 两个指针一个是通过遍历访问指定位置cur一个是通过遍历访问到指定位置的前一个节点prev。
而又如图所示当最后只剩下一个链表的时候那一个遍历指定位置的指针指向的节点该节点内部的指针指向的是它自己。
所以当遍历指定位置 的节点 的内部指针 指向它自己的时候就是跳出约瑟夫游戏判断的时候。 因为之前返回值是返回环形指针的最后一个尾节点原单链表尾节点所有prev是尾节点而prev-next 则是原单链表的头节点。 而因为我们是从头指针开始的约瑟夫问题的所以报数是从1开始的这里我们就需要一个计数报数变量。 而接下来关于约瑟夫问题的核心部分便是计数和删除节点。当计数变量抵达我们指定的数字后需要将节点进行删除进行修改节点内部指针指向且将计数变量重置回初始值重置回1而未抵达我们指定的数字时则继续进行计数。
图例 删除节点 未删除继续报数 代码演示
