import java.util.ArrayList;
/**
* 约瑟夫环 问题
* 获取幸运数字
* 思路：
* ①集合数组的
* ②递归
*/
public class josephRing03 {
public static void main(String[] args){
System.out.println("第一种方法：集合法");
System.out.println(getLuckNum01(10));
System.out.println("第二种方法：递归法");
System.out.println(getLuckNum02(10,3,8));
System.out.println(getLuckNum02(9,3,7));
System.out.println(getLuckNum02(8,3,6));
System.out.println(getLuckNum02(7,3,5));
System.out.println(getLuckNum02(6,3,4));
System.out.println(getLuckNum02(5,3,3));
System.out.println(getLuckNum02(4,3,2));
System.out.println("第三种方法：公式法");//本质也是递归
System.out.println(getlive(10, 3));
System.out.println(getlive( 9, 3));
System.out.println(getlive( 8 , 3));
System.out.println("第三.001种方法：公式形象记忆法");//本质也是递归
System.out.println(getLuckNum(10, 3));
System.out.println(getLuckNum(9, 3));
System.out.println(getLuckNum(8, 3));
}
//①数组集合法
public static int getLuckNum01(int num) {
//1.定义一个集合，并且添加人进去，10环就add十个人进去，100人环就add100个人进去
ArrayList<Integer> list = new ArrayList<>();
for (int i = 1; i <= num; i++) {
list.add(i);
}
//2.定义一个指针，区别于下面的i，这个count是直接跟人头对接的，所以要从1开始。
int count = 1;
//3.遍历所有元素，一直“杀死”人直到只剩下最后一个人即list.size()!=1时都要继续遍历
/* System.out.println(list.size());*/
for (int i=0;list.size()!=1;i++){
//4.如果已经遍历到最后一个人了，则重新开始，i重新等于0，又一个新环来进行“杀人”游戏
//注：这里要设置判断条件为list.size(),而不是list.size()-1是有原因的
//因为i作为下标一直遍历增加，直到最后一个下标，都是可以杀人的，也就是说还可以进行下面的if判断以及count++
//所以，直到i增加到list.size时，已经可以说是下标越界了，此时就要使得要越界的这个i变成0，重新开始新的“i生”（人生~哈哈哈）
if(i==list.size()){
i =0;
}
//5.当指针的对3求余为0时，去除掉list的这个元素。
//注：由于少了一个数，后面的数会补上前来，下标不变的话，i又必须得-1，才能不会错过当前的人
if(count%3 == 0){
list.remove(i--);
}
//6.count继续累加
count++;
}
return list.get(0);
}
//②递归法（大神法）
public static int getLuckNum02(int sum,int value,int n) {
if( n ==1){
return (sum+value-1)%sum;
}
else{
return (getLuckNum02(sum-1, value, n-1)+value)%sum;
}
}
//3.公式法
public static int getlive(int n,int m){
if(n == 1){return 1;}
return (getlive(n-1,m)+m-1)%n+1;//背下来就可以了
}
//3.01形象记忆公式法
public static int getLuckNum(int sumMan,int jiange){
if(sumMan == 1) {
return 1;
}
else{
return (getLuckNum(sumMan-1,jiange)+jiange-1)%sumMan+1;//背下来就可以了
}
}
}
总结：
①直接背公式。
②理解指针指向。
