算法笔记_029-约瑟夫斯问题（Java）

package com.liuzhen.chapter4;
import java.util.Scanner;
public class JosephProblem {
/*
* 参数n:给定总人数
* 参数k:报数为k的人出列
* 函数功能：返回n个人从前到后的自杀顺序
*/
public int[] getKillOrder(int n,int k){
int[] result = new int[n];
int[] man = new int[n];
for(int i = 0;i < n;i++)
man[i] = i+1;     //给n个人编号，编号分别为1~n
int count = 0;        //用于计算当前已经自杀的人数
int pos = -1;         //用于记录遍历数组man当前下标
int tempK = 0;        //用于计算报数大小，一旦tempK = k,则喊到k的人出列
while(count < n){
pos = (pos+1)%n;         //遍历过程中，会出现环列，取余可以除去环的影响
if(man[pos] != 0)  //man[pos] == 0，表示此人已自杀
tempK++;
if(tempK == k){
result[count++] = man[pos];  //记录当前自杀人的编号
man[pos] = 0;
tempK = 0;
}
}
return result;
}
public static void main(String[] args){
JosephProblem test = new JosephProblem();
Scanner in = new Scanner(System.in);
System.out.println("请输入约瑟夫斯问题的总人数n:");
int n = in.nextInt();
System.out.println("请输入约瑟夫斯问题的报数设定值k:");
int k = in.nextInt();
int[] result = test.getKillOrder(n,k);
System.out.println("共"+n+"人，依次报数，当报到"+k+"的人自杀，其自杀顺序为：");
for(int i = 0;i < result.length;i++)
System.out.print(result[i]+"  ");
}
}

请输入约瑟夫斯问题的总人数n:
6
请输入约瑟夫斯问题的报数设定值k:
2
共6人，依次报数，当报到2的人自杀，其自杀顺序为：
2  4  6  3  1  5  
请输入约瑟夫斯问题的总人数n:
7
请输入约瑟夫斯问题的报数设定值k:
2
共7人，依次报数，当报到2的人自杀，其自杀顺序为：
2  4  6  1  5  3  7  
请输入约瑟夫斯问题的总人数n:
10
请输入约瑟夫斯问题的报数设定值k:
3
共10人，依次报数，当报到3的人自杀，其自杀顺序为：
3  6  9  2  7  1  8  5  10  4