约瑟夫问题。N个人围成一圈,第一个人开始从1报数,报到M的将被杀掉,下一个人接着从1开始报数,如此反复,最后剩一个。求最后的胜利者。 要求:循环链表实现 (java类)
时间: 2024-06-14 12:05:24 浏览: 187
以下是使用循环链表实现约瑟夫问题的Java类的示例代码:
```java
public class JosephusProblem {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
static int getJosephusPosition(int n, int m) {
Node head = new Node(1);
Node prev = head;
for (int i = 2; i <= n; i++) {
prev.next = new Node(i);
prev = prev.next;
}
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 = 5; // 总人数
int m = 2; // 报数到m的人将被杀掉
int winner = getJosephusPosition(n, m);
System.out.println("The winner is: " + winner);
}
}
```
阅读全文