今天呢，阿Q給大家?guī)硪粋€小故事，那就是著名的約瑟夫問題。公元66年，約瑟夫不情愿地參與領(lǐng)導(dǎo)了猶太同胞反抗羅馬統(tǒng)治的起義，后來起義失敗，他和一些寧死不降的起義者被困于一個山洞之中。羅馬將軍韋斯巴薌(Vespasian)派人來勸降，他主張投降，其余的人不答應(yīng)，并以死相逼。最后，約瑟夫提議，與其死在自己的手上，不如死在彼此的手上。因此他便將游戲規(guī)則告知眾人：N個人圍成一圈，從第一個人開始報數(shù)，報到m的人被殺，剩下的人繼續(xù)從1開始報數(shù)，報到m的人繼續(xù)被殺；如此往復(fù)，直到剩下最后一個人。他就是運(yùn)用這個游戲規(guī)則最終活了下來，被后人稱為約瑟夫環(huán)問題。

接下來呢，就讓我們用java代碼來模擬一下故事的進(jìn)程。

方式一：

public static void getLucklyNum(int num) {
    ArrayList<Integer> list = new ArrayList<>();        //創(chuàng)建集合存儲1到num的對象
    for(int i = 1; i <= num; i++) {
        list.add(i);                                    //將1到num存儲在集合中
    }

    int count = 1;                                      //用來數(shù)數(shù)的,只要是3的倍數(shù)就殺人
    for(int i = 0; list.size() != 1; i++) {             //只要集合中人數(shù)超過1,就要不斷的殺
        if(i == list.size()) {                          //如果i增長到集合最大的索引+1時
            i = 0;                                      //重新歸零
        }

        if(count % 3 == 0) {                            //如果是3的倍數(shù)                   
            System.out.println(list.get(i));
            list.remove(i--);                           //就殺人
        }
        count++;            
    }
}

方式二：

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();        //創(chuàng)建集合存儲1到num的對象
    for(int i = 1; i <= 20; i++) {
        list.add(i);                                    //將1到num存儲在集合中
    }
    cycleCal(list,1);
}


public static void cycleCal(ArrayList<Integer> list,int count) {
    int len = list.size();
    if (len > 1) {
        for (int i = 0; i < len; i++) {
            if (count == 3) {   //用來數(shù)數(shù)的,只要是3的倍數(shù)就殺人
                System.out.println(list.get(i));
                list.remove(i--);
                len = list.size();
                count=0;
            }
            count++;
        }
        cycleCal(list,count); //帶著count是為了形成循環(huán)，首尾相連
    }
}

第二種方法是用遞歸解決的，所謂遞歸呢，就是方法里面調(diào)用方法本身的現(xiàn)象。我們在使用遞歸時不需要明確循環(huán)次數(shù)，可以很容易的解決一些for循環(huán)和while循環(huán)很難解決的問題。

注意事項：

1）構(gòu)造方法不能遞歸

2）遞歸次數(shù)不能太多，否則就棧內(nèi)存溢出

3）遞歸必須有出口 否則就是死遞歸

接下來就舉幾個例子來了解一下。

案例一：5的階乘

public static void main(String[] args) {
    //使用遞歸求5的階乘
    System.out.println(fun(5)); //次數(shù)不能太多，否則會棧內(nèi)存溢出
}

public static int fun(int num) {
    if(num == 1) {      //if(num == 1)是遞歸出口
        return 1;
    }else {
        return num * fun(num - 1);  //調(diào)用方法本身
    }
}

案例二：文件遍歷

/**
  - 需求:從鍵盤輸入接收一個文件夾路徑,打印出該文件夾下所有的.java文件名
  - 分析:
  - 從鍵盤接收一個文件夾路徑
  - 1,如果錄入的是不存在,給與提示
  - 2,如果錄入的是文件路徑,給與提示
  - 3,如果是文件夾路徑,直接返回
  - 
  - 打印出該文件夾下所有的.java文件名
  - 1,獲取到該文件夾路徑下的所有的文件和文件夾,存儲在File數(shù)組中
  - 2,遍歷數(shù)組,對每一個文件或文件夾做判斷
  - 3,如果是文件,并且后綴是.java的,就打印
  - 4,如果是文件夾,就遞歸調(diào)用
    */
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);        //創(chuàng)建鍵盤錄入對象
    System.out.println("請輸入一個文件夾路徑");
    File dir = null;
    while(true) {
        String line = sc.nextLine();        //將鍵盤錄入的文件夾路徑存儲
        dir = new File(line);       //封裝成File對象
        if(!dir.exists()) {
            System.out.println("您錄入的文件夾路徑不存在,請重新錄入");
        }else if(dir.isFile()) {
            System.out.println("您錄入的是文件路徑,請重新錄入文件夾路徑");
        }else {
            printJavaFile（dir）;
        }
    }   
}

public static void printJavaFile(File dir){
    //獲取到該文件夾路徑下的所有的文件和文件夾,存儲在File數(shù)組中
    File[] subFiles = dir.listFiles();  
    //有的文件夾 windows系統(tǒng)不讓其訪問，所以獲取某個文件夾里面的所有文件和文件夾，有時候獲取成null
    
    //遍歷數(shù)組,對每一個文件或文件夾做判斷
    if(subFiles!=null){ //所以此處需要判斷一下獲取的subFiles數(shù)組是否為null，不判斷的話 “for (File subFile : subFiles)” 會報空指針異常
        for (File subFile : subFiles) {
            //3,如果是文件,并且后綴是.java的,就打印
            if(subFile.isFile() && subFile.getName().endsWith(".java")) {
                System.out.println(subFile);

                //4,如果是文件夾,就遞歸調(diào)用
            }else if (subFile.isDirectory()){
                printJavaFile(subFile);
            }
        }
    }
}

了解了約瑟夫問題，是不是覺得數(shù)學(xué)也能救命了？哈哈。想了解更多學(xué)習(xí)知識，請關(guān)注微信公眾號“阿Q說”，獲取更多學(xué)習(xí)資料吧！你也可以后臺留言說出你的疑惑，阿Q將會在后期的文章中為你解答。每天學(xué)習(xí)一點點，每天進(jìn)步一點點。