今天呢，阿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将会在后期的文章中为你解答。每天学习一点点，每天进步一点点。
