算法学习笔记之约瑟夫环问题
博客专区 > Mr_Nice 的博客 > 博客详情
算法学习笔记之约瑟夫环问题
Mr_Nice 发表于2年前
算法学习笔记之约瑟夫环问题
  • 发表于 2年前
  • 阅读 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;
        }
    }

结果:
这里写图片描述

共有 人打赏支持
粉丝 0
博文 47
码字总数 39947
×
Mr_Nice
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: