约瑟夫的问题？(具体数学)

约瑟夫的问题是一个经典的数学问题，也被称为约瑟夫环问题。问题的描述如下：假设有n个人围成一圈，从第一个人开始报数，报到m的人出列，然后从下一个人开始重新报数，再次报到m的人出列，如此循环，直到所有人都出列。问最后剩下的人在原始序列中的位置是多少？

这个问题可以通过数学推导和递归算法来解决。数学推导的结果是，当n和m固定时，最后剩下的人在原始序列中的位置可以通过以下公式计算得出：

f(n, m) = (f(n-1, m) + m) % n

其中，f(n, m)表示n个人中最后剩下的人在原始序列中的位置，%表示取余运算。当n=1时，f(n, m)的值为0。

约瑟夫的问题在实际应用中并不常见，但它可以帮助我们理解数学推导和递归算法的思想。在编程中，可以使用递归算法来解决约瑟夫的问题，具体步骤如下：

定义一个递归函数，传入参数为当前人数n和报数的m。
当n=1时，返回0，表示最后剩下的人在原始序列中的位置为0。
当n>1时，调用递归函数计算n-1个人中最后剩下的人在原始序列中的位置，记为x。
根据公式f(n, m) = (x + m) % n，计算出n个人中最后剩下的人在原始序列中的位置，并返回结果。

这样，我们就可以通过递归算法解决约瑟夫的问题。

腾讯云相关产品和产品介绍链接地址：

腾讯云函数（Serverless）：https://cloud.tencent.com/product/scf
腾讯云数据库（TencentDB）：https://cloud.tencent.com/product/cdb
腾讯云容器服务（TKE）：https://cloud.tencent.com/product/tke
腾讯云人工智能（AI）：https://cloud.tencent.com/product/ai
腾讯云物联网（IoT）：https://cloud.tencent.com/product/iotexplorer
腾讯云移动开发（移动推送）：https://cloud.tencent.com/product/umeng
腾讯云对象存储（COS）：https://cloud.tencent.com/product/cos
腾讯云区块链（BCS）：https://cloud.tencent.com/product/bcs
腾讯云虚拟专用网络（VPC）：https://cloud.tencent.com/product/vpc
腾讯云安全产品（云安全中心）：https://cloud.tencent.com/product/ssc

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

约瑟夫问题与魔术（三）——终极数学推导

前面文章我们介绍了约瑟夫问题，并给出了基本的数学模型，和其内部数学性质的分析。...今天我们接着上期的问题分析把整个过程的数学细节都描绘下来，注意今天的描绘的粒度是每一次对整个序列的遍历，而第一篇描述的时候是每一次行动。...所以这个函数恰好可以用高斯函数表达： f(n, k) = [k / (k - 1)((f(n’, k) - n % k)mod n’)] 于是，整个约瑟夫问题求解的，复杂度降低为O(klogn)的递归表达式如下...，我们找到了更深层次的约瑟夫问题的求解策略，大大降低了问题的时间复杂度。...以上就是约瑟夫问题数学部分的全部内容，从下一篇起，我们进入魔术部分，看看这一神奇的结构能够怎样配合上我们的魔术表演，去继续缔造属于我们的奇迹。

3861 0

约瑟夫问题与魔术（二）——数学结构解析

在上一篇文章中，我们聊到了约瑟夫问题的定义，以及其用环的数学模型来建模，最后用循环单链表的数据结构解决该问题等内容。...这些只是基本内容，当我们有了数学模型把这个问题变成数学问题以后，就可以在数学结构内去研究更多的东西，而不局限于仅仅求出最后那个被杀的人，比如：在约瑟夫问题中，我们还可以关心几个内容： 1....被移除的节点的顺序如何？ 2. 最后一个以及倒数若干个留下的节点编号是多少？本质上，我们希望对约瑟夫问题更细致地每一步到底发生了什么进行更细致的观察。...具体就是，到底一个原始环上的元素，是以怎样的排列顺序给移出去的，有怎样的规律，这个搞清楚了，其他的问题都是这个问题的子问题，包含于此。...接下来，我们再仔细分析一下约瑟夫问题的过程，看看这个结论为什么会成立。 约瑟夫问题通项公式理解原始的约瑟夫问题的每一步仅往后处理一个人，这也是前面代码模拟的思路。

6323 0

C#实现约瑟夫环数学问题

