约瑟夫问题
Question
N个人围成一圈，从第一个人开始报数，报到M的人出圈，剩下的人继续从1开始报数，报到M的人出圈；如此往复，直到所有人出圈。（模拟此过程，输出出圈的人的序号）
Answer
解法一： 假设有n个人，从1到n，放入一个ArrayList中。 设置开始的编号k(设为0，为第一个人），加上需要报的数减1，即得到需要出列人的索引。 要注意要出列的人是不是最后一个人，要特殊处理。当ArrayList为空，则完成。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Solution {
public static void Josephus(int totalNum, int countNum) {
List<Integer> start = new ArrayList<Integer>();
for(int i=1; i<=totalNum; i++) {
//初始化人数
start.add(i);
}
int k = 0;
while(start.size() != 0) {
k = k+countNum;
k = k%(start.size())-1; //得到第m人的索引位置，所以要-1
if(k == -1) {
//到队尾
System.out.println(start.get(start.size()-1));
start.remove(start.size()-1);
k = 0;
}else {
System.out.println(start.get(k));
start.remove(k);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int totalNum = scanner.nextInt();
int countNum = scanner.nextInt();
Josephus(totalNum, countNum);
scanner.close();
}
}
//input：10 3
//output：3 6 9 2 7 1 8 5 10 4
解法二： 用队列
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Solution {
public static void countQueue(int totalNum, int countNum) {
Queue<Integer> queue = new LinkedList<Integer>();
for(int i=1; i<=totalNum; i++) {
queue.add(i);
}
int count = 0; //计数器
while(!queue.isEmpty()) {
int person = 0;
person = queue.poll(); //出队列
count++;
if(count % countNum == 0) {
//是，出队
System.out.println(person);
}else {
//不是，继续入队列
queue.add(person);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int totalNum = scanner.nextInt();
int countNum = scanner.nextInt();
countQueue(totalNum, countNum);
scanner.close();
}
}
