分别利用顺序和链式结构存储结构解决约瑟夫环问题的具体java代码
时间: 2024-05-10 17:14:31 浏览: 4
使用顺序存储结构的Java代码:
```java
import java.util.Scanner;
public class JosephusProblemSeq {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入总人数:");
int n = scanner.nextInt();
System.out.print("请输入报数的大小:");
int m = scanner.nextInt();
boolean[] isOut = new boolean[n];
int outCount = 0;
int index = -1;
while (outCount < n) {
for (int i = 0; i < m; i++) {
index = (index + 1) % n;
while (isOut[index]) {
index = (index + 1) % n;
}
}
isOut[index] = true;
outCount++;
System.out.println("第" + outCount + "个出圈的人是:" + (index + 1));
}
}
}
```
使用链式存储结构的Java代码:
```java
import java.util.Scanner;
public class JosephusProblemLinked {
static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入总人数:");
int n = scanner.nextInt();
System.out.print("请输入报数的大小:");
int m = scanner.nextInt();
Node head = new Node(1);
Node tail = head;
for (int i = 2; i <= n; i++) {
tail.next = new Node(i);
tail = tail.next;
}
tail.next = head; // 形成环
int outCount = 0;
Node prev = tail; // 初始值为 tail,因为从 tail 开始报数
while (outCount < n) {
for (int i = 0; i < m; i++) {
prev = prev.next;
}
System.out.println("第" + (outCount + 1) + "个出圈的人是:" + prev.next.value);
prev.next = prev.next.next;
outCount++;
}
}
}
```