约瑟夫问题,n个人围成一圈,第一个人开始从1报数,报到M的将被杀掉,下一个人接着从1开始报数,如此反复,最后剩一个,求最后的胜利者。用循环链表实现,用Java代码写出
时间: 2024-06-14 10:05:23 浏览: 121
以下是使用循环链表实现约瑟夫问题的Java代码:
```java
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class JosephusProblem {
public static int findSurvivor(int n, int m) {
// 创建循环链表
Node head = new Node(1);
Node prev = head;
for (int i = 2; i <= n; i++) {
Node newNode = new Node(i);
prev.next = newNode;
prev = newNode;
}
prev.next = head; // 将链表首尾相连
// 开始报数并删除节点
Node curr = head;
while (curr.next != curr) {
// 找到要删除的节点的前一个节点
for (int i = 1; i < m - 1; i++) {
curr = curr.next;
}
// 删除节点
curr.next = curr.next.next;
curr = curr.next;
}
return curr.data; // 返回最后剩下的节点的值
}
public static void main(String[] args) {
int n = 3; // 人数
int m = 2; // 报数到m的人将被杀掉
int survivor = findSurvivor(n, m);
System.out.println("The last survivor is: " + survivor);
}
}
```
阅读全文