约瑟夫环问题与递归问题（详解）

今天呢，阿Q给大家带来一个小故事，那就是著名的约瑟夫问题。公元66年，约瑟夫不情愿地参与领导了犹太同胞反抗罗马统治的起义，后来起义失败，他和一些宁死不降的起义者被困于一个山洞之中。罗马将军韦斯巴芗(Vespasian)派人来劝降，他主张投降，其余的人不答应，并以死相逼。最后，约瑟夫提议，与其死在自己的手上，不如死在彼此的手上。因此他便将游戏规则告知众人：N个人围成一圈，从第一个人开始报数，报到m的人被杀，剩下的人继续从1开始报数，报到m的人继续被杀；如此往复，直到剩下最后一个人。他就是运用这个游戏规则最终活了下来，被后人称为约瑟夫环问题。

接下来呢，就让我们用java代码来模拟一下故事的进程。

方式一：

public static void getLucklyNum(int num) {
    ArrayList<Integer> list = new ArrayList<>();        //创建集合存储1到num的对象
    for(int i = 1; i <= num; i++) {
        list.add(i);                                    //将1到num存储在集合中
    }

    int count = 1;                                      //用来数数的,只要是3的倍数就杀人
    for(int i = 0; list.size() != 1; i++) {             //只要集合中人数超过1,就要不断的杀
        if(i == list.size()) {                          //如果i增长到集合最大的索引+1时
            i = 0;                                      //重新归零
        }

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

方式二：

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();        //创建集合存储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) {   //用来数数的,只要是3的倍数就杀人
                System.out.println(list.get(i));
                list.remove(i--);
                len = list.size();
                count=0;
            }
            count++;
        }
        cycleCal(list,count); //带着count是为了形成循环，首尾相连
    }
}

第二种方法是用递归解决的，所谓递归呢，就是方法里面调用方法本身的现象。我们在使用递归时不需要明确循环次数，可以很容易的解决一些for循环和while循环很难解决的问题。

注意事项：

1）构造方法不能递归

2）递归次数不能太多，否则就栈内存溢出

3）递归必须有出口 否则就是死递归

接下来就举几个例子来了解一下。

案例一：5的阶乘

public static void main(String[] args) {
    //使用递归求5的阶乘
    System.out.println(fun(5)); //次数不能太多，否则会栈内存溢出
}

public static int fun(int num) {
    if(num == 1) {      //if(num == 1)是递归出口
        return 1;
    }else {
        return num * fun(num - 1);  //调用方法本身
    }
}

案例二：文件遍历

/**
  - 需求:从键盘输入接收一个文件夹路径,打印出该文件夹下所有的.java文件名
  - 分析:
  - 从键盘接收一个文件夹路径
  - 1,如果录入的是不存在,给与提示
  - 2,如果录入的是文件路径,给与提示
  - 3,如果是文件夹路径,直接返回
  - 
  - 打印出该文件夹下所有的.java文件名
  - 1,获取到该文件夹路径下的所有的文件和文件夹,存储在File数组中
  - 2,遍历数组,对每一个文件或文件夹做判断
  - 3,如果是文件,并且后缀是.java的,就打印
  - 4,如果是文件夹,就递归调用
    */
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);        //创建键盘录入对象
    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数组中
    File[] subFiles = dir.listFiles();  
    //有的文件夹 windows系统不让其访问，所以获取某个文件夹里面的所有文件和文件夹，有时候获取成null
    
    //遍历数组,对每一个文件或文件夹做判断
    if(subFiles!=null){ //所以此处需要判断一下获取的subFiles数组是否为null，不判断的话 “for (File subFile : subFiles)” 会报空指针异常
        for (File subFile : subFiles) {
            //3,如果是文件,并且后缀是.java的,就打印
            if(subFile.isFile() && subFile.getName().endsWith(".java")) {
                System.out.println(subFile);

                //4,如果是文件夹,就递归调用
            }else if (subFile.isDirectory()){
                printJavaFile(subFile);
            }
        }
    }
}

了解了约瑟夫问题，是不是觉得数学也能救命了？哈哈。想了解更多学习知识，请关注微信公众号“阿Q说”，获取更多学习资料吧！你也可以后台留言说出你的疑惑，阿Q将会在后期的文章中为你解答。每天学习一点点，每天进步一点点。