- 综合排序
- 最热优先
- 最新优先
- 来自专栏算法与编程之美
算法 | 约瑟夫环
欢迎点击「算法与编程之美」↑关注我们！ 本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。 问题描述 猴子选大王，让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。 从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？ 第一次报数由编号为1的猴子开始往后数3次编号为3索引为2的猴子退出，我们将索引为2的猴子从列表L中删除，之后更新列表编号在3之后的猴子的索引全部减1； 第二次报数由编号为4的猴子依次往后报数，编号为6索引为 总结 通过一周的学习又增加了自己的知识储备，在解题的过程中需要不断的思索，算法我现在对他的定义是一种解题的步骤——思路和公式。也许看书、看视频我们会觉得算法不就如此吗？ where2go 团队 ---- 微信号：算法与编程之美 温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！
93220发布于 2019-07-17 - 来自专栏算法与编程之美
Python|约瑟夫环算法
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。 （模拟此过程，输出出圈的人的序号） 解决方案 这道题涉及到的算法叫做“约瑟夫算法”，我们需要将列表内所有人类似排列成一个“圈”来解决，需要将前一次删除后剩下的元素的索引不变，但是位置向前提。 = 0: index = 0 print( "最后剩下的为：",location_list[0]) Josephus_problem(5,3) 结语 这道题的解决方法有很多种，这里主要介绍一下这种算法。
1.3K10发布于 2020-02-13 - 来自专栏爱编码
经典算法之约瑟夫问题
） 可能以上过程你还是觉得不太清晰，那么我们重复以上过程，继续推导剩余的n-1个人的约瑟夫环的问题： 那么在这剩下的n-1个人中，我们也可以为了方便，将这n-1个人编号为： 0,1,2,3,4...n- ..n-2，n-1，0，1，2...k2-3，k2-2 (k2-1第一次已出列) 那么在这个新的序列中，第一个人依旧是从1开始报数，那么在这个新的序列中，每个人报的相应数字为： 1,2，3,4....n 后面的过程与前两次的过程一模一样，那么递归处理下去，直到最后只剩下一个人的时候，便可以直接得出结果 当我们得到一个人的时候（即一阶约瑟夫环问题）的结果，那么我们是否能通过一阶约瑟夫环问题的结果，推导出二阶约瑟夫环的结果呢 借助上面的分析过程，我们知道，当在解决n阶约瑟夫环问题时，序号为k1的人出列后，剩下的n-1个人又重新组成了一个n-1阶的约瑟夫环，那么 假如得到了这个n-1阶约瑟夫环问题的结果为ans（即最后一个出列的人编号为 int count = 3; while (p.next!
2K10发布于 2019-11-14 - 来自专栏算法协议
Golang实现算法-约瑟夫环
什么是约瑟夫环约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。 最终胜利者是C图片普通算法使用Golang中的切片，来模拟约瑟夫环。通过cur游标来确定本轮次被踢出的元素，类似于丢手绢，丢到谁后，谁出局。当curl超过切片长度时，从头开始计算cur的值。 f2(n, m int) int {if n == 1 {return 0}return (f2(n-1, m) + m) % n}公式循环时间复杂度：O(N)空间复杂度：O(1)// 循环func f3( m := 2for n := 4; n < 12; n++ {res1 := f1(n, m)fmt.Println(res1)res2 := f2(n, m)fmt.Println(res2)res3 := f3(n, m)fmt.Println(res3)}}结果：000222444666000222444666总结： 利用数学公式写的算法就是牛
1K120编辑于 2023-02-16 - 来自专栏明志德到的IT笔记
C#约瑟夫环问题算法
///
/// 约瑟夫环问题算法 /// /// <param name="total">总人数30920编辑于 2023-10-21 - 来自专栏五分钟学算法
算法科普：什么是约瑟夫环
1 问题描述 约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。 若规定数到 3 的人出圈。则游戏过程如下。 （1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。 1， 2， 【3】， 4， 5， 6， 7， 8， 9， 10。 （3）从7号重新从1开始计数，则接下来数到3的人为9号，9号出圈。 1， 2， 【3】， 4， 5， 【6】， 7， 8， 【9】， 10。 循环链表求解 3.1 解题思想 约瑟夫环问题可以转化为循环链表的数据结构来求解。 >next = p; q = p; } q->next = head;//末尾节点指向头结点，构成循环链表 return head; } /*模拟运行约瑟夫环
1.5K20发布于 2019-05-06 - 来自专栏MyTechnology
Josephu(约瑟夫、约瑟夫环) 问题
3. 单向环形链表应用场景 Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束 约瑟夫问题-创建环形链表的思路图解 ? 约瑟夫问题-小孩出圈的思路分析图 ? 我自己画了一个图 ? (); //测试一把小孩出圈是否正确 circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->3
99940发布于 2021-01-18 - 来自专栏cwl_Java
C++经典算法题-约瑟夫问题
26.Algorithm Gossip: 约瑟夫问题（Josephus Problem） 说明 据说着名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus 及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了 一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀， 然后再由下一个重新报数，直到所有人都自杀身亡为止 解法 约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您与您的朋友？ 使用程式来求解的话，只要将阵列当作环状来处理就可以了，在阵列中由计数1开始，每找到三个无资料区就填入一个计数，直而计数达41为止，然后将阵列由索引1开始列出，就可以得知每个位置的自杀顺序，这就是约瑟夫排列 ，41个人而报数3的约琴夫排列如下所示： 14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10
1.2K10发布于 2020-02-13 - 来自专栏全栈程序员必看
约瑟夫算法（数学分析法）
//看了帖子后认为有趣就实现了一把递归的约瑟夫算法 package test; /** * 500个小孩围成一圈，从第一个開始报数：1，2，3，1,2,3,1,2,3,……每次报3的小孩退出 */ public class Test { /** * 约瑟夫标准循环非递归解法 * @param n * @param m * @return */ public static int i = 2; i <= n; i++) { index = (index + m) % i; } return index +1; } /** * 约瑟夫递归算法 //约瑟夫标准循环非递归解法 System.out.println(f2(n, m));//此方法来自帖子 /* (函数)index表示(变量)n个人玩游戏报(常量)m退出最后胜利者的编号 = 1;//第2个 * */ //參考上面的提示写了下约瑟夫的递归算法 System.out.println(f(n, m)+1); } } 今天看到一个LinkedList
27510编辑于 2022-07-13 - 来自专栏繁依Fanyi 的专栏
【算法】约瑟夫环问题解析与实现
本篇博客将详细解析约瑟夫环问题，并使用 Python 实现算法。 问题分析 在约瑟夫环问题中，有两个变量需要确定：人数 n 和报数的数字 m。当给定 n 和 m 后，需要确定最后留下的人的编号。 例如，当 n=7，m=3 时，约瑟夫环问题的过程如下： 1 2 3 4 5 6 7（初始状态） 1 2 4 5 6 7（第三个人出列，报数到 3） 1 2 4 5 7（第六个人出列，报数到 3） 1 4 5 7（第二个人出列，报数到 3） 1 4 5（第五个人出列，报数到 3） 4 5（第一个人出列，报数到 3） 4（最后一个人出列，报数到 3） 因此，最后留下的人的编号为 4。 3. 数组法 我们可以使用数组来模拟约瑟夫环的过程。首先，创建一个长度为 n 的数组，表示 n 个人的状态。初始化数组的值为 True，表示人还在圈中。 总结 本篇博客详细解析了约瑟夫环问题，并使用 Python 实现了一个基于循环链表的解决方案。通过使用循环链表，我们可以模拟约瑟夫环问题的过程，找到最后留下的人的编号。
1.8K20编辑于 2023-10-12 - 来自专栏刷题笔记
7-3 约瑟夫环 (25 分)
本文链接：https://blog.csdn.net/shiliang97/article/details/101472782 7-3 约瑟夫环 (25 分) N个人围成一圈顺序编号，从1号开始按1、 2、3......顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。 例如： 7 3 输出样例: 3 6 2 7 5 1 4 #include<iostream> using namespace std; int num[30005]; int main(){ int
1K10发布于 2019-11-08 - 来自专栏宫水三叶的刷题日记
【约瑟夫环】约瑟夫环思想运用题
Tag : 「动态规划」、「数学」、「约瑟夫环」 列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。 请你对 arr 应用下述算法： 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。 示例 1： 输入：n = 9 输出：6 解释： arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] arr = [2, 4, 6, 8] arr = [2, 6] arr = [6] 示例 2： 输入：n = 1 输出：1 image.png 约瑟夫环 image.png image.png 代码： class Solution { public int lastRemaining
60710编辑于 2022-05-27 - 来自专栏技术派
PHP使用栈解决约瑟夫环问题算法示例
本文实例讲述了PHP使用栈解决约瑟夫环问题算法。分享给大家供大家参考，具体如下： 约瑟夫环问题： 39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。 于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。 StackJoseph($arrayStack); return $joseph->handle($num//, $step, $survivorsNum); } print_r(joseph(41, 3,
53220发布于 2021-07-02 - 来自专栏后端开发从入门到入魔
【数据结构与算法】【约瑟夫问题】还在用递归？教你用链表秒杀约瑟夫
开始吧 引言：为什么学习链表是数据结构与算法的必备知识 链表是数据结构与算法中最基本、最常用的数据结构之一。 在算法竞赛中，链表常常被用作构建和实现其他复杂数据结构的基础，如栈、队列和图等。因此，掌握链表的知识和技巧，对于在竞赛中迅速解决问题、提高算法效率至关重要。 示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2- 1->1->2->3->4->4->5->6 示例 2： 输入：lists = [] 输出：[] 示例 3： 输入：lists = [[]] 输出：[] 提示： k == lists.length 0 【链表应用】约瑟夫问题 上面铺垫了那么多 其实也只是为了解决问题而做的嘛 那么现在我们来面对一个实际的问题 约瑟夫问题 （典中典了属于是） 约瑟夫问题（Josephus Problem）是一个经典的数学问题
33510编辑于 2024-03-01 - 来自专栏JavaEE
约瑟夫问题
一、约瑟夫问题介绍 1、约瑟夫问题原题： n个小孩子手拉手围成一个圈，编号为k(1 <= k <= n )的人从1开始报数，报到m的那个人出列，它的下一位又从1开始报数，报到m的又出列……依此类推，直到所有人都出列 那么最后出列的结果应该是：2，4，1，5，3。 二、单向环形链表的构建 1、构建思路： 首先创建第一个节点，用first指针指向它，它的next指向自己，如下图： ? 2、代码实现： 根据上面的分析，可以写出如下代码： package com.zhu.study.linkedList; /** * 约瑟夫问题，即单向循环链表问题 * @author: zhu cur.getNext(); pre.setNext(cur); } } 调用该方法，k、m、n分别输入1、2、5，最后发现结果和上面分析的一样，打印的是2,4,1,5,3。
63720发布于 2020-09-08 - 来自专栏C\C++
【算法通关指南：数据结构和算法篇 】链表相关算法题：3. 队列安排，4.约瑟夫问题
小龙报：个人主页 作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南 》 ✨ 永远相信美好的事情即将发生 前言 本专栏聚焦算法题实战，系统讲解算法模块：以《c++ 编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力***ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解 2.1题目 链接：约瑟夫问题 2.2算法原理 使用循环链表模拟即可。 ：《队列安排》和《约瑟夫问题》。 约瑟夫问题：利用循环链表模拟游戏过程，每次移动m-1次后删除节点，直至所有节点出圈。 代码简洁高效，适合算法初学者练习链表操作。文末附励志语句，鼓励坚持学习。
23110编辑于 2025-12-15 - 来自专栏全栈程序员必看
经典算法–约瑟夫环问题的三种解法
约瑟夫环问题，这是一个很经典算法，处理的关键是：伪链表 问题描述：N个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈。 （模拟此过程，输出出圈的人的序号） 在数据结构与算法书上，这个是用链表解决的。我感觉链表使用起来很麻烦，并且这个用链表处理起来也不是最佳的。 ，为总人数-1 int *circle = NULL; //根据需求设为循环数组，存储每个人 //用calloc()函数申请得到的空间，自动初始化每个元素为0 //所以，0表示在这个人在约瑟夫环内 那么circle[2] = circle[3] ，circle[2] = 4，circle[2]之前等于3，现在等于4。 即下标为3的第四个人已经被删除了。 怎样遍历？
1.3K40编辑于 2022-09-05 - 来自专栏算法与编程之美
约瑟夫环
1 问题 如何利用python设计程序，解决约瑟夫环的问题。 2 方法 已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。. 若规定数到 3 的人出圈。. 则游戏过程如下。（1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。（2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。 （3）按以上的方法依次类推。 }result = Josephus(55,4)print("最后剩下的是第",result["lastData"],"人")print("淘汰顺序为",result["delData"]) 3 结语 本文介绍了约瑟夫环的问题来历，以及如何使用Python设计程序解决约瑟夫环，并且进行了拓展，使该程序能应用于更多相似的问题。
37330编辑于 2023-08-22 - 来自专栏P_M_P学习笔记
约瑟夫问题
约瑟夫问题： 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。 返回头节点的话还需要遍历链表 } int iceBreakingGame(int num, int target) { ListNode* prev=CreateList(num); //进行约瑟夫游戏 算法 我们将上述问题建模为函数 f(num, target)，该函数的返回值为最终留下的元素的序号。
31010编辑于 2024-01-19 - 来自专栏软件工程
约瑟夫问题
题目:约瑟夫问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。现在需要求的是最后一个出局的人的编号。 注意: 这里判断新的起始位置时候需要用当前位置重新对链表长度取余得方式,因为这里不确定是否需要从头开始 测试样例： 输入5 3 返回 4 思想: 数学方法判断取出数据得位置: getIndex=
47120编辑于 2021-12-22
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号