约瑟夫环(Josephus Problem)是一个经典的数学问题,涉及一个编号为 1 到 n 的人围成一圈,从第一个人开始报数,报到某个数字 m 的人出列,然后再从下一个人开始报数,如此循环,直到所有人都出列。本篇博客将详细解析约瑟夫环问题,并使用 Python 实现算法。
在牛客网上做到一道题,是约瑟夫环的变型,所以借此学习一下新知识,并且巩固一下对题目意思的理解,这一篇仅作约瑟夫环问题的解释,下一篇再写题目:
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?
约瑟夫问题,相信对有一点数学或者信息学竞赛背景的同学应该都不会很陌生,这是数学竞赛中常见的一个考题背景以及数据结构中用循环链表建模的一个代表性应用。而我懵懂地第一次接触到它居然是在一个魔术流程里,那是我小学时候的事了。而当我很多年以后再在数学和计算机的书上看到它时,竟然有一种从心头涌动的兴奋。于是,我决定从多个视角来回顾一番,并从数学模型,数据结构,数学推导,以及用到这个原理的若干魔术几个角度,来共同探讨这一古老又迷人的议题。
面试中可能经常会遇到约瑟夫环问题,逻辑上很简单,就是看怎么实现了,一般而言,最简单最直观的就是利用链表,然后构建一个循环结构,正好是环,最后计算出结果。
约瑟夫游戏的大意:30个游客同乘一条船,因为严重超载, 加上风浪大作,危险万分。因此船长告诉乘客,只有将全船 一半的旅客投入海中,其余人才能幸免于难。无奈,大家只 得同意这种办法,并议定30 个人围成一圈,由第一个人数起,依次报数,数到第9人,便把他投入大海中,然后再从 他的下一个人数起,数到第9人,再将他投入大海中,如此 循环地进行,直到剩下 15 个游客为止。问:哪些位置是将 被扔下大海的位置?
题目: 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号0,1,2,3…n-1分别表示)围坐在一张圆桌周围。从编号为0的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,求最后一个出列的人。
题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&
思路: 用链表模拟约瑟夫环,每次要删除的地方应该是当前索引加上要走的步数,由于我们不要转n圈,所以这可以对链表长度取余,1圈内就找到要删除的位置;
本文实例讲述了PHP使用栈解决约瑟夫环问题算法。分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀。然后下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
哦,是这样的,每个猴子出列后,剩下的猴子又组成了另一个子问题。只是他们的编号变化了。第一个出列的猴子肯定是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。设此时某个猴子的新编号是i,他原来的编号就是(i+a[1])%n。于是,这便形成了一个递归问题。假如知道了这个子问题(n-1个猴子)的解是x,那么原问题(n个猴子)的解便是:(x+m%n)%n=(x+m)%n。问题的起始条件:如果n=1,那么结果就是1。
给定一个从 到 排序的整数列表。首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。返回长度为 的列表中,最后剩下的数字。
约瑟夫环原理运作如下: N个人围在一起坐成环状 从K编号开始报数 数到某个数M的时候,此人出列,下一个人重新报数 一直循环,直到所有人出列,约瑟夫环结束 joselooplink.c(编译环境: Ubuntu18.04 ,Vim) #include <stdio.h> #include <stdlib.h> typedef struct node /*头指针型约瑟夫环*/ { int item; struct node *next;
Josephu 问题为:设编号为 1,2,… n 的 n 个人围坐一圈,约定编号为 k(1<=k<=n)的人从 1 开始报数,数 到 m 的那个人出列,它的下一位又从 1 开始报数,数到 m 的那个人又出列,依次类推,直到所有人出列为止,由
约瑟夫问题是个著名的问题:N个人围成一圈,第一个人从1开始报数,报M的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个,求最后的胜利者。
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知 n 个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为 k 的人开始报数,数到 m 的那个人出圈;他的下一个人又从 1 开始报数,数到 m 的那个人又出圈;依此规律重复下去,直到剩余最后一个胜利者。
约瑟夫环问题请参考: Python版本的报数游戏 微课|中学生可以这样学Python(例5.3):报数游戏 使用Python列表方法模拟约瑟夫环问题 问题描述: 使用约瑟夫环生成伪随机数。 技术
已知 n 个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。. 从编号为 k 的人开始报数,数到 m 的那个人出圈;他的下一个人又从 1 开始报数,数到 m 的那个人又出圈;依此规律重复下去,直到剩余最后一个胜利者。. 例如:有10个人围成一圈进行此游戏,每个人编号为 1-10 。. 若规定数到 3 的人出圈。. 则游戏过程如下。(1)开始报数,第一个数到 3 的人为 3 号,3 号出圈。(2)从4号重新从1开始计数,则接下来数到3的人为6号,6号出圈。(3)按以上的方法依次类推。
约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在城市沦陷之后,他和40名死硬的将士在附近的一个洞穴中避难。在那里,这些叛乱者表决说“要投降毋宁死”。于是,约瑟夫建议每个人轮流杀死他旁边的人,而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签,并且,作为洞穴中的两个幸存者之一,他说服了他原先的牺牲品一起投降了罗马。 约瑟夫环问题的具体描述是:设有编号为1,2,……,n的n(n>0)个人围成一个圈,从第1个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。
约瑟夫环问题是算法中相当经典的一个问题,其问题理解是相当容易的,并且问题描述有非常多的版本,并且约瑟夫环问题还有很多变形,这篇约瑟夫问题的讲解,一定可以带你理解通通!
约瑟夫环问题(Josephus problem)是一个古老而经典的数学问题。问题的场景通常是有n个人(编号从1到n)站在一个圆形排列的位置上。接下来,从第一个人开始,每隔k个人就删除一个人,然后重新开始数,直到所有人都被删除。问题的目标是确定最后剩下的那个人的编号。
在牛客上跑通过了,本着追求机器效率的原则,去leetcode上找到了同样的题,再跑了一遍,发现超时。看了几篇博客并思索许久后打算写这篇博客来探究
正如文章 Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List 中所言,链表这种数据结构非常像电视节目里的 寻宝游戏 —— 而不是 火车。
原文链接: 具体数学-第2课 - WeiYang Bloggodweiyang.com 今天主要讲了关于递推式和求和的一些方法,主要是成套方法。 约瑟夫环推广 上一节课说到,约瑟夫环问题的解是 其
昨晚春晚上刘谦的两个魔术表演的都非常 nice,其中第二个魔术就是非常经典的约瑟夫环问题!
https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tab=note
今年春晚刘谦的魔术堪称惊艳全场,那么他这个魔术实现的原理是什么呢?今天,就让咱们使用 JS 是实现这个魔术。
从判断一个单链表是否存在循环而扩展衍生的问题,有则称之为有环链表问题,也就是经典的约瑟夫问题,也称为约瑟夫环。
在上一篇文章中,我们聊到了约瑟夫问题的定义,以及其用环的数学模型来建模,最后用循环单链表的数据结构解决该问题等内容。这些只是基本内容,当我们有了数学模型把这个问题变成数学问题以后,就可以在数学结构内去研究更多的东西,而不局限于仅仅求出最后那个被杀的人,比如:
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
## 题目: 设有 n 个人围坐在圆桌周围,现从某个位置 k 上的人开始报数,报数到 m的人就站出来。下一个人,即原来的第 m+1m+1 个位置上的人,又从 11 开始报数,再报数到 mm 的人站出来。依次重复下去,直到全部的人都站出来为止。试设计一个程序求出这 nn 个人的出列顺序。
原文链接: 具体数学-第8课 - WeiYang Bloggodweiyang.com 今天主要讲了取整与递归式的结合,还有取模的相关知识。 例题1 给出下列递归式: 现在不要求你求解,要你证明:
约瑟夫环: n个人围成一个圈,从第一个人点名,每数到第三个人,这个人移出圈外, 依次类推,求最后留下来的人编号是? 思路:每次循环重新编码序号作为names,并根据names 进行筛选 拓展:约瑟夫
设编号为1,2,3,...n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
这学期提前选修了研究生的课程:具体数学、人工智能前沿、NLP讨论班,就随便记记具体数学每一节课所学的东西吧。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/172079.html原文链接:https://javaforall.cn
这是我们「刷穿 LeetCode」系列文章的第 No.390 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
Introduction of How to submit PHP code to Online Judge Systems
本文实例讲述了PHP环形链表实现方法。分享给大家供大家参考,具体如下: 环形链表是一种链式存储结构,类似于单链表。区别是环形链表的尾节点指向头节点。 从而形成一个环, 环形链表是一种非常灵活的存储结构,可解决许多实际问题,魔术师发牌问题和约瑟夫问题 都能利用环形链表来解决,下面是一个完整的环形链表实例,使用php来实现的(参照韩顺平老师的php算法教程)
0,1,…,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
约瑟夫环问题算是很经典的题了,估计大家都听说过,然后我就在一次笔试中遇到了,下面我就用 3 种方法来详细讲解一下这道题,最后一种方法学了之后保证让你可以让你装逼。
有时候,队列会有优先级。比如 VIP 用户总是比普通用户服务优先一些,头等舱总比经济舱要好。实现这样一功能需要在原来的队列基础上加上优先级:当 push 操作时,我们可以传入两个参数,第一个为数据,第二个是优先级大小(数字类型),传入的数值越大优先级越高。
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:15个教徒和15 个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。
约瑟夫环是一个数学的应用问题:已知n个人(以编号0,2,3...n-1分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 解决方案: 约瑟夫环有递归和非递归两种解决方案。 1. 非递归可用数组和循环链表来解决。下面给出用数组解决的源码:
春节假期这么长,干啥最好?当然是折腾一些算法题了,下面给大家讲几道一行代码就能解决的算法题,当然,我相信这些算法题你都做过,不过就算做过,也是可以看一看滴,毕竟,你当初大概率不是一行代码解决的。
0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。
在前面的三篇文章中,我们完成了约瑟夫问题数学部分的解析,相信已经令数学爱好者们大呼过瘾,让魔术爱好者们一头雾水了,相关内容请戳:
领取专属 10元无门槛券
手把手带您无忧上云