实现约瑟夫环的实例 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

约瑟夫环 python 实现

面试的过程中遇到了这个问题。就是经典的约瑟夫环。总共有41个人，排成一排，数到3的人自杀，问最后剩下的是那两个号码？这个题目最早是用指针实现的。...在我面试python的过程中遇到了，我嫌麻烦，所以只写了伪代码。后来想来一下，这样实在是表现太差劲啊。python是很方便的，为什么非要用指针去实现呢，这也表现出我对语言的实用不熟练吧。...这也是我面试过程中表现最突出的问题。好吧，分析一下，其实很简单，就是数数，只不过死去的人不参与计数。只需要建一个死人的list，然后在从活人的list中循环数，知道剩下2个人，就是输出结果。...下面是实现过程。...3: ans(p) for i in p: if i not in dead: print i, 其实用python 还是很容易实现的

8571 0

Golang实现算法-约瑟夫环

什么是约瑟夫环约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。...最终胜利者是C图片普通算法使用Golang中的切片，来模拟约瑟夫环。通过cur游标来确定本轮次被踢出的元素，类似于丢手绢，丢到谁后，谁出局。当curl超过切片长度时，从头开始计算cur的值。...此方法，相对于链表省去了由M带来的时间复杂度。...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总结：利用数学公式写的算法就是牛

80612 0

您找到你想要的搜索结果了吗？

是的

没有找到

【约瑟夫环】约瑟夫环思想运用题

Tag : 「动态规划」、「数学」、「约瑟夫环」列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。...也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。给你整数 n，返回 arr 最后剩下的数字。..., 3, 4, 5, 6, 7, 8, 9] arr = [2, 4, 6, 8] arr = [2, 6] arr = [6] 示例 2：输入：n = 1 输出：1 image.png 约瑟夫环...在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。...在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

4481 0

Josephu(约瑟夫、约瑟夫环) 问题

单向环形链表应用场景 Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。...提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从...更通俗的说，他就是一个圆形蛋糕，分成四份的话，我们有两个指针，一个指向第一块，一个指向最后一块，然后他们一起移动，后指针永远在前指针的后面做好对接的准备。约瑟夫问题-创建环形链表的思路图解 ?...约瑟夫问题-小孩出圈的思路分析图 ? 我自己画了一个图 ?

8434 0

单向链表实现约瑟夫环

构建一个单项的环形链表思路先创建第一个节点，让first指向该节点，并形成环形后面当我们每创建一个新的节点，就把该节点加入到已有的环形链表中即可。...{ Id = id; } public PersonNode NextPerson { get; set; } } /// /// 创建一个环形的单向链表.../// public class MyJoseph { //创建一个头节点，不包含任何意义的数据 private PersonNode first = new PersonNode...currentNode.NextPerson = person; //将新增的节点指向第一个节点完成闭环...person.NextPerson = first; //改变当前节点的位置 currentNode = person;

3182 0

python实现约瑟夫环问题

大家好，又见面了，我是你们的朋友全栈君。 #!

3451 0

约瑟夫环的解法

arrayList.remove(0)); count++; } } //打印 System.out.print("输出的约瑟夫数是...//创建list1集合存放约瑟夫数 LinkedList list1 = new LinkedList(); //把序号添加到list集合中 for (int...// continue; } else { list.add(list.removeFirst());///把不是约瑟夫数的序号往后添加...count++;//报数加1 } } //打印，约瑟夫数 System.out.print("输出的约瑟夫数是...：" + list1); } } 解法三： import java.util.Scanner; //顺序表实现约瑟夫数 public class sequence_table { private

3682 0

约瑟夫环问题链表实现（Java）

面试中可能经常会遇到约瑟夫环问题，逻辑上很简单，就是看怎么实现了，一般而言，最简单最直观的就是利用链表，然后构建一个循环结构，正好是环，最后计算出结果。...遍历环形链表会是一个无限循环，如果链表中的数据逐渐减少，不控制终究会一个不剩，这又不满足我们问题的求解，因此我们需要定义出循环结束的条件，按照约瑟夫环的规则，只剩下一个的时候就结束，在环形链表结构中，那就是结点本身的下一个节点就是它自己...这里给出Java版本的实现： package com.xxx.algorithm.wh; //约瑟夫环java实现 //约瑟夫环问题的起源来自犹太历史学家约瑟夫和他的朋友以及39其余的犹太人，总共41人为了躲避敌人...count(4); //41个人为例，就是约瑟夫环的本身了，最后剩下的是31 count(41); } } class Node{ int data; Node next; public...，也验证了约瑟夫环的本身的结论。