犹太士兵里有个人叫约瑟夫，他想投降保命但又不能明说。那么约瑟夫应该站在哪个位置上才能成为最后一个剩下的人？这样就不用自sha可以直接向罗马人投降。...在人数不多的情况下这个问题很好推算，假设总人数10人的前置条件。...约瑟夫没有那么多时间进行推算。把总人数和最终存活的位置整理成图表的话大致如下：最终我们发现，活下来的都是奇数位。...因为最先杀人的士兵都处在奇数位置，不管人数多少最先被kill掉的肯定是站在偶数位置上的人。也就是约瑟夫绝对不能站在偶数位置上。...C#代码 /// /// 约瑟夫一下 /// /// 总人数 ///

3171 0

约瑟夫问题与魔术（一）——数学模型求解

约瑟夫问题，相信对有一点数学或者信息学竞赛背景的同学应该都不会很陌生，这是数学竞赛中常见的一个考题背景以及数据结构中用循环链表建模的一个代表性应用。...问题定义和历史沿革 约瑟夫斯问题（有时也称为约瑟夫斯置换，但严格来讲这并不是一个集合到自身的映射，所以不是置换，需要推广到集合的序列到集合的序列的映射才行。），是一个出现在计算机科学和数学中的问题。...问题：给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。大家一定很好奇这个问题名字的由来。这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。...约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。哈哈，这么个数学味浓厚的问题居然是个历史学家发明了，真是有趣。...具体到这个问题，因为我们不太需要对环上元素进行像数组那样的随机下标访问，而比较看重“下一个”这个环上的核心关系，中间还涉及很多删除元素，也就是修改这个映射的操作。

8044 0

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

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

8244 0

约瑟夫问题

