代码详解Java猴子选王问题（约瑟夫环）

关于约瑟夫环的基本知识：

罗马人攻占了乔塔帕特，41人藏在一个山洞中躲过了这场浩劫。这41个人中，包括历史学家josephus和他的一个朋友。剩余的39个人为了表示不向罗马人屈服，决定集体自杀。大家决定了一个自杀方案，所有这41人围城一个圆圈，由第一个人开始顺时针报数，没报数为3的人就立刻自杀，然后由下一个人重新开始报数仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止.约瑟夫和他的朋友并不想自杀，于是约瑟夫想到了一个计策，他们两个同样参数到自杀方案中，但是最后却躲过了自杀。请问是怎么做到的

代码分享：

import java.util.HashMap;
import java.util.Map;
public class MonkeyKing {
  public static void main(String args[]) {
    int n = 100; // 猴子总数
    int m = 3; // 报数出局数
    @SuppressWarnings("rawtypes")
    Map map = new HashMap();
    int nn = 1; // 报数序号
    int mm = 1; // 报数号
    System.out.println("-----------------------" + n + "只猴子选大王开始-----------------------");
    for (int i = 1; i < n + 1; i++) {
      map.put(i, i);
    }
    while (map.size() > 1) {
      if (mm == 3) {
        map.remove(nn);
      }
      nn++;
      if (nn == n + 1) {
        nn = 1;
      }
      if (map.get(nn) != null) {
        mm++;
      }
      if (mm == m + 1) {
        mm = 1;
      }
    }
    String result = map.values().toString();
    System.out.println("第" + result.substring(1, result.length() - 1) + "只猴子当选猴王");
  }
}
赞 (0)