4441 0

约瑟夫环

1 问题如何利用python设计程序，解决约瑟夫环的问题。 2 方法已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。....从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。....（3）按以上的方法依次类推。...count) return { "lastData":ls1[0], "delData":ls2 }result = Josephus(55,4)print("最后剩下的是第...",result["lastData"],"人")print("淘汰顺序为",result["delData"]) 3 结语本文介绍了约瑟夫环的问题来历，以及如何使用Python设计程序解决约瑟夫环

2033 0

约瑟夫环 OJ

大家好，又见面了，我是你们的朋友全栈君。...循环链表的应用，并且应为不带头节点的循环链表，首先创建一个循环链表，在函数JOHEPHUS中进行操作，主要就是用for找到要删除的元素（注意p==1单独考虑，for中p至少为2），删除元素并输出直至链表为空...for(j=1;j的位置和寻找要删除的节点的前驱结合在一个循环中，减少时间复杂度，因为第一次写我是在主函数中用r指向找到的要删除的节点，然后传入delete(&L,r)中删除...，而在delete中，需要从头找r的前驱，再修改指针，会发现这其中两个寻找的过程是重复进行的，所以基于函数功能的思想将它结合在一起，放入JOHEPHUS中，第一次写加入了initList，但由于没有头节点

3651 0

算法 | 约瑟夫环

从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？...解决方案解题思路：我们首先将N只猴子从1-N进行编号存到列表L里面，既然有N只猴子那么就要进行N-1次报数最后剩余一只猴子，接着我们来解决环问题，我们将猴子由1到N编号对应的索引是由0到N-1。...第一次报数由编号为1的猴子开始往后数3次编号为3索引为2的猴子退出，我们将索引为2的猴子从列表L中删除，之后更新列表编号在3之后的猴子的索引全部减1；第二次报数由编号为4的猴子依次往后报数，编号为6索引为...，那么退出的将会是编号为2索引为1的猴子，那么我们要怎么实现呢？...总结通过一周的学习又增加了自己的知识储备，在解题的过程中需要不断的思索，算法我现在对他的定义是一种解题的步骤——思路和公式。也许看书、看视频我们会觉得算法不就如此吗？

7502 0

约瑟夫环问题

一、问题描述约瑟夫环问题是一个很经典的问题：一个圈共有N个人（N为不确定的数字），按顺序第一个人的编号为1，第二个人的编号为2，第三个人的编号就为3，以此类推第N个人的编号就为N，现在提供一个数字K，...举一个简单的例子：假设一个圆桌上有8个人，即N的值为8，他们在进行一个小游戏，从第一个人开始报数，报到3的（即K的值为3），需要喝酒，喝的醉为止，喝醉后出局不能再喝，求出他们喝醉人的顺序。...答案是：3 6 1 5 2 8 4 7 分析：如上图所示，圈内的数字代表每个人的编号，从1开始编号到8。圈中的数字代表出局的人数，黑色的是已经喝醉出局的人。...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

1131 0

约瑟夫环问题

以前写的程序，今天在整理文件的时候发现了，贴出来有需要的朋友可以参考！问题提出：约瑟夫环是一个数学的应用问题：已知n个人（以编号0，2，3...n-1分别表示）围坐在一张圆桌周围。...从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。解决方案：约瑟夫环有递归和非递归两种解决方案。 1....下面给出用数组解决的源码： namespace JosephusRing { class Josephus { public int[] Jose(int total...int[] result = new int[total];//定义存储出列顺序的数组 int count = 0;//定义出列的计数器 //people...先来看一下递归函数：为了简化问题，我们假设k=0，设f(n,m,i)为n个人的环，报数为m，第i个人出环的编号当i=1时，f(n,m,i) = (m-1)%m 当i!

6472 0

细究“约瑟夫环”

2 算法描述解题思路：首先因为考虑到是不断的有规律退出数字则首先要考虑到循环的使用，我们从索引上看，如果将每次循环的三人看成一组，则被退出的人的索引为2，此时我们就知道了我们删去的就应该是索引为2的人...我们又举123为例，若想得到1，我们可以有很多的做法，而取余则是一种很巧的运算方式，如：“1”的位置是1，所以0%3（3是这三个值的长度（1,2,3））得到0，而1 的索引就是0，同理我们可得其他的值。...（简单讲就是本事索引除以长度得到自身位置，本身长度加1除以长度得到下一个位置，同理加2） 3 实验结果与讨论通过编程最终求出了约瑟夫环的问题。...len(list1) == 1: break list1.pop(k) k += 2 k %= len(list1) print(list1[0]) 4 结语约瑟夫环是一个很经典的数学问题...，其中的解法多种多样，通过这种复杂的循环可以使我们很轻松的解决一些问题。

5082 0

Java实现约瑟夫环问题「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。...从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。...System.out.print("请输入总人数："); int totalNum = scanner.nextInt(); System.out.print("请输入报数的大小...int k = 0; while (start.size() > 0) { k = k + countNum; // 第m人的索引位置

4931 0

# R语言——约瑟夫环

约瑟夫环: n个人围成一个圈,从第一个人点名,每数到第三个人,这个人移出圈外, 依次类推,求最后留下来的人编号是?...思路：每次循环重新编码序号作为names,并根据names 进行筛选拓展：约瑟夫环的关键点——每次循环数&最后留下的人数；代码中的整除数即为每次循环数，循环条件即为最后留下的人数 Survive_No...并转换成numerical格式 all 的整数倍的元素，即留下的人编号...names(all) <- 1:length(all)+end_names%%3 #生成新的names，从上一次末尾的names【整除3的余数加1】开始，到新all的长度 } unname...(all) #输出去除names的变量 } Survive_No(100000)

2872 0

约瑟夫环（排成圈）

/** * 约瑟夫环问题主要是考虑下标问题，只要解决了下标控制问题，这个题目就不难了 * 在这里我是分成了3中情况： * 1，下标小于剩余人数时：删除当前元素，并将下标后移 * 2....下标大于剩余人数时：用下标对剩余人数取于，删除元素，并下移下标 * 3.下标等于剩余人数或者是剩余人数的倍数的时候：移除最后一个元素，并让下标后移 */ 1 import java.util.LinkedList

4182 0

Python|约瑟夫环算法

（模拟此过程，输出出圈的人的序号）解决方案这道题涉及到的算法叫做“约瑟夫算法”，我们需要将列表内所有人类似排列成一个“圈”来解决，需要将前一次删除后剩下的元素的索引不变，但是位置向前提。...这道题的关键在于如何将每个数的索引数字固定，在删除前一个数字后，后面的数字都应该在排序中加一。所以我们一开始需要创建一个列表，从1开始到含有位数的数字，代表每个数字的索引列表。...del location_list[index] if index == 0: index = 0 print( "最后剩下的为...：",location_list[0]) Josephus_problem(5,3) 结语这道题的解决方法有很多种，这里主要介绍一下这种算法。

1.2K1 0

约瑟夫环问题(单向循环链表实现)

一开始人选一个正整数作为报数上线值m,从第一个人开始按顺时针方向自1报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去...这个游戏的实现只需将每个人的信息作为一个结点，节点中存放每个人的编号和密码，由于要反复做删除操作，所以采用单项循环链表实现较为方便。...编程实现： #include #include #define MAX 100 typedef struct NodeType { int id;...NodeType *);//打印循环链表 int isEmptyList(NodeType *);//测试链表是否为空 void JosephusOperate(NodeType **,int);//运行约瑟夫环问题...//打印循环链表 printf("\n-----------------打印出队情况---------------\n"); JosephusOperate(&pHead,m); //运行约瑟夫环问题

3842 0

约瑟夫环问题详解

在牛客网上做到一道题，是约瑟夫环的变型，所以借此学习一下新知识，并且巩固一下对题目意思的理解，这一篇仅作约瑟夫环问题的解释，下一篇再写题目： ##1.首先，我们先来了解一下什么是约瑟夫环问题：讲一个比较有意思的故事...##2.这就是约瑟夫环问题，接下来我们说个特例初步了解下这种问题的求解思路：特例：2，当q = 2时候，是一个特例，能快速求解特例还分两种 ###1.思路：注意这里的前提是n = 2^k(也就是...q个人约定： Jq(n)表示n人构成的约瑟夫环，每次移除第q个人的解 n个人的编号从0开始至n-1 我们沿用之前特例的思想：能不能由Jq(n+1)的问题缩小成为J(n)的问题（这里的n是n+1规模的约瑟夫问题消除一个元素之后的答案...，应该联想到是否是约瑟夫环问题，方便求解。...此文章重新整理在约瑟夫环问题详解里了，修改了之前写过程中存在的一些错误，并添加了一些新的推导过程，谢谢指出错误之处.

4281 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