写一个代码作业,先写明代码思路,在关键部分写上详细注释。提示:程序运行后,首先要求用户指定初始报数上限值,然后读取各人的密码。题目要求:约瑟夫环问题的一种描述是:编号为1,2,...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求:利用单向循环链表模拟此过程,按照出列的顺序印出各人的编号,此题所用的循环链表中不需要头结点,使用尾插法。
时间: 2023-10-20 19:05:28 浏览: 95
代码思路:
1. 首先要求用户输入初始报数上限值和各人的密码,存储到链表中。
2. 然后按照题目描述的规则,依次出列每个人,并将他的密码作为新的报数上限值。
3. 重复以上步骤,直到所有人全部出列。
代码实现:
```java
import java.util.Scanner;
public class Josephus {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取初始报数上限值
System.out.print("请输入初始报数上限值:");
int m = scanner.nextInt();
// 读取各人的密码
System.out.print("请输入各人的密码(以空格分隔):");
String[] passwords = scanner.next().split(" ");
int n = passwords.length;
// 创建循环链表
Node head = new Node(1, Integer.parseInt(passwords[0]));
Node tail = head;
for (int i = 2; i <= n; i++) {
Node node = new Node(i, Integer.parseInt(passwords[i - 1]));
tail.next = node;
tail = node;
}
tail.next = head;
// 按照题目描述的规则,依次出列每个人
int count = 0;
while (tail != tail.next) {
count++;
if (count == m) {
System.out.print(tail.next.id + " "); // 输出出列的人的编号
m = tail.next.password; // 将他的密码作为新的报数上限值
tail.next = tail.next.next; // 从循环链表中删除出列的人
count = 0;
}
tail = tail.next;
}
// 输出最后一个出列的人的编号
System.out.println(tail.id);
}
// 定义循环链表节点
static class Node {
int id; // 编号
int password; // 密码
Node next; // 下一个节点
public Node(int id, int password) {
this.id = id;
this.password = password;
}
}
}
```
注释说明:
1. 在循环链表的尾部添加新节点时,我们使用 `tail.next = node` 来实现尾插法。
2. 在出列操作中,我们使用 `tail.next = tail.next.next` 来从循环链表中删除出列的人。
阅读全文