单向环形链表应用场景 Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从...约瑟夫问题-创建环形链表的思路图解 ? 约瑟夫问题-小孩出圈的思路分析图 ? 我自己画了一个图 ?
一、约瑟夫问题介绍 1、约瑟夫问题原题： n个小孩子手拉手围成一个圈，编号为k(1 问题分析： 根据题目的描述，很容易可以想到用单向循环链表来模拟。...2、代码实现： 根据上面的分析，可以写出如下代码： package com.zhu.study.linkedList; /** * 约瑟夫问题，即单向循环链表问题 * @author: zhu
约瑟夫问题： 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。...返回头节点的话还需要遍历链表 } int iceBreakingGame(int num, int target) { ListNode* prev=CreateList(num); //进行约瑟夫游戏...这个问题很难快速给出答案。...但是同时也要看到，这个问题似乎有拆分为较小子问题的潜质：如果我们知道对于一个长度 num - 1 的序列，留下的是第几个元素，那么我们就可以由此计算出长度为 num 的序列的答案。...算法 我们将上述问题建模为函数 f(num, target)，该函数的返回值为最终留下的元素的序号。
题目:约瑟夫问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。现在需要求的是最后一个出局的人的编号。
一、问题描述 约瑟夫环问题是一个很经典的问题：一个圈共有N个人（N为不确定的数字），按顺序第一个人的编号为1，第二个人的编号为2，第三个人的编号就为3，以此类推第N个人的编号就为N，现在提供一个数字K，...1：代码 #include //约瑟夫环 int main() { int ren=0;//人数 int k=0;//报数 int sum=8; int arr[100]...1：可以直接输入想报到几出局，以及想要得总人数 #include //约瑟夫环 int main() { int ren=0;//人数 int k=0;//报数 printf
问题提出： 约瑟夫环是一个数学的应用问题：已知n个人（以编号0，2，3...n-1分别表示）围坐在一张圆桌周围。...解决方案： 约瑟夫环有递归和非递归两种解决方案。 1. 非递归可用数组和循环链表来解决。...先来看一下递归函数： 为了简化问题，我们假设k=0，设f(n,m,i)为n个人的环，报数为m，第i个人出环的编号 当i=1时，f(n,m,i) = (m-1)%m 当i!
弗拉维奥·约瑟夫斯（Josephus problem）是一世纪著名历史学家，他和他39个战友被罗马军队包围在洞中。...约瑟夫斯是一个厉害的数学家，他立即想出了坐在哪里才能成为最后一个人。最后他加入了罗马军队。
n 个人围成一圈，从第一个人开始报数,数到m的人出列，再由下一个人重新从1开始报数，数到m的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。...
在牛客网上做到一道题，是约瑟夫环的变型，所以借此学习一下新知识，并且巩固一下对题目意思的理解，这一篇仅作约瑟夫环问题的解释，下一篇再写题目： ##1.首先，我们先来了解一下什么是约瑟夫环问题： 讲一个比较有意思的故事...##2.这就是约瑟夫环问题，接下来我们说个特例初步了解下这种问题的求解思路： 特例：2，当q = 2时候，是一个特例，能快速求解 特例还分两种 ###1.思路：注意这里的前提是n = 2^k(也就是...见图下： 这时候，我们从3号开始，就成了另外一个规模小1的约瑟夫问题（恰好为2^k的特例）。...假设n = 11，这时候n = 2^3 + 3，也就是说t = 3，所以开始剔除元素直到其成为2^k问题的约瑟夫问题。...q个人 约定： Jq(n)表示n人构成的约瑟夫环，每次移除第q个人的解 n个人的编号从0开始至n-1 我们沿用之前特例的思想：能不能由Jq(n+1)的问题缩小成为J(n)的问题（这里的n是n+1规模的约瑟夫问题消除一个元素之后的答案
题目背景 约瑟夫是一个无聊的人！！！
第一行为人数n; 第二行为报数k 10 4 对于约瑟夫问题当前实现方法大概有两种： 一：模拟： 链表模拟： 1 #include 2 #include 3...(x%n + (m%n)%n)%n (x%n+m%n)%n (x+m)%n (3)第二个被删除的数为（m-1）%n-1 (4)假设第三轮的开始数字为o，那这n-2个数构成的约瑟夫环为...映射 o--->0 o+1--->1 o+2--->2 --- --- o-2--->n-3 这是一个n-2个人的问题。...代入可得(y+m)%(n-1) 要得到n-1个人问题的解，只需要得到n-2个人问题的解，倒退下去。
n-1个人的报数问题（即n-1阶约瑟夫环的问题） 可能以上过程你还是觉得不太清晰，那么我们重复以上过程，继续推导剩余的n-1个人的约瑟夫环的问题： 那么在这剩下的n-1个人中，我们也可以为了方便，将这n...n-2阶约瑟夫环的问题呢？...后面的过程与前两次的过程一模一样，那么递归处理下去，直到最后只剩下一个人的时候，便可以直接得出结果 当我们得到一个人的时候（即一阶约瑟夫环问题）的结果，那么我们是否能通过一阶约瑟夫环问题的结果，推导出二阶约瑟夫环的结果呢...借助上面的分析过程，我们知道，当在解决n阶约瑟夫环问题时，序号为k1的人出列后，剩下的n-1个人又重新组成了一个n-1阶的约瑟夫环，那么 假如得到了这个n-1阶约瑟夫环问题的结果为ans（即最后一个出列的人编号为...[n] = (f[n-1] + m)%n //m表示每次数到该数的人出列，n表示当前序列的总人数 而我们只需要得到第n次出列的结果即可，那么不需要另外声明数组保存数据，只需要直接一个for循环求得n阶约瑟夫环问题的结果即可
代码 #include <stdio.h> /* 编号为 1，2，3，…，n 的 n 个人围坐一圈，任选一个正整数 m 作为报数上限值， 从第一个人开始按顺时...
这个游戏叫做“约瑟夫问题”！ 这个问题是一个古老的谜题，就像是一个神秘的宝藏地图，我们要一步步解开谜团，找到最后的宝藏！ 想象一下，我们有好多小朋友，大家手拉着手，站成一个大大的圆圈。...希望小朋友们能够通过约瑟夫问题的有趣游戏过程哦！记得要保持好奇心，继续探索编程的奇妙世界！
n个人进行编号。分别从1到n。排成一个圈。顺时针从1開始数到m，数到m的人被杀。剩下的人继续游戏，活到最后的一个人是胜利者。
首先来看一个著名的约瑟夫（Josephu）问题 设编号为1，2，3......个人围坐一圈，约定编号为k(1<=k <= n)的人从1开始报数，数到m的那个人出列，紧接着他的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止，由此产出一个编号的序列 如何解决上述问题.../遍历到最后 } temp = temp.getNext(); } } } 至此我们已经创建好了一个单向环形链表，接下来我们完成约瑟夫问题...约瑟夫问题 假设环形链表上有5个节点 设 k = 1 即从第一个节点开始计数 设 m = 2 即计数到m的那个节点出列，并记录其编号。...分析 这里涉及到一个问题，当我们出圈的时候，怎么把某个节点移除环形链表呢？ 1.这里需要一个辅助指针helper，默认指向环形链表中的最后一个节点。
1.故事背景以及题目概述 通过这个例子，我们就应该大致了解这个环形链表的约瑟夫问题大致是干什么的，先说一个很简单的例子，比如有5个数据组成一个环形结构，每次数到2的数字自杀，最后这个环形链表只会保留一个数据...，具体如下图所示： 下面的就是牛客网的题目，这个题目表面上看比较委婉，把这个数字删除，其实其本质就是约瑟夫问题，下面我会拆解步骤为大家进行介绍解题思路。...就是我们想要解决这个约瑟夫问题，首先就需要创建一个环形的链表，这个链表肯定要有很多个节点，我们这步就是提前封装一个函数，我们在创建环形链表之后进行创建节点的时候可以直接调用这个函数； （1）我们想要创建节点就要开辟新的空间存放这个节点...如果count=0就会错过这个节点（可能表述不是很清晰，反正就是说pcur已经指向了一个节点，所以count应该初始化为1）； （3）count==m就说明这个节点就是我们要删除的节点，这个节点就属于约瑟夫问题里面的报数节点...pcur指向新的节点，这个时候新的节点就是我们的报数节点的上一个节点的next指针指向的位置，让后让count=1重新开始计数； （4）这个过程就按照这样依次进行循环，什么时候循环会结束呢，我们都知道，约瑟夫问题里面最后会剩下一个节点
The Joseph's problem is notoriously known. For those who are not familiar with t...
com_onlinejudge&Itemid=8&page=show_problem&problem=1883 题意：n个人围成一圈，第一次删第m个人，然后每数K个删一个人，求最后一个人的编号 分析：典型的约瑟夫问题...则我们可以从这个人的后面编号设为k= m % n，则这n-1个人的编号依次为k,k+1,….n-1,n,1,2,…k-2; 则重新编号为0,1,2….n-2,那么我们就可以看作是在这n-1规模的子问题的约瑟夫环的基础上...，求解n规模的约瑟夫环。...设n-1规模的子问题的约瑟夫环的解为f[n-1],则n规模约瑟夫环是f[n] = (f[n-1] + k) % n; 证明过程如下： 原来编号依次为k,k+1,….n-1,n,1,2,…...] + m) % n;递推公式是f[i] = (f[i-1] + k) % i; 而f[1] = 0,则最后的结果是f[n]+1(因为f[n]是0,1…n-1编号的，所以要加1)这样，光秃秃的约瑟夫环问题就结束了
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/136125.html原文链接：https://javaforall.cn
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
