- 综合排序
- 最热优先
- 最新优先
- 来自专栏宫水三叶的刷题日记
【约瑟夫环】约瑟夫环思想运用题
Tag : 「动态规划」、「数学」、「约瑟夫环」 列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。 示例 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 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2)); } } image.png 最后 这是我们「刷穿 LeetCode」系列文章的第 No.390 篇，
60710编辑于 2022-05-27 - 来自专栏MyTechnology
Josephu(约瑟夫、约瑟夫环) 问题
单向环形链表应用场景 Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 约瑟夫问题-创建环形链表的思路图解 ? 约瑟夫问题-小孩出圈的思路分析图 ? 我自己画了一个图 ? circleSingleLinkedList.showBoy(); //测试一把小孩出圈是否正确 circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->3 } } } class CircleSingleLinkedList { //创建一个first节点 private
99940发布于 2021-01-18 - 来自专栏算法与编程之美
约瑟夫环
1 问题 如何利用python设计程序，解决约瑟夫环的问题。 2 方法 已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。. （2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。（3）按以上的方法依次类推。 代码清单 1 def Josephus(data,step): ls1 = [i for i in range(1,data+1)] ls2 = [] num = 0 while = Josephus(55,4)print("最后剩下的是第",result["lastData"],"人")print("淘汰顺序为",result["delData"]) 3 结语 本文介绍了约瑟夫环的问题来历 ，以及如何使用Python设计程序解决约瑟夫环，并且进行了拓展，使该程序能应用于更多相似的问题。
37330编辑于 2023-08-22 - 来自专栏算法与编程之美
算法 | 约瑟夫环
解决方案 解题思路：我们首先将N只猴子从1-N进行编号存到列表L里面，既然有N只猴子那么就要进行N-1次报数最后剩余一只猴子，接着我们来解决环问题，我们将猴子由1到N编号对应的索引是由0到N-1。 第一次报数由编号为1的猴子开始往后数3次编号为3索引为2的猴子退出，我们将索引为2的猴子从列表L中删除，之后更新列表编号在3之后的猴子的索引全部减1； 第二次报数由编号为4的猴子依次往后报数，编号为6索引为 的猴子退出，编号为10的猴子索引再次减1； 第四次报数由编号为10的猴子开始，但是在列表中10号猴子的后面没有猴子可以继续数数，到这里我们不妨思考一下如果列表尾部接着列表的头部，那么退出的将会是编号为2索引为 我们不妨将第10只猴子的索引值加上3再对列表的长度求余数再减去1，发现正好是编号为2索引为1的猴子。 where2go 团队 ---- 微信号：算法与编程之美 温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！
93220发布于 2019-07-17 - 来自专栏全栈程序员必看
约瑟夫环 OJ
循环链表的应用，并且应为不带头节点的循环链表，首先创建一个循环链表，在函数JOHEPHUS中进行操作，主要就是用for找到要删除的元素（注意p==1单独考虑，for中p至少为2），删除元素并输出直至链表为空 LNode * s=(LNode * )malloc(sizeof(LNode)); (*s).num=1; (*s).next=s; (*L)=s; if(n>=2) { for(i=2;i<=n;i++) { LNode * w=(LNode * )malloc(sizeof(LNode)); (*w ; cur=(*cur).next; n–; } printf(“%d”,(*cur).num); } else//p>=2
55410编辑于 2022-09-02 - 来自专栏ljw
约瑟夫环问题
一、问题描述 约瑟夫环问题是一个很经典的问题：一个圈共有N个人（N为不确定的数字），按顺序第一个人的编号为1，第二个人的编号为2，第三个人的编号就为3，以此类推第N个人的编号就为N，现在提供一个数字K， ）重新开始从1开始报数，所以2号从1开始继续报数，那么第四个出局的人就是5号（2号报1，4号报2，5号报3，5号出局），5号出局之后，要从出局的这个人（5号）的下一个未出局的人（7号，这边6号已经出局了 ，不能报数，所以直接跳到7号）重新开始从1开始报数，那么第五个出局的人就是2号，2号出局之后，要从出局的这个人（2号）的下一个未出局的人（4号）重新开始从1开始报数，那么第六个出局的人就是8号，8号出局之后 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 - 来自专栏给永远比拿愉快
约瑟夫环问题
问题提出： 约瑟夫环是一个数学的应用问题：已知n个人（以编号0，2，3...n-1分别表示）围坐在一张圆桌周围。 解决方案： 约瑟夫环有递归和非递归两种解决方案。 1. 非递归可用数组和循环链表来解决。 Console.WriteLine(num); } Console.ReadKey(); } } } 2. 先来看一下递归函数： 为了简化问题，我们假设k=0，设f(n,m,i)为n个人的环，报数为m，第i个人出环的编号 当i=1时，f(n,m,i) = (m-1)%m 当i!
81420发布于 2019-01-25 - 来自专栏算法与编程之美
细究“约瑟夫环”
示例一： 输入：n = 3 输出：“2” 解释：首先轮流报数，3就被退出了，之后1,2,1,1就被退出了，最后只剩下了2。 2 算法描述 解题思路：首先因为考虑到是不断的有规律退出数字则首先要考虑到循环的使用，我们从索引上看，如果将每次循环的三人看成一组，则被退出的人的索引为2，此时我们就知道了我们删去的就应该是索引为2的人 根据规律可得，若k=2的值为删去的数，那么我们只需进行k = k+2得到下一个删去的值。 （简单讲就是本事索引除以长度得到自身位置，本身长度加1除以长度得到下一个位置，同理加2） 3 实验结果与讨论 通过编程最终求出了约瑟夫环的问题。 ) == 1: break list1.pop(k) k += 2 k %= len(list1) print(list1[0]) 4 结语 约瑟夫环是一个很经典的数学问题
65820编辑于 2021-12-15 - 来自专栏算法与编程之美
Python|约瑟夫环算法
（模拟此过程，输出出圈的人的序号） 解决方案 这道题涉及到的算法叫做“约瑟夫算法”，我们需要将列表内所有人类似排列成一个“圈”来解决，需要将前一次删除后剩下的元素的索引不变，但是位置向前提。
1.3K10发布于 2020-02-13 - 来自专栏用户3030674的专栏
约瑟夫环（排成圈）
/** * 约瑟夫环问题主要是考虑下标问题，只要解决了下标控制问题，这个题目就不难了 * 在这里我是分成了3中情况： * 1，下标小于剩余人数时：删除当前元素，并将下标后移 * 2. 用下标对剩余人数取于，删除元素，并下移下标 * 3.下标等于剩余人数或者是剩余人数的倍数的时候：移除最后一个元素，并让下标后移 */ 1 import java.util.LinkedList; 2
52720发布于 2018-09-14 - 来自专栏诡途的python路
# R语言——约瑟夫环
约瑟夫环: n个人围成一个圈,从第一个人点名,每数到第三个人,这个人移出圈外, 依次类推,求最后留下来的人编号是? 思路：每次循环重新编码序号作为names,并根据names 进行筛选 拓展：约瑟夫环的关键点——每次循环数&最后留下的人数；代码中的整除数即为每次循环数，循环条件即为最后留下的人数 Survive_No
39920编辑于 2022-05-09 - 来自专栏python3
约瑟夫环 python 实现
就是经典的约瑟夫环。总共有41个人，排成一排，数到3的人自杀，问最后剩下的是那两个号码？ 这个题目最早是用指针实现的。在我面试python的过程中遇到了，我嫌麻烦，所以只写了伪代码。 只需要建一个死人的list，然后在从活人的list中循环数，知道剩下2个人，就是输出结果。下面是实现过程。
95110发布于 2020-01-08 - 来自专栏后端开发笔记
约瑟夫环的解法
System.out.print("输入剔除的序号："); int n = zs.nextInt(); josephus(m, n); } //判断是否为约瑟夫数 int n) { //创建list集合存放人数的序号 LinkedList list = new LinkedList(); //创建list1集合存放约瑟夫数 count++;//报数加1 } } //打印，约瑟夫数 System.out.print("输出的约瑟夫数是 ：" + list1); } } 解法三： import java.util.Scanner; //顺序表实现约瑟夫数 public class sequence_table { private (int i = 0; i < n; i++) { if (size == initcapacity) { expansion(size * 2)
57820编辑于 2022-11-18 - 来自专栏全栈程序员必看
约瑟夫环问题详解
在牛客网上做到一道题，是约瑟夫环的变型，所以借此学习一下新知识，并且巩固一下对题目意思的理解，这一篇仅作约瑟夫环问题的解释，下一篇再写题目： ##1.首先，我们先来了解一下什么是约瑟夫环问题： 讲一个比较有意思的故事 ##2.这就是约瑟夫环问题，接下来我们说个特例初步了解下这种问题的求解思路： 特例：2，当q = 2时候，是一个特例，能快速求解 特例还分两种 ###1.思路：注意这里的前提是n = 2^k(也就是 1了 …… 定义J(n)为n个人构成的约瑟夫环最后结果，则有j(2^k) = 1 J(n) = 2^k – 2^k-1 = 2^k-1 n=2^k J(n) = 2^k-1 – 2^k So，我们在剔除了t（3）个元素之后（分别是2,4,6），此时我们定格在2t+1（7）处，并且将2t+1（7）作为新的一号，而且这时候的约瑟夫环只剩下23，也就是J(23 + 3) = 2*3 + 1 = 7，答案为7 总结一下这个规律： J(2^k + t) = 2t+1 ##3.说完了特例，现在说说q 不等于2的情况下： 当q ≠ 2： 我们假定： n — n人构成的约瑟夫环 q — 每次移除第
66610编辑于 2022-09-05 - 来自专栏数据结构与算法
约瑟夫环 队列+链表
设ｎ个人的编号分别为1，2，…，n，打印出列的顺序。 【算法分析】 本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。 当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点的前继结点指针指向其后继结点； 2、设立指针，指向当前结点，设立计数器，计数数到多少人； 3、沿链移动指针 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int a[10000001]; 5 int tot=1; 6
1.1K70发布于 2018-04-12 - 来自专栏算法协议
Golang实现算法-约瑟夫环
什么是约瑟夫环约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。 例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。首先A开始报数，他报1。侥幸逃过一劫。然后轮到B报数，他报2。 非常惨，他被杀了C接着从1开始报数接着轮到A报数，他报2。也被杀死了。最终胜利者是C图片普通算法使用Golang中的切片，来模拟约瑟夫环。 m - 1}arr = append(arr[:cur], arr[cur+1:]...)if cur >= len(arr) {cur -= len(arr)}}return arr[0]}公式递归约瑟夫环公式 ++ {res1 := f1(n, m)fmt.Println(res1)res2 := f2(n, m)fmt.Println(res2)res3 := f3(n, m)fmt.Println(res3
1K120编辑于 2023-02-16 - 来自专栏全栈程序员必看
python约瑟夫环「建议收藏」
第一次出队的那个人的编号是( m-1)%n ，第二次重新开始的编号是m%n 约瑟夫环是一个经典的数学问题，我们不难发现这样的依次报数，似乎有规律可循。为了方便导出递推式，我们重新定义一下题目。 问题： N个人编号为1，2，……，N，依次报数，每报到M时，杀掉那个人，求最后胜利者的编号。 这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。 class Solution: def LastRemaining_Solution(self, n, m): # write code here # 用列表来模拟环，
53610编辑于 2022-09-05 - 来自专栏C/C++
数据结构：约瑟夫环
约瑟夫环原理运作如下： N个人围在一起坐成环状 从K编号开始报数 数到某个数M的时候，此人出列，下一个人重新报数 一直循环，直到所有人出列，约瑟夫环结束 joselooplink.c（编译环境： Ubuntu18.04 ，Vim） #include <stdio.h> #include <stdlib.h> typedef struct node /*头指针型约瑟夫环 , p->item); p = p->next; } printf("%d ", p->item); printf("\n"); } void joseph_init(int n) /*约瑟夫环初始化 */ { int i; node *p = mk_node(1); head = p; tail = p; for (i = 2; i <= n; i++) { p = mk_node
43420编辑于 2022-11-15 - 来自专栏乐行僧的博客
29-约瑟夫环问题
代码 #include <stdio.h> /* 编号为 1，2，3，…，n 的 n 个人围坐一圈，任选一个正整数 m 作为报数上限值， 从第一个人开始按顺时针方向报数，报数到 m 时停止，报数为 m
61030编辑于 2022-02-25 - 来自专栏JusterZhu
单向链表实现约瑟夫环
//调用 MyJoseph myJoseph = new MyJoseph(); myJoseph.addPerson(5); myJoseph.Print(); myJoseph.Kill(1,2,5
43920编辑于 2022-12-07
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号