相关推荐

  • Java通过索引值实现约瑟夫环算法

    问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈, 剩下的人继续从1开始报数,报到m的人出圈:如此往复,直到所有人出圈 很多实现是使用链表结构,让元素构成一个圈,而我使用底层是数组的ArrayList集合实现,并且不需要遍历搜索,依靠数组特性:索引值,通过数学计算,让索引值构成一个圈,每次算出来的索引值,对应的那个元素一定是下一个出局的元素 这样的话,有n个元素,就只需要计算n次,删除n次,无需搜索,最大程度优化了程序的时间 import java.util.ArrayList; i

  • java使用链表实现约瑟夫环

    约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围.从编号为k的人开始报数,数到m的那个人出列:他的下一个人又从1开始报数,数到m的那个人又出列:依此规律重复下去,直到圆桌周围的人全部出列.求出出队序列. 采用链表实现,结点数据就是编号. package com.dm.test; public class Test2 { public static void main(String[] args) { //头结点 Node root = new Nod

  • Java简单实现约瑟夫环算法示例

    Java简单实现约瑟夫环算法示例

    本文实例讲述了Java简单实现约瑟夫环算法.分享给大家供大家参考,具体如下: 1.算法背景: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数 仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止. 约瑟夫和他的朋友并不想自杀,于是约

  • java 实现约瑟夫环的实例代码

    复制代码 代码如下: import java.io.BufferedInputStream;import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Josephus {    private static class Node{        int No;        Node next;        public Node(int No){            this

  • 代码详解Java猴子选王问题（约瑟夫环）

    关于约瑟夫环的基本知识: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止.约瑟夫和他的朋友并不想自杀,于是约瑟夫想到了一个计策,他们两个同样参数到自杀方案中,但是最后却躲过了自杀.

  • 代码详解java里的“==”和“equels”区别

    测试1: 先看一组String类型比较,废话不多说,直接上代码: public class Test { public static void main(String[] args) { String a = "java书苑"; String b = "java书苑"; String c = new String("java书苑"); String d = new String("java书苑").intern(); if(a

  • Java编程Post数据请求和接收代码详解

    这两天在做http服务端请求操作,客户端post数据到服务端后,服务端通过request.getParameter()进行请求,无法读取到数据,搜索了一下发现是因为设置为text/plain模式才导致读取不到数据 urlConn.setRequestProperty("Content-Type","text/plain; charset=utf-8"); 若设置为以下方式,则通过request.getParameter()可以读取到数据 urlConn.setReq

  • java中switch选择语句代码详解

    switch结构(开关语句)的语法 switch(表达式 ){ --->类型为int.char case 常量1 :--->case 结构可以有多个 //语句块1 break; --->程序跳出switch结构 case 常量n :--->常量的值不能相同 //语句块n break; default:--->和if结构中的 else作用相同 //语句块 break; } 下面看一段代码示例,有详细的注释,大家可以参考: public class SwitchStu{ /* s

  • Java中可变长度参数代码详解

    到J2SE1.4为止,一直无法在Java程序里定义实参个数可变的方法--因为Java要求实参(Arguments)和形参(Parameters)的数量和类型都必须逐一匹配,而形参的数目是在定义方法时就已经固定下来了.尽管可以通过重载机制,为同一个方法提供带有不同数量的形参的版本,但是这仍然不能达到让实参数量任意变化的目的. 然而,有些方法的语义要求它们必须能接受个数可变的实参--例如著名的main方法,就需要能接受所有的命令行参数为实参,而命令行参数的数目,事先根本无法确定下来. 对于这个问题,

  • 复选框和Struts2后台交互代码详解

    本文研究的主要是Struts框架中复选框的相关内容.复选框在web开发中用的非常广泛,具体介绍如下. 案例 如下图,当前为用户选中的水果为"香蕉",点击按钮,跳转到修改界面进行修改. 跳转到修改界面后要回显用户的选择(香蕉),然后由用户再次进行勾选,如图: 前台界面: <body> <form action="checBoxAction_test.action" method="post"> 请选择您喜欢的水果:<b

  • 使用AngularJS编写多选按钮选中时触发指定方法的指令代码详解

    最近在做项目时,遇到了需要用到多选按钮选中触发事件的功能,因此我查找了一下AngularJS的提供的指令,但是没有发现相应的指令.而一个看起来很像的指令就是ng-checked,但是这个指令是用来代替标签里面checked属性的,所以也用不了.因此我就自己动手试着写一个这样的指令,相应的代码如下: <form name="test_form" ng-controller="TestCtrl"> <input type="checkbox&

  • Java多线程之线程通信生产者消费者模式及等待唤醒机制代码详解

    前言 前面的例子都是多个线程在做相同的操作,比如4个线程都对共享数据做tickets–操作.大多情况下,程序中需要不同的线程做不同的事,比如一个线程对共享变量做tickets++操作,另一个线程对共享变量做tickets–操作,这就是大名鼎鼎的生产者和消费者模式. 正文 一,生产者-消费者模式也是多线程 生产者和消费者模式也是多线程的范例.所以其编程需要遵循多线程的规矩. 首先,既然是多线程,就必然要使用同步.上回说到,synchronized关键字在修饰函数的时候,使用的是"this"

  • Java回调函数实例代码详解

    首先说说什么叫回调函数? 在WINDOWS中,程序员想让系统DLL调用自己编写的一个方法,于是利用DLL当中回调函数(CALLBACK)的接口来编写程序,使它调用,这个就 称为回调.在调用接口时,需要严格的按照定义的参数和方法调用,并且需要处理函数的异步,否则会导致程序的崩溃. 这样的解释似乎还是比较难懂,这里举个简 单的例子: 程序员A写了一段程序(程序a),其中预留有回调函数接口,并封装好了该程序.程序员B要让a调用自己的程序b中的一个方法,于是,他通过a中的接口回调自己b中的方法.目的达到

  • 详解Java读取Jar中资源文件及示例代码

    详解Java读取Jar中资源文件及实现代码 直接上代码,文章的注释部分说的比较清楚,大家可以参考下, 工具类源代码: ResourceLoadFromJarUtil.java 实现代码: import java.io.IOException; import java.io.InputStream; import java.net.JarURLConnection; import java.net.MalformedURLException; import java.net.URL; import

随机推荐