约瑟夫环问题

📑前言

本文主要是【数据结构】——约瑟夫环问题的文章，如果有什么需要改进的地方还请大佬指出??

🎬作者简介：大家好，我是听风与他🥇
??博客首页：CSDN主页听风与他
🌄每日一句：狠狠沉淀，顶峰相见

• 问题描述:
• n个人按顺序围成一圈(编号为1~n),从第1个人从1开始报数，报到k的人出列，相邻的下个人重新从1开始报数，报到k的人出列，重复这个过程，直到队伍中只有1个人为止，这就是约瑟夫问题。现在给定n和k，你需要返回最后`剩下的那个人的编号。

1.数组版

package practice;

import java.util.Scanner;

public class 找出游戏的获胜者 {
/*
5 2
3
 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int total = 0;
		int a[] = new int[n+1];
		for(int i=1;i<=n;i++) {
			a[i] = i;
		}
		int i = 0;//记录数组下标
		int num = 0;//计数器
		while(true) {
			if(a[i]!=0) {
				num++;
			}
			if(num == k) {
				a[i] = 0;
				num = 0;
				total++;
			}
			i++;
			if(i==n+1) i = 1;
			//需要淘汰n-1人
			if(total==n-1) break;
		}
		for(i=1;i<=n;i++) {
			if(a[i]!=0) {
				System.out.println(a[i]);
			}
		}
	}

}

2.单链表版

package practice;

import java.util.Scanner;

public class 约瑟夫环链表版 {

	static class Node{
		int val;
		Node next;
		public Node(int val) {
			this.val = val;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		Node head = new Node(1);
		Node pre = head;
		for(int i=2;i<=n;i++) {
			pre.next = new Node(i);
			pre = pre.next;
		}
		pre.next=head;//形成循环链表，最后一个指向头
		int count = 1;
		//头等于尾时，结束，此时链表中只剩下一个元素
		while(head.next!=head) {
			if(count==k-1) {//下一个元素就是要出列的元素
				System.out.println(head.next.val+"->");
				head.next = head.next.next;//下一个出列
				count=1;//计数器归1
			}
			else count++;//无需出列，计数器+1
			head = head.next;//每次都后移一个
		}
		System.out.println(head.val);
	}

}

3.队列版

package practice;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 约瑟夫环队列版 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int count = 1;//计数器
		Queue<Integer> q = new LinkedList<>();
		for(int i=1;i<=n;i++) {
			q.offer(i);
		}
		while(!q.isEmpty()) {
			if(count==k) {
				System.out.println(q.poll()+"->");
				count=1;
			}
			else {
				count++;
				//已经数过的数字放到尾部去
				q.offer(q.poll());
			}
		}
	}

}

📑文章末尾