java假设n个旅客排成一个环形,依次顺序编号1,2,…,n。从某个指定的第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到剩下k个旅客为止。 本游戏的要求用户输入的内容包括: 1. 旅客的个数,也就是n的值; 2. 离开旅客的间隔数,也就是m的值; 3. 所有旅客的序号作为一组数据要求存放在某种数据结构中。 本游戏要求输出的内容是包括 1. 离开旅客的序号; 2. 剩余旅客的序号; 所以,根据上面的模型分析及输入输出参数分析,可以定义一种数据结构后进行算法实现。
时间: 2024-03-22 16:38:50 浏览: 80
java实现的数据结构以及算法
5星 · 资源好评率100%
Java实现约瑟夫问题的代码示例:
```java
import java.util.Scanner;
public class Josephus {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter n, m, k: ");
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
scanner.close();
CircularLinkedList list = new CircularLinkedList(n);
Node curr = list.get(k - 1); // 将当前节点移动到第k个节点
while (list.size() > k) { // 循环直到链表中只剩下k个节点
curr = list.deleteNext(curr); // 删除第m个节点
System.out.print(curr.data + " "); // 输出旅客编号
if (curr == list.getTail()) { // 如果当前节点为尾节点,将其移动到头节点
curr = list.getHead();
}
for (int i = 1; i < m; i++) { // 将当前节点移动到下一个要删除的节点的前一个节点
curr = curr.next;
if (curr == list.getTail()) { // 如果当前节点为尾节点,将其移动到头节点
curr = list.getHead();
}
}
}
System.out.print("\nRemaining: ");
for (int i = 0; i < k; i++) { // 输出剩余节点的旅客编号
curr = list.deleteNext(curr);
System.out.print(curr.data + " ");
}
}
}
// 定义链表节点类
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
// 定义循环链表类
class CircularLinkedList {
private Node head;
private Node tail;
private int size;
public CircularLinkedList(int n) {
for (int i = 1; i <= n; i++) {
add(i);
}
}
// 在链表尾部添加节点
public void add(int data) {
Node node = new Node(data);
if (head == null) {
head = tail = node;
} else {
tail.next = node;
tail = node;
}
tail.next = head;
size++;
}
// 删除当前节点的下一个节点,并返回下一个节点
public Node deleteNext(Node curr) {
Node next = curr.next;
curr.next = next.next;
next.next = null;
size--;
return next;
}
// 获取链表头节点
public Node getHead() {
return head;
}
// 获取链表尾节点
public Node getTail() {
return tail;
}
// 获取链表中第k个节点
public Node get(int k) {
Node curr = head;
for (int i = 0; i < k; i++) {
curr = curr.next;
}
return curr;
}
// 获取链表大小
public int size() {
return size;
}
}
```
在main方法中,首先从标准输入读取n、m、k三个参数。然后构建一个包含n个节点的循环链表,并将当前节点移动到第k个节点。
接下来,循环执行以下操作直到链表中只剩下k个节点:
1. 删除当前节点的下一个节点,将其旅客编号输出。
2. 将当前节点移动到下一个要删除的节点的前一个节点。
如果当前节点为尾节点,则将其移动到头节点。
循环结束后,将剩余节点的旅客编号输出即可。
注意,我们使用了一个CircularLinkedList类来封装循环链表,其中包含了一些常用的方法,如添加节点、删除节点、获取节点等。在deleteNext方法中,我们删除当前节点的下一个节点,并返回下一个节点的引用,方便后续操作。在get方法中,我们通过遍历链表获取第k个节点的引用。
阅读全文