文档章节

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

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
学习笔记之约瑟夫环的两种实现方法(数组&链表)

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

Jung_zhang
2015/04/08
0
0
约瑟夫问题(Josephus problem)的klog(n)解法

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

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

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

香沙小熊
01/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
今天
2
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
今天
8
0
让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字

让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字: 作者:孙冬梅;以前读韩国前总统朴槿惠的著作《绝望锻炼了我》时,里面有一句话令我印象深刻,她说“在我最困难的时期,...

原创小博客
今天
4
0
JAVA-四元数类

public class Quaternion { private final double x0, x1, x2, x3; // 四元数构造函数 public Quaternion(double x0, double x1, double x2, double x3) { this.x0 = ......

Pulsar-V
今天
18
0
Xshell利用Xftp传输文件,使用pure-ftpd搭建ftp服务

Xftp传输文件 如果已经通过Xshell登录到服务器,此时可以使用快捷键ctrl+alt+f 打开Xftp并展示Xshell当前的目录,之后直接拖拽传输文件即可。 pure-ftpd搭建ftp服务 pure-ftpd要比vsftp简单,...

野雪球
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部