学习
实践
活动
专区
工具
TVP
写文章
  • 广告
    关闭

    新年·上云精选

    热卖云产品新年特惠,2核2G轻量应用服务器9元/月起,更多上云必备产品助力您轻松上云

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

    约瑟夫问题详解

    在牛客网上做到一道题,是约瑟夫环的变型,所以借此学习一下新知识,并且巩固一下对题目意思的理解,这一篇仅作约瑟夫问题的解释,下一篇再写题目: ##1.首先,我们先来了解一下什么是约瑟夫问题: 讲一个比较有意思的故事 ##2.这就是约瑟夫问题,接下来我们说个特例初步了解下这种问题的求解思路: 特例:2,当q = 2时候,是一个特例,能快速求解 特例还分两种 ###1.思路:注意这里的前提是n = 2^k(也就是 见图下: 这时候,我们从3号开始,就成了另外一个规模小1的约瑟夫问题(恰好为2^k的特例)。 假设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规模的约瑟夫问题消除一个元素之后的答案

    10710

    经典算法之约瑟夫问题

    n-1个人的报数问题(即n-1阶约瑟夫环的问题) 可能以上过程你还是觉得不太清晰,那么我们重复以上过程,继续推导剩余的n-1个人的约瑟夫环的问题: 那么在这剩下的n-1个人中,我们也可以为了方便,将这n n-2阶约瑟夫环的问题呢? 后面的过程与前两次的过程一模一样,那么递归处理下去,直到最后只剩下一个人的时候,便可以直接得出结果 当我们得到一个人的时候(即一阶约瑟夫问题)的结果,那么我们是否能通过一阶约瑟夫问题的结果,推导出二阶约瑟夫环的结果呢 借助上面的分析过程,我们知道,当在解决n阶约瑟夫问题时,序号为k1的人出列后,剩下的n-1个人又重新组成了一个n-1阶的约瑟夫环,那么 假如得到了这个n-1阶约瑟夫问题的结果为ans(即最后一个出列的人编号为 [n] = (f[n-1] + m)%n //m表示每次数到该数的人出列,n表示当前序列的总人数 而我们只需要得到第n次出列的结果即可,那么不需要另外声明数组保存数据,只需要直接一个for循环求得n阶约瑟夫问题的结果即可

    83510

    单向环形链表--约瑟夫问题

    首先来看一个著名的约瑟夫(Josephu)问题 设编号为1,2,3... 个人围坐一圈,约定编号为k(1<=k <= n)的人从1开始报数,数到m的那个人出列,紧接着他的下一位又从1开始报数,数到m的那个人又出列,以此类推,直到所有人出列为止,由此产出一个编号的序列 如何解决上述问题 /遍历到最后 } temp = temp.getNext(); } } } 至此我们已经创建好了一个单向环形链表,接下来我们完成约瑟夫问题 约瑟夫问题 假设环形链表上有5个节点 设 k = 1 即从第一个节点开始计数 设 m = 2 即计数到m的那个节点出列,并记录其编号。 分析 这里涉及到一个问题,当我们出圈的时候,怎么把某个节点移除环形链表呢? 1.这里需要一个辅助指针helper,默认指向环形链表中的最后一个节点。

    9310

    UVALive 3882 - And Then There Was One【约瑟夫问题

    com_onlinejudge&Itemid=8&page=show_problem&problem=1883 题意:n个人围成一圈,第一次删第m个人,然后每数K个删一个人,求最后一个人的编号 分析:典型的约瑟夫问题 则我们可以从这个人的后面编号设为k= m % n,则这n-1个人的编号依次为k,k+1,….n-1,n,1,2,…k-2; 则重新编号为0,1,2….n-2,那么我们就可以看作是在这n-1规模的子问题约瑟夫环的基础上 ,求解n规模的约瑟夫环。 设n-1规模的子问题约瑟夫环的解为f[n-1],则n规模约瑟夫环是f[n] = (f[n-1] + k) % n; 证明过程如下: 原来编号依次为k,k+1,….n-1,n,1,2,… ] + m) % n;递推公式是f[i] = (f[i-1] + k) % i; 而f[1] = 0,则最后的结果是f[n]+1(因为f[n]是0,1…n-1编号的,所以要加1)这样,光秃秃的约瑟夫问题就结束了

    43360

    如何解决约瑟夫问题

    约瑟夫问题算是很经典的题了,估计大家都听说过,然后我就在一次笔试中遇到了,下面我就用 3 种方法来详细讲解一下这道题,最后一种方法学了之后保证让你可以让你装逼。 问题描述:编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈,从编号为 1 的士兵开始依次报数(1,2,3…这样依次报),数到 m 的 士兵会被杀死出列,之后的士兵再从 1 开始报数。 这种做法的时间复杂度是 O(n * m), 空间复杂度是 O(n); 2、方法二:环形链表 学过链表的人,估计都会用链表来处理约瑟夫问题,用链表来处理其实和上面处理的思路差不多,只是用链表来处理的时候 那如果你想跟别人说,我想一行代码解决约瑟夫问题呢?答是没问题的,如下: int f(int n, int m){ return n == 1 ?

    94420

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

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

    9410

    扫码关注腾讯云开发者

    领取腾讯云代金券