Josephus环的四种解法(约瑟夫环)基于java详解

约瑟夫环

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。

通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解

引用别人的一个图：直观说明问题

分析：

  • 第一步：从1开始报数为3的时候就删除3号结点
  • 第二步：从4号结点开始报数，当为3的时候删除6号结点；
  • 第三步：从7号结点开始报数，当为3的时候删除1号结点；
  • 第四步：从2号结点开始报数，当为3的时候删除5号结点；
  • 第五步：从7号结点开始报数，当为3的时候删除2号结点；
  • 第六步：从4号元素开始报数，当为3的时候删除8号结点；
  • 第七步：又从4号开始报数，当为3的时候删除4号结点，此时链表中只有一个7号结点，所以最后的结点就是7号结点；

1.模拟解法

public class 模拟 {
  public static void main(String[] args) {
    Scanner in=new Scanner(System.in);

    //总人数
    int n=in.nextInt();
    // 数到m的那个人出列
    int m=in.nextInt();
    // 初始化为0 都没有出去
    int [] arr=new int[n];

    //剩下的人数
    int peopleLeft=n;
    //初始化下标
    int index=0;
    // 下标计算器
    int count=0;
    // >0 出循环为负
    while (peopleLeft>1){
      if(arr[index]==0){
        // count为计步器 不是下标指向
        count++;
        if(count==m){
          arr[index]=1;
          count=0;
          peopleLeft--;
        }
      }
      index++;
      if(index==arr.length){
        index=0;
      }
    }
    for (int i = 0; i < arr.length; i++) {
      if(arr[i]==0){
        System.out.println(i+1);
      }
    }
  }
}

2.递归解法

/**
   * 递归式:
   * f(1)=0; 第一个位置永远为0
   * f(i)=f(i)+m%n;
   */
  public static int yuesefu(int n,int m){
    if(n==1){
      return 0;
    }else {
      return (yuesefu(n-1,m) + m) % n;
    }
  }
  public static void main(String[] args) {
    System.out.println(yuesefu(41,3)+1);
    vailCode(41,3);
  }

  //逆推验证代码
  public static void vailCode(int a,int b){
    System.out.print(b);
    int reslut;
    for (int i = a; i >=2 ; i--) {
       reslut=2;
      for (int j = i; j <=a ; j++) {
        reslut=(reslut+b)%j;
      }
      System.out.printf("->%d",reslut+1);
    }
  }

3.循环链表解法

public class CircularLinkedList {
  public static void main(String[] args) {
    /**
     * 节点类
     */
    class Node{
      private int data=1;
      private Node next;
      Node(){
        next=null;
      }
    }

    Node head,temp;
    head=new Node();
    head.data=1;

    int a=41;
    int b=3;
    // 临时节点
    temp=head;
    for (int i = 0; i < a; i++) {
      Node new_node=new Node();
      new_node.data=i+1;
      temp.next=new_node;
      temp=new_node;
    }
    temp.next=head.next;
    while (head.next!=head){
      for (int i = 0; i < b-1; i++) {
        head=head.next;
      }
      System.out.print("->"+(head.data+1));
      head.next=head.next.next;
    }
    System.out.println(head.data);
  }
}

4.Collection解法

