约瑟夫环问题

发布时间:2024年01月15日

📑前言

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

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

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

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());
			}
		}
	}

}

📑文章末尾

在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_61494821/article/details/135600519
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。