首页
学习
活动
专区
工具
TVP
发布

约瑟夫 python 实现

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

79910

约瑟夫约瑟夫思想运用题

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 原题链接和其他优选题解。

41310
您找到你想要的搜索结果了吗?
是的
没有找到

php解决约瑟夫算法实例分析

本文实例讲述了php解决约瑟夫算法。分享给大家供大家参考,具体如下: 今天偶遇一道算法题 “约瑟夫”是一个数学应用问题:一群猴子排成一圈,按1,2,…,n依次编号。...($monkeys , $m); 运行结果: 3猴子被踢掉了 6猴子被踢掉了 9猴子被踢掉了 2猴子被踢掉了 7猴子被踢掉了 1猴子被踢掉了 8猴子被踢掉了 5猴子被踢掉了...10猴子被踢掉了 4成为猴王了 方法二:线性表应用 最后这个算法最牛, 哦,是这样,每个猴子出列后,剩下猴子又组成了另一个子问题。...第一个出列猴子肯定是a[1]=m(mod)n(m/n余数),他除去后剩下猴子是a[1]+1,a[1]+2,…,n,1,2,…a[1]-2,a[1]-1,对应新编号是1,2,3…n-1。...假如知道了这个子问题(n-1个猴子)解是x,那么原问题(n个猴子)解便是:(x+m%n)%n=(x+m)%n。问题起始条件:如果n=1,那么结果就是1。

35951

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总结: 利用数学公式写算法就是牛

677120

Josephu(约瑟夫约瑟夫) 问题

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

77540

约瑟夫问题链表实现(Java)

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

37010

约瑟夫 OJ

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

33710

算法 | 约瑟夫

从第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猴子,那么我们要怎么实现呢?...总结 通过一周学习又增加了自己知识储备,在解题过程中需要不断思索,算法我现在对他定义是一种解题步骤——思路和公式。也许看书、看视频我们会觉得算法不就如此吗?

70320

约瑟夫问题

以前写程序,今天在整理文件时候发现了,贴出来有需要朋友可以参考! 问题提出: 约瑟夫是一个数学应用问题:已知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!

61120

细究“约瑟夫

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 结语 约瑟夫是一个很经典数学问题...,其中解法多种多样,通过这种复杂循环可以使我们很轻松解决一些问题。

45220

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

一开始人选一个正整数作为报数上线值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); //运行约瑟夫问题

29620

【算法】约瑟夫问题解析与实现

本篇博客将详细解析约瑟夫问题,并使用 Python 实现算法。 问题分析 在约瑟夫问题中,有两个变量需要确定:人数 n 和报数数字 m。当给定 n 和 m 后,需要确定最后留下的人编号。...解决方案 解决约瑟夫问题一种常见思路是使用循环链表。首先,我们可以创建一个循环链表,并将人编号作为节点值。...下面是使用 Python 实现约瑟夫问题代码: class Node: def __init__(self, value): self.value = value self.next =...下面列出了几种常见解决方案: 1. 数学公式法 约瑟夫问题解决可以通过数学公式来推导。...总结 本篇博客详细解析了约瑟夫问题,并使用 Python 实现了一个基于循环链表解决方案。通过使用循环链表,我们可以模拟约瑟夫问题过程,找到最后留下的人编号。

41920
领券