- 综合排序
- 最热优先
- 最新优先
- 来自专栏算法与编程之美
算法 | 约瑟夫环
欢迎点击「算法与编程之美」↑关注我们！ 本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。 问题描述 猴子选大王，让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。 第一次报数由编号为1的猴子开始往后数3次编号为3索引为2的猴子退出，我们将索引为2的猴子从列表L中删除，之后更新列表编号在3之后的猴子的索引全部减1； 第二次报数由编号为4的猴子依次往后报数，编号为6索引为 4猴子退出，之后再次更新列表同理编号在6之后的猴子的索引全部减1； 到这里我们还是没有较多的头绪，那么我们再往后推两次。 第三次报数编号为9索引为6的猴子退出，编号为10的猴子索引再次减1； 第四次报数由编号为10的猴子开始，但是在列表中10号猴子的后面没有猴子可以继续数数，到这里我们不妨思考一下如果列表尾部接着列表的头部 总结 通过一周的学习又增加了自己的知识储备，在解题的过程中需要不断的思索，算法我现在对他的定义是一种解题的步骤——思路和公式。也许看书、看视频我们会觉得算法不就如此吗？
93220发布于 2019-07-17 - 来自专栏算法与编程之美
Python|约瑟夫环算法
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。 （模拟此过程，输出出圈的人的序号） 解决方案 这道题涉及到的算法叫做“约瑟夫算法”，我们需要将列表内所有人类似排列成一个“圈”来解决，需要将前一次删除后剩下的元素的索引不变，但是位置向前提。 0 print( "最后剩下的为：",location_list[0]) Josephus_problem(5,3) 结语 这道题的解决方法有很多种，这里主要介绍一下这种算法
1.3K10发布于 2020-02-13 - 来自专栏爱编码
经典算法之约瑟夫问题
当n，m数据量很小的时候，我们可以用循环链表模拟约瑟夫环的过程。当模拟到人数等于1的时候，输出剩下的人的序号即可。 具体解法这种方法往往实现起来比较简单，而且也很容易理解。 ） 可能以上过程你还是觉得不太清晰，那么我们重复以上过程，继续推导剩余的n-1个人的约瑟夫环的问题： 那么在这剩下的n-1个人中，我们也可以为了方便，将这n-1个人编号为： 0,1,2,3,4...n- 后面的过程与前两次的过程一模一样，那么递归处理下去，直到最后只剩下一个人的时候，便可以直接得出结果 当我们得到一个人的时候（即一阶约瑟夫环问题）的结果，那么我们是否能通过一阶约瑟夫环问题的结果，推导出二阶约瑟夫环的结果呢 借助上面的分析过程，我们知道，当在解决n阶约瑟夫环问题时，序号为k1的人出列后，剩下的n-1个人又重新组成了一个n-1阶的约瑟夫环，那么 假如得到了这个n-1阶约瑟夫环问题的结果为ans（即最后一个出列的人编号为 ans），那么我们通过上述分析过程，可以知道，n阶约瑟夫环的结果 (ans + k)%n(n为当前序列的总人数)，而k = m%n 则有： n阶约瑟夫环的结果 (ans + m % n)%n，那么我们还可以将该式进行一下简单的化简
2K10发布于 2019-11-14 - 来自专栏算法协议
Golang实现算法-约瑟夫环
什么是约瑟夫环约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。 最终胜利者是C图片普通算法使用Golang中的切片，来模拟约瑟夫环。通过cur游标来确定本轮次被踢出的元素，类似于丢手绢，丢到谁后，谁出局。当curl超过切片长度时，从头开始计算cur的值。 m - 1}arr = append(arr[:cur], arr[cur+1:]...)if cur >= len(arr) {cur -= len(arr)}}return arr[0]}公式递归约瑟夫环公式 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分别表示）围坐在一张圆桌周围。 1， 2， 【3】， 4， 5， 6， 7， 8， 9， 10。 （2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。 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。 （6）从8号重新从1开始计数，则接下来数到3的人为1号，1号出圈。 >next = p; q = p; } q->next = head;//末尾节点指向头结点，构成循环链表 return head; } /*模拟运行约瑟夫环
1.5K20发布于 2019-05-06 - 来自专栏MyTechnology
Josephu(约瑟夫、约瑟夫环) 问题
单向环形链表应用场景 Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束 约瑟夫问题-创建环形链表的思路图解 ? 约瑟夫问题-小孩出圈的思路分析图 ? 我自己画了一个图 ?
99940发布于 2021-01-18 - 来自专栏cwl_Java
C++经典算法题-约瑟夫问题
26.Algorithm Gossip: 约瑟夫问题（Josephus Problem） 说明 据说着名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus 解法 约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与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; } /** * 约瑟夫递归算法 return t; } public static void main(String[] args) { // int n = 500; int m = 3; //约瑟夫标准循环非递归解法 n得出的结论， */ /* *f(1) = 0;//第0个 *f(2) = 1;//第1个 *f(3) = 1;//第2个 * */ //參考上面的提示写了下约瑟夫的递归算法
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 解决方案 解决约瑟夫环问题的一种常见思路是使用循环链表。首先，我们可以创建一个循环链表，并将人的编号作为节点的值。 链表法 除了使用循环链表，我们还可以使用普通的链表来解决约瑟夫环问题。首先，我们创建一个链表，将人的编号依次加入到链表中。 总结 本篇博客详细解析了约瑟夫环问题，并使用 Python 实现了一个基于循环链表的解决方案。通过使用循环链表，我们可以模拟约瑟夫环问题的过程，找到最后留下的人的编号。
1.8K20编辑于 2023-10-12 - 来自专栏宫水三叶的刷题日记
【约瑟夫环】约瑟夫环思想运用题
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个犹太人决定宁愿死也不要被敌人抓。
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- >6 ] 将它们合并到一个有序链表中得到。 【链表应用】约瑟夫问题 上面铺垫了那么多 其实也只是为了解决问题而做的嘛 那么现在我们来面对一个实际的问题 约瑟夫问题 （典中典了属于是） 约瑟夫问题（Josephus Problem）是一个经典的数学问题
33510编辑于 2024-03-01 - 来自专栏JavaEE
约瑟夫问题
一、约瑟夫问题介绍 1、约瑟夫问题原题： n个小孩子手拉手围成一个圈，编号为k(1 <= k <= n )的人从1开始报数，报到m的那个人出列，它的下一位又从1开始报数，报到m的又出列……依此类推，直到所有人都出列 2、代码实现： 根据上面的分析，可以写出如下代码： package com.zhu.study.linkedList; /** * 约瑟夫问题，即单向循环链表问题 * @author: zhu
63720发布于 2020-09-08 - 来自专栏全栈程序员必看
经典算法–约瑟夫环问题的三种解法
约瑟夫环问题，这是一个很经典算法，处理的关键是：伪链表 问题描述：N个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈。 （模拟此过程，输出出圈的人的序号） 在数据结构与算法书上，这个是用链表解决的。我感觉链表使用起来很麻烦，并且这个用链表处理起来也不是最佳的。 ，为总人数-1 int *circle = NULL; //根据需求设为循环数组，存储每个人 //用calloc()函数申请得到的空间，自动初始化每个元素为0 //所以，0表示在这个人在约瑟夫环内 curIndex = circle[curIndex]; // 继续处理下一个人 } // 这个算法比normalJoseph.c效率提高30%！
1.3K40编辑于 2022-09-05 - 来自专栏算法与编程之美
约瑟夫环
1 问题 如何利用python设计程序，解决约瑟夫环的问题。 2 方法 已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。. （2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。（3）按以上的方法依次类推。 = 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的人出局。现在需要求的是最后一个出局的人的编号。
47120编辑于 2021-12-22 - 来自专栏算法与编程之美
约瑟夫小游戏
+=1 if check == 9: people[i]=0 check = 0 print("{}号下船了".format(i)) j+=1 else: i+=1 continue 3 结语 针对‘约瑟夫小游戏
24710编辑于 2024-07-05 - 来自专栏ljw
约瑟夫环问题
一、问题描述 约瑟夫环问题是一个很经典的问题：一个圈共有N个人（N为不确定的数字），按顺序第一个人的编号为1，第二个人的编号为2，第三个人的编号就为3，以此类推第N个人的编号就为N，现在提供一个数字K， 答案是：3 6 1 5 2 8 4 7 分析：如上图所示，圈内的数字代表每个人的编号，从1开始编号到8。圈中的数字代表出局的人数，黑色的是已经喝醉出局的人。 ，6号出局之后，要从出局的这个人（6号）的下一个未出局的人（7号）重新开始从1开始报数，所以7号从1开始继续报数，那么，第三个出局的人就是1号，1号出局之后，要从出局的这个人（1号）的下一个未出局的人（ 1：代码 #include<stdio.h> //约瑟夫环 int main() { int ren=0;//人数 int k=0;//报数 int sum=8; int arr[100] 1：可以直接输入想报到几出局，以及想要得总人数 #include<stdio.h> //约瑟夫环 int main() { int ren=0;//人数 int k=0;//报数 printf
42810编辑于 2024-10-18
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号