Josephus环的四种解法(约瑟夫环)基于java详解
作者:---dgw博客 发布时间:2022-02-28 23:29:13
标签: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());
}
来源:https://www.cnblogs.com/dgwblog/p/10086189.html
0
投稿
猜你喜欢
- 一、字符串:1、访问String中的字符:string本身可看作一个Char数组。string s = "hello world&
- RocketMQ 是什么Github 上关于 RocketMQ 的介绍:RcoketMQ 是一款低延迟、高可靠、可伸缩、易于使用的消息中间件
- 有些人可能对线程池比较陌生,并且更不熟悉线程池的工作原理。所以他们在使用线程的时候,多数情况下都是new Thread来实现多线程。但是,往
- 一、题目描述题目实现:一个服务器与多个客户端通信。通过一个服务器与多个客户端进行通信,运行程序,服务器启动后,启动两个客户端程序,然后通过服
- 一、项目创建创建一个控制台应用程序,项目右键->管理 NuGet 程序包->Topshelft及Topshelf.Log4Net
- Java定义Long数据类型Long lg=10L;只需要在定义的的整型后面加个L;就和定义float数据类型一样Float ft=5.20
- ##创建测试类 新建Java工程创建测试类如下代码:(创建文件验证定时器是否执行)package makeFile;import java.
- Java 执行 JS 脚本工具用途:为了便于系统扩展,提供了 JS 脚本的功能,可以通过在系统中执行脚本来获得更复杂的功能。例如:系统提供了
- java简易小游戏制作游戏思路:设置人物移动,游戏规则,积分系统,随机移动的怪物,游戏胜负判定,定时器。游戏内容部分package 代码部分
- 本文实例为大家分享了Java手写线程池的实现代码,供大家参考,具体内容如下1.线程池是一种多线程处理形式,处理过程中将任务添加到队列,然后在
- 如果你是一名Web开发人员,那么用膝盖想也知道你的职业生涯大部分将使用Java而度过。这是一款商业级的编程语言,我们没有办法不接触它。对于J
- 这篇文章主要介绍了springboot自定义异常视图过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需
- 这篇文章主要介绍了Java如何把数组转换为ArrayList,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需
- 配置文件context-path的坑context-path: /manage 这个配置加入后会导致访问spring的页面都需要加这个/ma
- 1. strlen —— 求字符串长度1.1 strlen 的声明与用处strlen ,我们有一些英
- 本文适合有 Java 基础的人群作者:DJL-LankingHelloGitHub 推出的《讲解开源项目》系列。有幸邀请到了亚马逊 + Ap
- 这篇文章主要介绍了Java中遍历ConcurrentHashMap的四种方式详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一
- 策略模式的应用场景策略模式是否要使用,取决于业务场景是否符合,有没有必要。是否符合如果业务是处于不同的场景时,采取不同的处理方式的话,就满足
- 一.你了解类吗?在Java中,类文件是以.java为后缀的代码文件,在每个类文件中最多只允许出现一个public类,当有public类的时候
- 做消息通信,消息会不断从网络流中取得,而后台也有线程不断消费。本来我一直是使用一些线程安全标识或方法来控制,后来在网上找到一些java新特性