首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    约瑟夫问题详解

    在牛客网上做到一道题,是约瑟夫的变型,所以借此学习一下新知识,并且巩固一下对题目意思的理解,这一篇仅作约瑟夫问题的解释,下一篇再写题目: ##1.首先,我们先来了解一下什么是约瑟夫问题: 讲一个比较有意思的故事...##2.这就是约瑟夫问题,接下来我们说个特例初步了解下这种问题的求解思路: 特例:2,当q = 2时候,是一个特例,能快速求解 特例还分两种 ###1.思路:注意这里的前提是n = 2^k(也就是...q个人 约定: Jq(n)表示n人构成的约瑟夫,每次移除第q个人的解 n个人的编号从0开始至n-1 我们沿用之前特例的思想:能不能由Jq(n+1)的问题缩小成为J(n)的问题(这里的n是n+1规模的约瑟夫问题消除一个元素之后的答案...} cout<<"result = "<<result<<endl; return 0; } ##总结: 在遇上包含特殊的出队规则相关的题目时,应该联想到是否是<em>约瑟夫</em><em>环</em><em>问题</em>...此文章重新整理在<em>约瑟夫</em><em>环</em><em>问题</em>详解里了,修改了之前写过程中存在的一些错误,并添加了一些新的推导过程,谢谢指出错误之处.

    41410

    如何解决约瑟夫问题

    约瑟夫问题算是很经典的题了,估计大家都听说过,然后我就在一次笔试中遇到了,下面我就用 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 ?

    1.5K20

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

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

    43110

    动态规划解决约瑟夫问题

    题目: 约瑟夫约瑟夫问题)是一个数学的应用问题:已知n个人(以编号0,1,2,3…n-1分别表示)围坐在一张圆桌周围。...1.经典解法 可以用链表来模拟约瑟夫,每次在链表中删除第m个节点,然后不断,直至链表中只剩下一个节点。最后一个这个节点就是我们要求的节点。 注意:当迭代器扫描到链表末尾时,将迭代器移至链表头。...=1){ //循环迭代至约瑟夫只剩最后一个元素 for(int i=0;i<m-1;++i){ //迭代m-1次找到需要移出的元素...状态就是确定问题的解的表达式,状态转移方程就是上一阶段问题的解推出当前阶段问题解的递推式。 针对约瑟夫问题,n个元素的可以定义为f(n,m),m表示每次移动的步数。则状态就是f(n,m)。...[2]解题笔记(10)——约瑟夫问题.

    1.2K20
    领券