【IT168 技术】什么是约瑟夫环呢?
约瑟夫环是一个数学的应用问题：已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。
我们用程序说话，实现约瑟夫环：
import java.util.Scanner;
public class Josephus {
private static class Node {
public int no;// 编号
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();
System.out.print("请输入报数的大小：");
int cycleNum = 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) {
for (int i = 1; i < cycleNum; i++) {
pointer = pointer.next;
}
System.out.println(pointer.next.no);
pointer.next = pointer.next.next;
}
System.out.println(pointer.next.no);
}
}
public class Josephus {
private static class Node {
public int no;// 编号
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();
System.out.print("请输入报数的大小：");
int cycleNum = 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) {
for (int i = 1; i < cycleNum; i++) {
pointer = pointer.next;
}
System.out.println(pointer.next.no);
pointer.next = pointer.next.next;
}
System.out.println(pointer.next.no);
}
}
原文链接：http://tanlan.iteye.com/blog/1159502
