用java写出N个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,报到m的人出圈;如此往复,找到最后一人的编号不用约瑟夫问题算法
时间: 2024-03-10 12:23:23 浏览: 52
感谢您的问题!这个问题可以使用循环链表来解决。首先,我们可以将N个人依次排成一个循环链表,每个节点表示一个人。在循环链表中,最后一个节点的next指向第一个节点,形成一个闭合的环。
接下来,我们可以进行报数和出圈的操作。设当前节点为p,每次让p从1开始报数,如果p的编号是m的倍数,则将p从链表中删除(即p的前一个节点的next指向p的下一个节点),然后令p指向下一个节点,继续报数。重复以上操作直到只剩下最后一个节点为止,最后一个节点的编号即为答案。
具体的代码实现可以参考以下示例:
```
public static int lastPerson(int N, int m) {
// create circular linked list
Node head = new Node(1);
Node p = head;
for (int i = 2; i <= N; i++) {
p.next = new Node(i);
p = p.next;
}
p.next = head;
// remove nodes one by one
p = head;
while (p.next != p) {
// count m nodes
for (int i = 1; i < m; i++) {
p = p.next;
}
// remove node
p.next = p.next.next;
// go to next node
p = p.next;
}
return p.val;
}
// definition of Node class
static class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
```
阅读全文