public static void main(String[] args) {
    int a=41;
    int b=3;
    LinkedList<Integer> list = new LinkedList<>();
    for (int i = 0; i < a; i++) {
      list.add(i+1);
    }
    while (list.size()>1){
      for (int i = 0; i < b-1; i++) {
        list.add(list.remove());
      }
      System.out.print("->"+list.getFirst());
      list.remove();//remve head
    }
    System.out.println(list.getFirst());
  }

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • selenium+java+chrome环境搭建的方法步骤

    我只能说因为版本冲突,简直太折腾了,而搜了无数个博友的帖子才找到正确条案,就不能好好的写篇文章吗? 最近真的是太闲太闲了,平时没事总得搞点技术,不然心里感觉好空虚, 最近看上了selenium,所以试一下 没啥目标 头一篇这个环境搞的崩溃了,都是版本冲突,目前为止,我还未有解决firefox与selenium的版本冲突问题 这是一篇只讲chrome的文章 1.selenium下载最新版本,我在官网下载的 http://selenium-release.storage.googleapis.com

  • Java新手环境搭建 Tomcat安装配置教程

    Java新手环境搭建 Tomcat安装配置教程

    安装 Tomcat 之前请一定先安装 Java ,然后才能安装 Tomcat . 安装 Java .环境变量 path 的设置以及 cmd 小技巧请看:Java新手环境搭建 JDK8安装配置教程 下载 Tomcat 首先到 Tomcat 的官方网站下载 Windows 版本的 Tomcat 最新版,根据我们所使用的操作系统,我们下载 64 位 Windows 的 zip 版本.不建议使用 Installer 版本. 我们以 apache-tomcat-9.0.0.M15-windows-x64.

  • 详解java解决分布式环境中高并发环境下数据插入重复问题

    java 解决分布式环境中 高并发环境下数据插入重复问题 前言 原因:服务器同时接受到的重复请求 现象:数据重复插入 / 修改操作 解决方案 : 分布式锁 对请求报文生成 摘要信息 + redis 实现分布式锁 工具类 分布式锁的应用 package com.nursling.web.filter.context; import com.nursling.nosql.redis.RedisUtil; import com.nursling.sign.SignType; import com.nu

  • JAVA环境搭建之MyEclipse10+jdk1.8+tomcat8环境搭建详解

    JAVA环境搭建之MyEclipse10+jdk1.8+tomcat8环境搭建详解

    一.安装JDK 1.下载得到jdk-8u11-windows-i586.1406279697.exe,直接双击运行安装,一直next就可以,默认是安装到系统盘下面Program Files, 我这里装在D:\Program Files\Java下面,注意安装完jdk之后会自动运行安装jre,这时的安装路径最好和jdk一样,方便管理,我的都是在D:\Program Files\Java下面. 2.环境变量配置: 右击"我的电脑",点击"属性":选择"高级系统

  • Java+Eclipse+Selenium环境搭建的方法步骤

    先选好自己要学的Selenium的版本然后再进行安装,少走弯路,,,, ===================================所需环境========================== 1.安装JAVA (我用的版本jdk-8u191-windows-x64) 官网:http://www.oracle.com/technetwork/java/javase/downloads/index.html java环境分JDK和JRE,JDK就是Java Development Kit

  • Java新手环境搭建 JDK8安装配置教程

    最近有时间,写一些很简单.很基础的东西,主要在操作层面.主要考虑如下: 1.经常搭建开发环境,所以有必要记录一下,自己也可以备查: 2.给新手看,写一些最最简单实用的东西. 1.确认 Java 没有安装过 首先先确认我们的电脑上没有安装 Java,打开命令行,输入 java -version,看到如下显示就说明 Java 还没有被安装. 2.在 Java 没有安装过,到官网下载 Java 最新版本 接下来到 Oracle 的网站上下载 Java 最新版本.百度搜索关键字"oradle java&

  • Java 8跳过本次循环,继续执行以及跳出循环,终止循环的代码实例

    Java 8跳过本次循环,继续执行以及跳出循环,终止循环的代码实例

    在Java8之前,最开始使用for i 循环,很老旧,后来有了高级的for each 循环,然后这个跳出本次循环和跳出所有的for循环,都简单,稍微没见过的就是跳出多层for循环. 然后就是Java8出的foreach循环,这个循环里面,break和continue都不管用啦.需要使用return,这个只能跳过本次循环,还是会继续执行for循环的,那么怎么跳出这个Java8的foreach循环呢? 下面对所有的循环,都来了一次操作. 看看如何,跳出当前循环,继续执行:或者直接跳出for循环:或者

  • Java中break、continue、return在for循环中的使用

    引言:在使用循环的时候,循环里面带有break.continue.return的时候经常弄混,今天特意整理了下,以待后用... for (int i = 1; i < 5; i++) { System.out.println("i==for=>"+i); while(i%2==0){ System.out.println("i==while==>"+i); break;//终止while循环,继续for后面的代码;(终止当前(while)循环,继续

  • Josephus环的四种解法(约瑟夫环)基于java详解

    约瑟夫环 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3-n分别表示)围坐在一张圆桌周围.从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列. 通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解 引用别人的一个图:直观说明问题 分析: 第一步:从1开始报数为3的时候就删除3号结点 第二步:从4号结点开始报数,当为3的时候删除6号结点: 第三步:从7号结点开始报数,当为

  • Java中四种线程池的使用示例详解

    在什么情况下使用线程池? 1.单个任务处理的时间比较短 2.将需处理的任务的数量大 使用线程池的好处: 1.减少在创建和销毁线程上所花的时间以及系统资源的开销 2.如不使用线程池,有可能造成系统创建大量线程而导致消耗完系统内存以及"过度切换". 本文详细的给大家介绍了关于Java中四种线程池的使用,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍: FixedThreadPool 由Executors的newFixedThreadPool方法创建.它是一种线程数量固定的线程

  • Java Rabbitmq中四种集群架构的区别详解

    Java Rabbitmq中四种集群架构的区别详解

    目录 主备模式 远程模式 镜像模式 多活模式 Federation插件 总结 Rabbitmq 四种集群架构 1. 主备模式 2. 远程模式3. 镜像模式  4. 多活模式 主备模式 主备模式: warren 兔子窝 一个主.一个备方案 主节点如果挂了 从节点提供服务 和Activemq 利用zk 做主/备一样 主备模式 ----------------------->HaProxy 配置 listen rabbitmq_cluster bind 0.0.0.0:5682 # 配置tcp 模式

  • MySQL 四种连接和多表查询详解

    MySQL 四种连接和多表查询详解

    目录 MySQL 内连接.左连接.右连接.外连接.多表查询 构建环境: 一.INNER JION 内连接 ( A ∩ B ) 二.LEFT JOIN 左外连接( A 全有 ) 三.RIGHT JOIN 右外连接 (B 全有) 四.FULL JOIN 全外连接( A + B) 五.LEFT Excluding JOIN ( A - B 即 A 表独有)+ 六.RIGHT Excluding JOIN ( B - A 即 B表独有) 七.OUTER Excluding JOIN (A 与 B 各自独

  • Java详解实现多线程的四种方式总结

    Java详解实现多线程的四种方式总结

    目录 前言 一.四种方式实现多线程 1.继承Thread类创建线程 2.实现Runnable接口创建线程 3.实现Callable接口 4.实现有返回结果的线程 二.多线程相关知识 1.Runnable 和 Callable 的区别 2.如何启动一个新线程.调用 start 和 run 方法的区别 3.线程相关的基本方法 4.wait()和 sleep()的区别 5.多线程原理 前言 Java多线程实现方式主要有四种: ① 继承Thread类.实现Runnable接口 ② 实现Callable接

  • 关于php几种字符串连接的效率比较(详解)

    php大致有三种字符串连接: 1.直接用.来进行连接. 2.用.=进行连接. 3.先压入数组,再通过join函数连接. 下面分别对这三种方法的效率进行测试: 第一种方法代码如下: <?php function get_tm() { list ( $usec, $sec ) = explode ( " ", microtime () ); return (( float ) $usec + ( float ) $sec); } $temp="test"; $re

  • JS中正则表达式只有3种匹配模式(没有单行模式)详解

    JS正则表达式对象模式仅有如下三种:  g (全文查找出现的所有 pattern) i (忽略大小写) m (多行查找) 即没有单行匹配模式,Singleline(单行模式):更改.的含义,使它与每一个字符匹配(包括换行符\n). 如java中 String regex = "(?s)(?<=interface).{0,500}(shutdown)";---------"."表示在一行. 但可以采用[\d\D]或[\w\W]或[\s\S]或(.|\s)*?来解

  • Linux下几种并发服务器的实现模式(详解)

    1>单线程或者单进程 相当于短链接,当accept之后,就开始数据的接收和数据的发送,不接受新的连接,即一个server,一个client 不存在并发. 2>循环服务器和并发服务器 1.循环服务器:一个server只能一次只能接收一个client,当当前client结束访问之后才能进行下一个client的连接. 2.并发服务器:一个server同一时间可以响应很多客户端的访问. 3>select+多线程模式 并发服务器的三种实现方式 1.多进程并发服务器 是指TCP连接后,每一个客户机的

  • Python之两种模式的生产者消费者模型详解

    第一种使用queue队列实现: #生产者消费者模型 其实服务器集群就是这个模型 # 这里介绍的是非yield方法实现过程 import threading,time import queue q = queue.Queue(maxsize=10) def Producer(anme): # for i in range(10): # q.put('骨头%s'%i) count = 1 while True: q.put('骨头%s'%count) print('生产了骨头',count) cou

  • python 安装库几种方法之cmd,anaconda,pycharm详解

    python安装库的几种方法 在python项目开发的过程中,需要安装大大小小的库,本文会提供几种安装库的方法,总有一种可以帮到大家. 安装的方法主要有三种: ①利用命令框安装库. ②利用pycharm的环境配置界面安装库. ③利用anaconda直接安装库(几乎无所不能). ①利用命令框安装python库 首先进命令行界面(cmd),利用conda指令打开演示用的anaconda环境(名称为tf1.13) conda activate tf1.13 如下图所示,进入名为tf1.13的环境(最前

随机推荐