约瑟夫环

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知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()); }

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