文档章节

算法学习笔记之约瑟夫环问题

Mr_Nice
 Mr_Nice
发布于 2016/05/22 20:01
字数 280
阅读 3
收藏 0
点赞 2
评论 0

问题:
假设下标从0开始,0,1,2 .. m-1共m个人,从1开始报数,报到k则此人从环出退出,问最后剩下的一个人的编号是多少?

我的理解:
设f(m,k,i)为m个人的环,报数为k,第i个人出环的编号,m个人的环第i个出来的人就相当于m-1个人的环第i-1个出来的人,不过这个序号是相当于原来m个人的序号。但注意的是m个人的环第一个出来的人序号要减一。

通俗的讲就是:假设10个人的环,报数为3的人出来,那么10个人的环第一个出来的人的序号为2,而10个人的环第二次出来的人相当于9个人第一次出来的人。

程序:

//m:人数
//k:报数
//i:第i个出来的
public static int fun(int m,int k,int i) {
        if (i == 1) {
            return (m+k-1)%m;
        }else {
            //取余是因为是环
            return (fun(m-1, k, i-1)+k)%m;
        }
    }

结果:
这里写图片描述

© 著作权归作者所有

共有 人打赏支持
Mr_Nice
粉丝 0
博文 47
码字总数 39947
作品 0
广州
考研复试系列——第十二节 后缀表达式&约瑟夫环

考研复试系列——第十二节 后缀表达式&约瑟夫环 前言 后缀表达式 #include include include include using namespace std; int priority(char ch)//定义优先级{switch(ch){case '(':return 0...

cassiepython ⋅ 2017/03/14 ⋅ 0

数据结构笔记1---链表与顺序表

导读 1.单链表(创建,插入,删除,查找(2),判空) 2.数组线性表(创建,插入,删除,查找,判空,判满) 3.循环链表(创建,插入,删除,判空) 4.运用数组线性表的串的替换暴力算法 单链...

qq_37527943 ⋅ 2017/11/27 ⋅ 0

数据结构与算法-C语言篇9-用循环链表实现约瑟夫环问题

数据结构与算法-目录 前言 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,...

香沙小熊 ⋅ 01/21 ⋅ 0

约瑟夫问题(Josephus problem)的klog(n)解法

约瑟夫问题是一个经典的算法问题,其解决过程涉可能用到的数据结构有数组、链表,涉及的算法包括模拟、递归、递推、动态规划等等,因此非常适合做一道面试题。 问题描述: 首先n个候选人围成...

尹宁 ⋅ 06/14 ⋅ 0

学习笔记之约瑟夫环的两种实现方法(数组&链表)

传说在很久很久以前,罗马人占领乔塔帕特之后咱们的约瑟夫大大,哦不,是著名的犹太历史学家约瑟夫(Josephus)和他的朋友躲在一个洞中,当时洞中还有其他的39名犹太人,他们非常的傻(ai)逼(gu...

Jung_zhang ⋅ 2015/04/08 ⋅ 0

约瑟夫环的处理

编辑本段链表方法 这个就是约瑟夫环问题的实际场景,有一种是要通过输入n,m,k三个正整数,来求出列的序列。这个问题采用的是典型的循环链表的数据结构,就是将一个链表的尾元素指针指向队首元...

皮皮大仙 ⋅ 2011/04/17 ⋅ 0

一天一练之算法——约瑟夫问题

猴子选王 一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该...

_编程菜鸟_ ⋅ 2014/09/03 ⋅ 1

PHP常见的算法

1:快速排序 <?php function quick_sort($array) { if(count($array) <= 1) { return $array; } $left_arr = array(); $right_arr = array(); $key = $array[0];......

雨醉风尘 ⋅ 2016/02/29 ⋅ 0

约瑟夫问题、循环链表、双向链表?

约瑟夫问题、循环链表、双向链表?

datacube ⋅ 2016/07/29 ⋅ 0

约瑟夫环的实现

约瑟夫环的实现 --- 概述 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个...

面码 ⋅ 2015/01/29 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

istio 文档

https://istio.io/docs/concepts/ https://istio.io/docs/concepts/traffic-management/handling-failures/ https://istio.io/docs/concepts/traffic-management/rules-configuration/......

xiaomin0322 ⋅ 10分钟前 ⋅ 0

编程语言的作用及与操作系统和硬件的关系

一、编程语言的作用及与操作系统和硬件的关系 作用:编程语言是计算机语言,是一种程序员与计算机之间沟通的介质,通过编程语言可以使得计算机能够根据人的指令一步一步去工作,完成某种特定...

slagga ⋅ 20分钟前 ⋅ 0

runtime实现按钮点击事件

也不能说是实现吧,,,就是有点类似于RAC里边的写法,不用给btn添加另外的点击事件,就那个add...select...这样子很不友好,来看下代码: [self.btn handleControlEvent:UIControlEventTou...

RainOrz ⋅ 21分钟前 ⋅ 0

Windows系统运维转linux系统运维的经历

开篇之前,首先介绍一下我的背景把:我是一个三线城市的甲方运维。最近,在《Linux就该这么学》书籍的影响下和朋友小A(Linux运维已经三年了,工资也比我的高很多)的影响下,决定转行。最近...

linux-tao ⋅ 21分钟前 ⋅ 0

zip压缩工具,tar打包工具

zip压缩工具 zip打包工具跟前面说到的gzip,bz2,xz 工具最大的不一样是zip可以压缩目录。如果没有安装,需要使用yum install -y zip 来安装。安装完之后就可以直接使用了,跟之前提到的压缩...

李超小牛子 ⋅ 29分钟前 ⋅ 0

使用npm发布自己的npm组件包

一、注册npm账号 官网:https://www.npmjs.com/signup 注册之后需要进行邮箱验证,否则后面进行组件包发布时候会提示403错误,让进行邮箱核准。 二、本地新建一个文件夹,cd进入后使用npm i...

灰白发 ⋅ 31分钟前 ⋅ 0

010. 深入JVM学习—垃圾收集策略概览

1. 新生代可用GC策略 1. 串行GC(Serial Copying) 算法:复制(Copying)清理算法; 操作步骤: 扫描年轻代中所有存活的对象; 使用Minor GC进行垃圾回收,同时将存活对象保存到“S0”或“S...

影狼 ⋅ 32分钟前 ⋅ 0

JVM性能调优实践——JVM篇

在遇到实际性能问题时,除了关注系统性能指标。还要结合应用程序的系统的日志、堆栈信息、GClog、threaddump等数据进行问题分析和定位。关于性能指标分析可以参考前一篇JVM性能调优实践——性...

Java小铺 ⋅ 33分钟前 ⋅ 0

误关了gitlab sign-in 功能的恢复记录

本想关sign-up的,误点了sign-in 退出后登录界面提示: No authentication methods configured 一脸懵逼.. 百度后众多方案说修改application_settings 的 signin_enabled字段; 实际上新版本字段...

铂金蛋蛋 ⋅ 33分钟前 ⋅ 0

登录后,后续请求接口没有带登录cookie可能原因

1.XMLHttpRequest.withCredentials没设置好,参考https://developer.mozilla.org/zh-CN/docs/Web/API/XMLHttpRequest/withCredentials...

LM_Mike ⋅ 34分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部