Question

java 约瑟夫环问题 数据结构

输入人数，每个人有一个密码，比如说从第一个开始，他的密码是3，则报到第3个人，第三个人出来，第三个人的密码是2，则继续报到第5个人，第五个人出来
。。。
这程序怎么不对啊？？？

import java.util.Scanner;

public class Josephus {
private static class Node {
public int no;// 编号
public int password;//密码
public Node next;// 下一个节点

public Node(int no) {
this.no = no;

}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入总人数：");
int totalNum = scanner.nextInt(); //输入人数
for(int i=1;i<=totalNum;i++){
System.out.println("请输入第个"+i+"人的密码：");
new Node(i).password = scanner.nextInt();
}//输入每个人的密码

Node header = new Node(1);
Node pointer = header;
for (int i = 2; i <= totalNum; i++) {
pointer.next = new Node(i);
pointer = pointer.next;
}
pointer.next = header;
// 初始化环形链表结束
System.out.println("以下是出列的顺序:");
while (pointer != pointer.next){
int a = 0;
for (int i=1; i<=totalNum; i++){
a=new Node(i).password;
for (int j=1;j<a;j++){
pointer = pointer.next;
}
}
System.out.println(pointer.next.no);
pointer.next = pointer.next.next;
}
System.out.println(pointer.next.no);
}
}

Answer 1

这个问题没那么简单，我分析了一下
1.出列的人，你没有删掉，虽然你输出了，但是却还在数组里面
2.假如有一个人被删除了，那么他的密码就无效了，这个需要考虑
3.还要考虑这是一个圈，也就是说，到了最后一个人，就要循环从头开始算

具体你写的不是数据结构相关的，看起来像，实际使用用普通算法而已

追问

谢谢 我们学链表的时候的作业 就是说只是要求用链表实现这个过程 如果说只是实现这个过程 我还要怎么改改啊？ 先把过程实现了，以后更好的算法还要向您请教。

追答

我们JAVA课本中有关于线性表和约瑟夫的实例的，一般的书上都有，你利用那个线性表去做算法就容易了，至于用普通的算法就没什么必要了，把简单问题复杂化不是好事，你会出栈入栈的话，就能自己编出来，自己先试试比较好，我也是学生！！