文档章节

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

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

没有更多内容

加载失败,请刷新页面

加载更多

关于Jackson默认丢失Bigdecimal精度问题分析

问题描述 最近在使用一个内部的RPC框架时,发现如果使用Object类型,实际类型为BigDecimal的时候,作为传输对象的时候,会出现丢失精度的问题;比如在序列化前为金额1.00,反序列化之后为1.0...

ksfzhaohui
21分钟前
0
0
vue less安装

$ npm install less less-loader --save 安装成功后修改文件:build>webpack.base.conf.js 在model.rules添加对象: { test: /\.less$/, loader: "style-loader!css-loader!less-loade......

shawnDream
26分钟前
0
0
kolla-ansible部署容器ceph

kolla是从openstack孵化出的一个项目,kolla项目可以制作镜像包括openstack、ceph等容器镜像, ansible是自动化部署工具,执行playbook中的任务。 kolla-ansible是容器部署工具,部署opensta...

zrz11
31分钟前
0
0
【三 异步HTTP编程】 1. 处理异步results

异步results 事实上整个Play框架都是异步的。Play非阻塞地处理每个request请求。 默认的配置适配的正是异步的controller。因此开发者应该尽力避免在在controller中阻塞,如在controller方法中...

Landas
33分钟前
0
0
Android Studio 3.1.4 buildApk遇到问题 Connection reset

打开设置,找到Android Studio选项卡,把下图选项打上勾就ok

lanyu96
34分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部