import java.util.ArrayList;
/**
* 約瑟夫環(huán) 問(wèn)題
* 獲取幸運(yùn)數(shù)字
* 思路：
* ①集合數(shù)組的
* ②遞歸
*/
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("第三種方法：公式法");//本質(zhì)也是遞歸
System.out.println(getlive(10, 3));
System.out.println(getlive( 9, 3));
System.out.println(getlive( 8 , 3));
System.out.println("第三.001種方法：公式形象記憶法");//本質(zhì)也是遞歸
System.out.println(getLuckNum(10, 3));
System.out.println(getLuckNum(9, 3));
System.out.println(getLuckNum(8, 3));
}
//①數(shù)組集合法
public static int getLuckNum01(int num) {
//1.定義一個(gè)集合袍祖，并且添加人進(jìn)去斥废，10環(huán)就add十個(gè)人進(jìn)去顷歌，100人環(huán)就add100個(gè)人進(jìn)去
ArrayList<Integer> list = new ArrayList<>();
for (int i = 1; i <= num; i++) {
list.add(i);
}
//2.定義一個(gè)指針演侯，區(qū)別于下面的i憔四，這個(gè)count是直接跟人頭對(duì)接的，所以要從1開始措拇。
int count = 1;
//3.遍歷所有元素肺蔚，一直“殺死”人直到只剩下最后一個(gè)人即list.size()!=1時(shí)都要繼續(xù)遍歷
/* System.out.println(list.size());*/
for (int i=0;list.size()!=1;i++){
//4.如果已經(jīng)遍歷到最后一個(gè)人了，則重新開始儡羔，i重新等于0，又一個(gè)新環(huán)來(lái)進(jìn)行“殺人”游戲
//注：這里要設(shè)置判斷條件為list.size(),而不是list.size()-1是有原因的
//因?yàn)閕作為下標(biāo)一直遍歷增加璧诵，直到最后一個(gè)下標(biāo)汰蜘，都是可以殺人的，也就是說(shuō)還可以進(jìn)行下面的if判斷以及count++
//所以之宿，直到i增加到list.size時(shí)族操，已經(jīng)可以說(shuō)是下標(biāo)越界了，此時(shí)就要使得要越界的這個(gè)i變成0比被，重新開始新的“i生”（人生~哈哈哈）
if(i==list.size()){
i =0;
}
//5.當(dāng)指針的對(duì)3求余為0時(shí)色难，去除掉list的這個(gè)元素。
//注：由于少了一個(gè)數(shù)等缀，后面的數(shù)會(huì)補(bǔ)上前來(lái)枷莉，下標(biāo)不變的話，i又必須得-1尺迂，才能不會(huì)錯(cuò)過(guò)當(dāng)前的人
if(count%3 == 0){
list.remove(i--);
}
//6.count繼續(xù)累加
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;//背下來(lái)就可以了
}
//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;//背下來(lái)就可以了
}
}
}
總結(jié)：
①直接背公式笤妙。
②理解指針指向。
