在上一篇文章中，我们聊到了约瑟夫问题的定义，以及其用环的数学模型来建模，最后用循环单链表的数据结构解决该问题等内容。...这些只是基本内容，当我们有了数学模型把这个问题变成数学问题以后，就可以在数学结构内去研究更多的东西，而不局限于仅仅求出最后那个被杀的人，比如： 在约瑟夫问题中，我们还可以关心几个内容： 1....被移除的节点的顺序如何？ 2. 最后一个以及倒数若干个留下的节点编号是多少？ 本质上，我们希望对约瑟夫问题更细致地每一步到底发生了什么进行更细致的观察。...具体就是，到底一个原始环上的元素，是以怎样的排列顺序给移出去的，有怎样的规律，这个搞清楚了，其他的问题都是这个问题的子问题，包含于此。...接下来，我们再仔细分析一下约瑟夫问题的过程，看看这个结论为什么会成立。 约瑟夫问题通项公式理解 原始的约瑟夫问题的每一步仅往后处理一个人，这也是前面代码模拟的思路。
前面文章我们介绍了约瑟夫问题，并给出了基本的数学模型，和其内部数学性质的分析。...今天我们接着上期的问题分析把整个过程的数学细节都描绘下来，注意今天的描绘的粒度是每一次对整个序列的遍历，而第一篇描述的时候是每一次行动。...所以这个函数恰好可以用高斯函数表达： f(n, k) = [k / (k - 1)((f(n’, k) - n % k)mod n’)] 于是，整个约瑟夫问题求解的，复杂度降低为O(klogn)的递归表达式如下...，我们找到了更深层次的约瑟夫问题的求解策略，大大降低了问题的时间复杂度。...以上就是约瑟夫问题数学部分的全部内容，从下一篇起，我们进入魔术部分，看看这一神奇的结构能够怎样配合上我们的魔术表演，去继续缔造属于我们的奇迹。
犹太士兵里有个人叫约瑟夫，他想投降保命但又不能明说。那么约瑟夫应该站在哪个位置上才能成为最后一个剩下的人？这样就不用自sha可以直接向罗马人投降。...在人数不多的情况下这个问题很好推算，假设总人数10人的前置条件。...约瑟夫没有那么多时间进行推算。把总人数和最终存活的位置整理成图表的话大致如下： 最终我们发现，活下来的都是奇数位。...因为最先杀人的士兵都处在奇数位置，不管人数多少最先被kill掉的肯定是站在偶数位置上的人。也就是约瑟夫绝对不能站在偶数位置上。...C#代码 /// /// 约瑟夫一下 /// /// 总人数 ///
约瑟夫问题，相信对有一点数学或者信息学竞赛背景的同学应该都不会很陌生，这是数学竞赛中常见的一个考题背景以及数据结构中用循环链表建模的一个代表性应用。...问题定义和历史沿革 约瑟夫斯问题（有时也称为约瑟夫斯置换，但严格来讲这并不是一个集合到自身的映射，所以不是置换，需要推广到集合的序列到集合的序列的映射才行。），是一个出现在计算机科学和数学中的问题。...问题：给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。 大家一定很好奇这个问题名字的由来。这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。...约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。 哈哈，这么个数学味浓厚的问题居然是个历史学家发明了，真是有趣。...具体到这个问题，因为我们不太需要对环上元素进行像数组那样的随机下标访问，而比较看重“下一个”这个环上的核心关系，中间还涉及很多删除元素，也就是修改这个映射的操作。
单向环形链表应用场景 Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。...提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从...更通俗的说，他就是一个圆形蛋糕，分成四份的话，我们有两个指针，一个指向第一块，一个指向最后一块，然后他们一起移动，后指针永远在前指针的后面做好对接的准备。 约瑟夫问题-创建环形链表的思路图解 ?...约瑟夫问题-小孩出圈的思路分析图 ? 我自己画了一个图 ?
一、约瑟夫问题介绍 1、约瑟夫问题原题： n个小孩子手拉手围成一个圈，编号为k(1 的那个人出列，它的下一位又从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
约瑟夫问题： 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。...cur=cur->next; cnt++; } } } return cur->val; } 方法三：数学...这个问题很难快速给出答案。...但是同时也要看到，这个问题似乎有拆分为较小子问题的潜质：如果我们知道对于一个长度 num - 1 的序列，留下的是第几个元素，那么我们就可以由此计算出长度为 num 的序列的答案。...算法 我们将上述问题建模为函数 f(num, target)，该函数的返回值为最终留下的元素的序号。
题目:约瑟夫问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。现在需要求的是最后一个出局的人的编号。...请返回最后一个出局的人的编号。 保证n和m小于等于1000。...注意: 这里判断新的起始位置时候需要用当前位置重新对链表长度取余得方式,因为这里不确定是否需要从头开始 测试样例： 输入5 3 返回 4 思想: 数学方法判断取出数据得位置: getIndex=
一、问题描述 约瑟夫环问题是一个很经典的问题：一个圈共有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
以前写的程序，今天在整理文件的时候发现了，贴出来有需要的朋友可以参考！ 问题提出： 约瑟夫环是一个数学的应用问题：已知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!
弗拉维奥·约瑟夫斯（Josephus problem）是一世纪著名历史学家，他和他39个战友被罗马军队包围在洞中。...约瑟夫斯是一个厉害的数学家，他立即想出了坐在哪里才能成为最后一个人。最后他加入了罗马军队。
第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!
1.故事背景以及题目概述 通过这个例子，我们就应该大致了解这个环形链表的约瑟夫问题大致是干什么的，先说一个很简单的例子，比如有5个数据组成一个环形结构，每次数到2的数字自杀，最后这个环形链表只会保留一个数据...，具体如下图所示： 下面的就是牛客网的题目，这个题目表面上看比较委婉，把这个数字删除，其实其本质就是约瑟夫问题，下面我会拆解步骤为大家进行介绍解题思路。...就是我们想要解决这个约瑟夫问题，首先就需要创建一个环形的链表，这个链表肯定要有很多个节点，我们这步就是提前封装一个函数，我们在创建环形链表之后进行创建节点的时候可以直接调用这个函数； （1）我们想要创建节点就要开辟新的空间存放这个节点...，这个节点就属于约瑟夫问题里面的报数节点，我们删除这个节点的方法就是让他的前一个节点的next指向他的后一个节点，释放掉这个空间，然后让这个pcur指向新的节点，这个时候新的节点就是我们的报数节点的上一个节点的...next指针指向的位置，让后让count=1重新开始计数； （4）这个过程就按照这样依次进行循环，什么时候循环会结束呢，我们都知道，约瑟夫问题里面最后会剩下一个节点，最后是这个节点的next指针指向自己
原文链接： 具体数学-第1课 - WeiYang Bloggodweiyang.com ?...这学期提前选修了研究生的课程：具体数学、人工智能前沿、NLP讨论班，就随便记记具体数学每一节课所学的东西吧。 第一节课讲的都是一些很简单的东西，这里就一带而过了。...汉诺塔问题 这是个老生常谈的问题了，n个盘子，3个柱子的汉诺塔问题，最少移动次数记为 ? 。 那么 ? 边界条件为 ? 。 解出 ? 验证可以采用数学归纳法，这里就不多说了。...约瑟夫环问题 这个问题暴力求解的话模拟就行了，复杂度是 ? 的，这里探索一种直接求解的方法。 分两种情况讨论： 当有 ? 个人时，踢掉 ? 个人之后，情况如下图所示 ?...的最大2的幂，那么 ? 正确性可以通过数学归纳法求证。 第一节课就讲了这么多，约瑟夫环还有很多问题值得探讨，下节课继续。。。
题目描述 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;//使最后一个结点指向第一个结点
前面说了，约瑟夫过程在扑克牌叠上只是一个复杂但又确定的操作过程，应用时候一方面要防止枯燥无聊，另一方面最好再结合一切其他的魔术或数学方法一起使用，才能锦上添花，画龙点睛，发挥这个原理的最大作用。...比如，我虽然知道取余数，取模这等操作，但并没有把它当作其实和正常四则运算同等地位的运算来理解，而是以别扭的方式来在错误的基础上打补丁，特例能解决但是并没有解决根本问题，可见研究问题的视角的选择有多么重要...那来看看看这里没有变的具体是什么吧？拿走3张以后的第一张其实是第4张，不变，最后一张其实是第8张不变。观众朋友们，第8和4张之间的差距4是什么呀，正好就是周期的大小啊！...末两位恰好是0~3之间数的二位二进制表示，值为(n - 4)。根据前面k = 2的约瑟夫问题公式，其最后一张牌的索引即为2(n - 4)，即三位二进制数右移一位的结果。...从这里也可以看出k = 2的约瑟夫问题结论的另一种表述和物理意义，其实是这个纯位指数值模的相反数模张数n的结果。
//看了帖子后认为有趣就实现了一把递归的约瑟夫算法 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
在牛客网上做到一道题，是约瑟夫环的变型，所以借此学习一下新知识，并且巩固一下对题目意思的理解，这一篇仅作约瑟夫环问题的解释，下一篇再写题目： ##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规模的约瑟夫问题消除一个元素之后的答案
第一行为人数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代表当前已经出列了多少个人。
题目背景 约瑟夫是一个无聊的人！！！...题目描述 n个人(n的编号....输入输出格式 输入格式： 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:当前数的数
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
