- 1问题描述
- 2解决方案
- 3代码实例
1、问题描述
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解。–百度百科
2、解决方案
这里主要使用了LinkedList来存储所有人的信息,假设有n个人,编号为0-n-1,默认是从编号为0的第一个人开始报数,每次从List中取出第一个元素来,如果此时报的数是淘汰数字的整数倍,则将该元素淘汰掉,否则放到List的末尾中,循环执行这个过程直到List中的人数与要求结束的人数相等为止,返回List中的编号组成的数组即可。
3、代码实例
import java.util.LinkedList;
import java.util.Scanner;
/**
* 约瑟夫环问题,输入总人数,每个人的编号从0开始,输入一个淘汰数字,当报数的人报的数为淘汰数字的整数倍数该人淘汰,后面的人继续报数(或从新报数是一样的)
*/
public class JosephDemo {
private LinkedList<Integer> perList;
private int start;
private int scale;
private int end;
/**
* @param num
* 总人数,每个人的编号是从0开始的
* @param start
* 起始报数
* @param scale
* 报数为scale的整数倍时淘汰一个人,比如scale为3,则报数为3、6...的人会淘汰
* @param end
* 结束时剩余的人数
*/
public JosephDemo(int num, int start, int scale, int end) {
perList = new LinkedList<Integer>();
for (int i = ; i < num; i++) {
perList.add(i);
}
this.start = start;
this.scale = scale;
this.end = end;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入总人数,大于0的整数:");
int num = scanner.nextInt();
System.out.print("请输入淘汰数字,大于0的整数:");
int scale = scanner.nextInt();
System.out.print("请输入起始报数的编号,大于等于0的整数:");
int start = scanner.nextInt();
System.out.print("请输入结束时剩余的人数,大于0的整数:");
int end = scanner.nextInt();
long l = System.currentTimeMillis();
JosephDemo yd = new JosephDemo(num, start, scale, end);
Integer[] index = yd.findEnd();
System.out.print("剩下的编号为:");
for (int i = ; i < index.length; i++) {
System.out.println(index[i] + );
}
System.out.println("耗时:" + (System.currentTimeMillis() - l));
}
/**
* 找到剩下输入的结束人数时的所有编号
*
* @return
*/
private Integer[] findEnd() {
int lastNum = perList.size();
int _start = this.start;
while (lastNum != this.end) {
Integer head = perList.pop();
if (_start % scale == ) {
lastNum--;
} else {
perList.addLast(head);
}
_start++;
}
Integer[] result = perList.toArray(new Integer[]);
return result;
}
}
执行的结果:
请输入总人数,大于0的整数:1000
请输入淘汰数字,大于0的整数:13
请输入起始报数的编号,大于等于0的整数:1
请输入结束时剩余的人数,大于0的整数:1
剩下的编号为:396
耗时:16