文档章节

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

Mr_Nice
 Mr_Nice
发布于 2016/05/22 20:01
字数 280
阅读 3
收藏 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
0
数据结构笔记1---链表与顺序表

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

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

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

香沙小熊
01/21
0
0
约瑟夫问题(Josephus problem)的klog(n)解法

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

尹宁
06/14
0
0
学习笔记之约瑟夫环的两种实现方法(数组&链表)

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

Jung_zhang
2015/04/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

MySQL 乱七八糟的可重复读隔离级别实现

MySQL 乱七八糟的可重复读隔离级别实现 摘要: 原文可阅读 http://www.iocoder.cn/Fight/MySQL-messy-implementation-of-repeatable-read-isolation-levels 「shimohq」欢迎转载,保留摘要,谢...

DemonsI
45分钟前
2
0
Spring源码阅读——2

在阅读源码之前,先了解下Spring的整体架构: 1、Spring的整体架构 1. Ioc(控制反转) Spring核心模块实现了Ioc的功能,它将类与类之间的依赖从代码中脱离出来,用配置的方式进行依赖关系描...

叶枫啦啦
今天
1
0
jQuery.post() 函数格式详解

jquery的Post方法$.post() $.post是jquery自带的一个方法,使用前需要引入jquery.js 语法:$.post(url,data,callback,type); url(必须):发送请求的地址,String类型 data(可选):发送给后台的...

森火
今天
0
0
referer是什么意思?

看看下面这个回答(打不开网页可以把网址复制到搜索栏): https://zhidao.baidu.com/question/577842068.html

杉下
今天
1
0
使用U盘安装CentOS-解决U盘找不到源

1. 使用UltraISO制作CentOS安装盘 如果需要安装带界面的系统,为保证安装顺利,可选择Everything版本的ISO制作安装盘。 2. 在BIOS中选择使用U盘安装 系统启动后,进入安装选择界面,其中有三...

Houor
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部