一、约瑟夫问题介绍 1、约瑟夫问题原题： n个小孩子手拉手围成一个圈，编号为k(1 <= k <= n )的人从1开始报数，报到m的那个人出列，它的下一位又从1开始报数，报到m的又出列……依此类推，直到所有人都出列...2、问题分析：根据题目的描述，很容易可以想到用单向循环链表来模拟。...遍历的时候，当节点的next等于first时，表示遍历完毕。...2、代码实现：根据上面的分析，可以写出如下代码： package com.zhu.study.linkedList; /** * 约瑟夫问题，即单向循环链表问题 * @author: zhu...cur和pre同时移动(m-1)次，此时cur就指向了要被删除的节点；打印要被删除的节点，然后将cur移动到被删除节点的下一个节点，即cur = cur.next，pre的next指向新的cur，即pre.next

4672 0

约瑟夫问题

约瑟夫问题：编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。...cur=cur->next; cnt++; } } } return cur->val; } 方法三：数学...这个问题很难快速给出答案。...但是同时也要看到，这个问题似乎有拆分为较小子问题的潜质：如果我们知道对于一个长度 num - 1 的序列，留下的是第几个元素，那么我们就可以由此计算出长度为 num 的序列的答案。...算法我们将上述问题建模为函数 f(num, target)，该函数的返回值为最终留下的元素的序号。

1411 0

约瑟夫问题

题目:约瑟夫问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。现在需要求的是最后一个出局的人的编号。...请返回最后一个出局的人的编号。保证n和m小于等于1000。...注意: 这里判断新的起始位置时候需要用当前位置重新对链表长度取余得方式,因为这里不确定是否需要从头开始测试样例：输入5 3 返回 4 思想: 数学方法判断取出数据得位置: getIndex=

3372 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!

6362 0

约瑟夫斯问题

弗拉维奥·约瑟夫斯（Josephus problem）是一世纪著名历史学家，他和他39个战友被罗马军队包围在洞中。...约瑟夫斯是一个厉害的数学家，他立即想出了坐在哪里才能成为最后一个人。最后他加入了罗马军队。

7074 0

《具体数学》学习笔记

第1章递归问题 1.1河内塔 $n$个盘子的汉诺塔问题需要移动$2^n - 1$次 1.2平面上的直线 $n$条直线最多能将平面划分为$\frac{n(n+1)}{2}$个区域 1.3约瑟夫问题 约瑟夫问题...$\sum$后面的量成为被加数(summand) $\sum_{k=1}^{\pi(N)}\frac{1}{p_k}$ 其中$p_k$表示第$k$个素数，$\pi(N)$是$\leqslant N$的素数的个数...这个和式给出了接近$N$的随机整数平均而言有多少个素因子，因为那些整数中大约有$1/p$个能被$p$整除，对于大的$N$，它的值近似等于$lnlnN + M$，其中 $$M \approx 0.261...,$H_n$称为一个“调和数”(harmonic number) 2.3 和式的处理设$K$是任意一个有限整数集合，$K$中元素的和式可以用三条简单的法则加以变换： $$\sum_{k \in K}ca_k..._{k = 1}^m p_k$$ 4.3 素数的例子素数有无穷多个形如$2^p - 1$的数，称为梅森素数(Mersenne number) 4.4 阶乘的因子斯特林公式 $$n!

7095 0

具体数学-第1课（递归求解实际问题）

原文链接：具体数学-第1课 - WeiYang Bloggodweiyang.com ?...这学期提前选修了研究生的课程：具体数学、人工智能前沿、NLP讨论班，就随便记记具体数学每一节课所学的东西吧。第一节课讲的都是一些很简单的东西，这里就一带而过了。...汉诺塔问题这是个老生常谈的问题了，n个盘子，3个柱子的汉诺塔问题，最少移动次数记为 ? 。那么 ? 边界条件为 ? 。解出 ? 验证可以采用数学归纳法，这里就不多说了。...约瑟夫环问题这个问题暴力求解的话模拟就行了，复杂度是 ? 的，这里探索一种直接求解的方法。分两种情况讨论：当有 ? 个人时，踢掉 ? 个人之后，情况如下图所示 ?...的最大2的幂，那么 ? 正确性可以通过数学归纳法求证。第一节课就讲了这么多，约瑟夫环还有很多问题值得探讨，下节课继续。。。

4533 0

洛谷 || 约瑟夫问题

题目描述 ‍‍n 个人围成一圈，从第一个人开始报数,数到m的人出列，再由下一个人重新从1开始报数，数到m的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。‍‍...输出格式输出一行 n个整数，按顺序输出每个出圈人的编号。...(i = 1; i <= n; i++) { p = (ListNode *) malloc(sizeof(ListNode)); p->data =i;//初始化p的data...q->next=p;//将q指向p的首地址 q=p;//p为尾结点，将p赋值给临时变量q } p->next=L->next;//使最后一个结点指向第一个结点

3943 0

约瑟夫问题与魔术（五）——魔术《自我匹配的奇迹》中的数学原理

前面说了，约瑟夫过程在扑克牌叠上只是一个复杂但又确定的操作过程，应用时候一方面要防止枯燥无聊，另一方面最好再结合一切其他的魔术或数学方法一起使用，才能锦上添花，画龙点睛，发挥这个原理的最大作用。...比如，我虽然知道取余数，取模这等操作，但并没有把它当作其实和正常四则运算同等地位的运算来理解，而是以别扭的方式来在错误的基础上打补丁，特例能解决但是并没有解决根本问题，可见研究问题的视角的选择有多么重要...那来看看看这里没有变的具体是什么吧？拿走3张以后的第一张其实是第4张，不变，最后一张其实是第8张不变。观众朋友们，第8和4张之间的差距4是什么呀，正好就是周期的大小啊！...末两位恰好是0~3之间数的二位二进制表示，值为(n - 4)。根据前面k = 2的约瑟夫问题公式，其最后一张牌的索引即为2(n - 4)，即三位二进制数右移一位的结果。...从这里也可以看出k = 2的约瑟夫问题结论的另一种表述和物理意义，其实是这个纯位指数值模的相反数模张数n的结果。

7881 0

约瑟夫算法（数学分析法）

//看了帖子后认为有趣就实现了一把递归的约瑟夫算法 package test; /** * 500个小孩围成一圈，从第一个開始报数：1，2，3，1,2,3,1,2,3,……每次报3的小孩退出...问最后剩下的那个小孩，在曾经500人里是第几个？？？...*/ public class Test { /** * 约瑟夫标准循环非递归解法 * @param n * @param m * @return */ public static...index(1) = 0; index(n) = (index(n-1) + m)%n; (n>1) 这个公式不是仅仅考虑一种场景得出的结果，而是抽象出普遍的n得出的结论， */.../* *f(1) = 0;//第0个 *f(2) = 1;//第1个 *f(3) = 1;//第2个 * */ //參考上面的提示写了下约瑟夫的递归算法 System.out.println

1721 0

约瑟夫环问题详解

在牛客网上做到一道题，是约瑟夫环的变型，所以借此学习一下新知识，并且巩固一下对题目意思的理解，这一篇仅作约瑟夫环问题的解释，下一篇再写题目： ##1.首先，我们先来了解一下什么是约瑟夫环问题：讲一个比较有意思的故事...见图下：这时候，我们从3号开始，就成了另外一个规模小1的约瑟夫问题（恰好为2^k的特例）。...这时候，我们可以把3号看成新的约瑟夫问题中的1号位置： J(8) = J(2^3) = 1，也就是说这里的1代表的就是上一个问题中的3号 So：J(9) = 3 答案为3号 ####同理可知所有的非...假设n = 11，这时候n = 2^3 + 3，也就是说t = 3，所以开始剔除元素直到其成为2^k问题的约瑟夫问题。...q个人约定： Jq(n)表示n人构成的约瑟夫环，每次移除第q个人的解 n个人的编号从0开始至n-1 我们沿用之前特例的思想：能不能由Jq(n+1)的问题缩小成为J(n)的问题（这里的n是n+1规模的约瑟夫问题消除一个元素之后的答案

4021 0

P1996 约瑟夫问题

题目背景 约瑟夫是一个无聊的人！！！...题目描述 n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号....输入输出格式输入格式： n m 输出格式：出圈的编号输入输出样例输入样例#1： 10 3 输出样例#1： 3 6 9 2 7 1 8 5 10 4 说明你猜，你猜，你猜猜猜...‘ 我确信我的是对的但是不知道为什么会超时跟填涂颜色那题一样明明在自己机子上秒出但是超时？？...;false则表示还未出圈 5 int main() 6 { 7 scanf("%d%d",&n,&m); 8 int cnt=0,now=0,tot=0;//cnt:当前数的数

7817 0

约瑟夫问题方法总结

第一行为人数n; 第二行为报数k 10 4 对于约瑟夫问题当前实现方法大概有两种：一：模拟：链表模拟： 1 #include 2 #include 3...)假设第三轮的开始数字为o，那这n-2个数构成的约瑟夫环为o,o+1,o+2,......映射 o--->0 o+1--->1 o+2--->2 --- --- o-2--->n-3 这是一个n-2个人的问题。...代入可得(y+m)%(n-1) 要得到n-1个人问题的解，只需要得到n-2个人问题的解，倒退下去。...不需要从i=0开始，要注意的是序列从0开始编号的，所以最后的输出结果也要加1. s表示的是上一轮的结果，m代表是每多少个人出列一次，i代表当前已经出列了多少个人。

1.2K8 0

经典算法之约瑟夫问题

问题是，给定了和，一开始要站在什么地方才能避免被处决？ Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。数学解法 ?...当n，m数据量很小的时候，我们可以用循环链表模拟约瑟夫环的过程。当模拟到人数等于1的时候，输出剩下的人的序号即可。具体解法这种方法往往实现起来比较简单，而且也很容易理解。...+n-2)%n1(n1为当前序列的总人数，因为是循环的序列，k1+n-1可能大于总人数) 那么这时我们要解决的问题就是n-1个人的报数问题（即n-1阶约瑟夫环的问题）可能以上过程你还是觉得不太清晰，那么我们重复以上过程...后面的过程与前两次的过程一模一样，那么递归处理下去，直到最后只剩下一个人的时候，便可以直接得出结果当我们得到一个人的时候（即一阶约瑟夫环问题）的结果，那么我们是否能通过一阶约瑟夫环问题的结果，推导出二阶约瑟夫环的结果呢...借助上面的分析过程，我们知道，当在解决n阶约瑟夫环问题时，序号为k1的人出列后，剩下的n-1个人又重新组成了一个n-1阶的约瑟夫环，那么假如得到了这个n-1阶约瑟夫环问题的结果为ans（即最后一个出列的人编号为

1.6K1 0

29-约瑟夫环问题

代码 #include /* 编号为 1，2，3，…，n 的 n 个人围坐一圈，任选一个正整数 m 作为报数上限值，从第一个人开始按顺时针方向报数，报数到 m 时停止，报数为 m...从出列人的顺时针方向的下一个人开始又从 1 重新报数，如此下去，直到所有人都全部出列为止。

4993 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

约瑟夫的问题？(具体数学)

相关·内容

约瑟夫问题与魔术（三）——终极数学推导

约瑟夫问题与魔术（二）——数学结构解析

C#实现约瑟夫环数学问题

约瑟夫问题与魔术（一）——数学模型求解

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

约瑟夫问题

约瑟夫问题

约瑟夫问题

约瑟夫环问题

约瑟夫斯问题

《具体数学》学习笔记

具体数学-第1课（递归求解实际问题）

洛谷 || 约瑟夫问题

约瑟夫问题与魔术（五）——魔术《自我匹配的奇迹》中的数学原理

约瑟夫算法（数学分析法）

约瑟夫环问题详解

P1996 约瑟夫问题

约瑟夫问题方法总结

经典算法之约瑟夫问题

29-约瑟夫环问题

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