单向环形链表应用场景 Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m...提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从...约瑟夫问题-创建环形链表的思路图解 ? 约瑟夫问题-小孩出圈的思路分析图 ? 我自己画了一个图 ?
一、约瑟夫问题介绍 1、约瑟夫问题原题： n个小孩子手拉手围成一个圈，编号为k(1 <= k <= n )的人从1开始报数，报到m的那个人出列，它的下一位又从1开始报数，报到m的又出列……依此类推，直到所有人都出列...2、问题分析： 根据题目的描述，很容易可以想到用单向循环链表来模拟。...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，默认指向环形链表中的最后一个节点。
head = head.next; 17 } 18 } 19 return head; 20 } 由于有些手机可能会出现乱码问题...问题拓展 对于上道题，假设是从第 K 个节点开始报数删除呢？ 又该如何解决呢？
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
The Joseph's problem is notoriously known. For those who are not familiar with t...
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议
