用java实现约瑟夫(Joseph)环
时间: 2023-12-16 14:06:26 浏览: 39
好的,下面是一个基于循环链表的 Java 代码示例,可以实现约瑟夫环问题:
```
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
class CircularLinkedList {
private Node tail;
public CircularLinkedList() {
tail = null;
}
public void add(int data) {
Node node = new Node(data);
if (tail == null) {
tail = node;
tail.next = tail;
} else {
node.next = tail.next;
tail.next = node;
tail = node;
}
}
public void remove(Node node) {
if (node == tail) {
tail = null;
} else {
Node prev = tail.next;
while (prev.next != node) {
prev = prev.next;
}
prev.next = node.next;
}
node.next = null;
}
public Node getHead() {
return tail.next;
}
}
public class Main {
public static void main(String[] args) {
int n = 10; // 总人数
int m = 3; // 数到 m 的人出圈
CircularLinkedList list = new CircularLinkedList();
for (int i = 1; i <= n; i++) {
list.add(i);
}
Node head = list.getHead();
while (list.tail != null) {
for (int i = 1; i < m; i++) {
head = head.next;
}
System.out.print(head.data + " ");
list.remove(head);
head = head.next;
}
}
}
```
这段代码中,`CircularLinkedList` 类表示循环链表,`Node` 类表示链表中的节点。在 `add` 方法中,我们根据链表的特性,将新节点插入到链表尾部即可。在 `remove` 方法中,我们需要找到要删除的节点的前一个节点,然后将它从链表中删除即可。在 `getHead` 方法中,我们可以返回链表的头部节点。
在 `main` 方法中,我们首先将 1 到 10 这十个数依次加入到链表中。然后,每次数到 m 的人出圈,直到链表为空为止。在每次出圈之前,我们需要将链表中的节点依次遍历,直到找到要出圈的节点为止。出圈后,我们需要将指针指向下一个节点,继续进行后续的计数。
希望这段代码可以帮助你解决问题,如果你还有任何疑问,欢迎随时追问。