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

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

约瑟夫环

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数http://，数到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 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());

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。