美文网首页算法第四版习题讲解
算法练习(43): 约瑟夫问题(1.3.37)

算法练习(43): 约瑟夫问题(1.3.37)

作者: kyson老师 | 来源:发表于2017-11-17 23:44 被阅读226次

本系列博客习题来自《算法(第四版)》,算是本人的读书笔记,如果有人在读这本书的,欢迎大家多多交流。为了方便讨论,本人新建了一个微信群(算法交流),想要加入的,请添加我的微信号:zhujinhui207407 谢谢。另外,本人的个人博客 http://www.kyson.cn 也在不停的更新中,欢迎一起讨论

算法(第4版)

知识点

  • 约瑟夫问题

题目

1.3.37 Josephus 问题。在这个古老的问题中,N 个身陷绝境的人一致同意通过以下方式减少生存人数。他们围坐成一圈(位置记作 0 到 N-1)并从第一个人开始报数,报到 M 的人会被杀死,直到最后一个人留下来。传说中 Josephus 找到了不会被杀死的位置。编写一个 Queue 的用例 Josephus,从命令行接受 N 和 M 并打印出人们被杀死的顺序(这也将显示 Josephus 在圈中的位置)。


1.3.37 Josephus problem. In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange them- selves in a circle (at positions numbered from 0 to N–1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated. Write a Queue client Josephus that takes N and M from the command line and prints out the order in which people are eliminated (and thus would show Josephus where to sit in the circle).

% java Josephus 7 2 
1 3 5 0 4 2 6

分析

本人所有简书的算法文章详细分析已经移入小专栏:算法四习题详解,欢迎大家订阅

f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)

答案

public class Josephus {

    public static void main(String[] args) {

        int m = 3;
        int N = 41;

        Queue<Integer> queue = new Queue<Integer>();
        for (int i = 0; i < N; i++)
            queue.enqueue(i);

        while (!queue.isEmpty()) {
            for (int i = 0; i < m - 1; i++)
                queue.enqueue(queue.dequeue());
            StdOut.print(queue.dequeue() + " ");
        }
        
        StdOut.println();
    }
}

打印的结果为:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30
因此,第31个人是最后一个被杀死的,第16个人是倒数第二个被杀死的

代码索引

Josephus.java

视频讲解

广告

我的首款个人开发的APP壁纸宝贝上线了,欢迎大家下载。

相关文章

  • 算法练习(43): 约瑟夫问题(1.3.37)

    本系列博客习题来自《算法(第四版)》,算是本人的读书笔记,如果有人在读这本书的,欢迎大家多多交流。为了方便讨论,本...

  • 算法之约瑟夫问题

    把我上学时候在csdn上的笔记搬过来了,便于自己查找 经典的约瑟夫问题 题目:假设下标从0开始,0,1,2 .. ...

  • 1.3.37 Josephus问题

    解法: 测试: 结果:

  • 算法题—约瑟夫环问题

    前言 本文编程语言使用Java 问题概述 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕...

  • 算法 js 解决约瑟夫问题

  • 约瑟夫算法

    1.约瑟夫算法:约瑟夫环:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的 人开始报数,...

  • 约瑟夫算法

    约瑟夫环问题是一个非常著名的趣题,即由n个人坐成一圈,按顺时针由1开始给他们编号。然后由第一个人开始报数,数到m的...

  • 约瑟夫问题的一个简单java实现

    约瑟夫问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约...

  • 算法-约瑟夫环

    有一个数组a[n]顺序存放0~n-1,要求每隔step个数删掉一个数,到末尾时循环至开头继续进行,求最后一个被删掉...

  • 约瑟夫环算法

    什么是约瑟夫环呢?约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在...

网友评论

    本文标题:算法练习(43): 约瑟夫问题(1.3.37)

    本文链接:https://www.haomeiwen.com/subject/qovsvxtx.html