java链表实现约瑟夫
时间: 2024-01-15 07:16:17 浏览: 31
Java链表实现约瑟夫问题的代码如下:
```java
import java.util.LinkedList;
public class Josephus {
public static void main(String[] args) {
int n = 7; // 总人数
int m = 3; // 报数为3的出列
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
int index = 0;
while (list.size() > 1) {
index = (index + m - 1) % list.size();
System.out.println("出列:" + list.remove(index));
}
System.out.println("最后留下:" + list.get(0));
}
}
```
相关问题
用Java通过链表实现约瑟夫问题
好的,约瑟夫问题是一个经典的数学问题,描述如下:
有n个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续报数,直到剩下最后一个人。
现在我们可以使用Java中的链表来实现这个问题。具体实现步骤如下:
1. 定义一个节点类,包含一个数据域和一个指向下一个节点的指针域。
```java
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
```
2. 创建一个循环链表,并初始化数据。
```java
int n = 10; // 总人数
int m = 3; // 报数到m的人出圈
Node head = new Node(1);
Node cur = head;
for (int i = 2; i <= n; i++) {
cur.next = new Node(i);
cur = cur.next;
}
cur.next = head; // 将链表首尾相连,形成循环链表
```
3. 开始报数,找到出圈的人,重置链表。
```java
while (cur.next != cur) { // 当链表中只剩最后一个节点时结束循环
for (int i = 1; i < m; i++) { // 报数
cur = cur.next;
}
System.out.println(cur.next.data + "出圈"); // 输出出圈人的编号
cur.next = cur.next.next; // 删除出圈的人
}
System.out.println("最后一个人的编号:" + cur.data); // 输出最后一个人的编号
```
完整代码如下:
```java
public class Josephus {
public static void main(String[] args) {
int n = 10; // 总人数
int m = 3; // 报数到m的人出圈
Node head = new Node(1);
Node cur = head;
for (int i = 2; i <= n; i++) {
cur.next = new Node(i);
cur = cur.next;
}
cur.next = head; // 将链表首尾相连,形成循环链表
while (cur.next != cur) { // 当链表中只剩最后一个节点时结束循环
for (int i = 1; i < m; i++) { // 报数
cur = cur.next;
}
System.out.println(cur.next.data + "出圈"); // 输出出圈人的编号
cur.next = cur.next.next; // 删除出圈的人
}
System.out.println("最后一个人的编号:" + cur.data); // 输出最后一个人的编号
}
}
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
```
希望能够帮助到你,如有疑问请随时追问。
java实现 链表 - 约瑟夫环模拟
下面是Java实现链表-约瑟夫环模拟的示例代码:
```
import java.util.*;
public class LinkedListDemo {
public static void main(String[] args) {
int n = 7; // 约瑟夫环总人数
int m = 3; // 数到第几个人出圈
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
System.out.println("初始链表:" + list);
int count = 0;
int index = 0;
while (list.size() > 1) {
int num = list.get(index);
count++;
if (count == m) {
list.remove(index);
System.out.println("出圈的人:" + num);
count = 0;
} else {
index++;
}
if (index >= list.size()) {
index = 0;
}
}
System.out.println("剩余的人:" + list.get(0));
}
}
```
运行结果:
```
初始链表:[1, 2, 3, 4, 5, 6, 7]
出圈的人:3
出圈的人:6
出圈的人:2
出圈的人:7
出圈的人:5
出圈的人:1
剩余的人:4
```
说明:
1. 首先创建一个LinkedList对象,用来存放约瑟夫环中的人;
2. 循环添加n个人到链表中;
3. 如果链表中还有人,则继续循环;
4. 每次数到第m个人,就将该人从链表中移除,并输出该人的编号;
5. 如果链表中的当前位置已经是最后一个元素,则将当前位置重置为0;
6. 最终剩下的一个人即为约瑟夫环的胜利者。