递归实例，欢迎大家修改优化

问题一

昨天同事提了一个问题：有50个学生站成圆圈（学号为1~50），从1开始报数，报数为4的倍数的学生离开圆圈，剩下的继续报数直至全部离开，问最后一个离开圆圈的是哪个同学？

说这个能使用递归实现了话请大家吃饭，赶紧上代码，今天大家等着吃饭呢！

 1    /**
 2      * 获取最后一个离开圆圈的学生
 3      * @param list 学生学号集合
 4      * @param hao 即将报的数
 5      * @return 
 6      */
 7     public static List<Integer> getNum(List<Integer> list,int hao){        
 8         //不等于一个继续报数
 9         if (list.size() != 1) {
10             //报数为4的倍数的下标集合
11             List<Integer> listIndex = new ArrayList<Integer>();
12             for (int i = 0; i < list.size(); i++) {
13                 if ((i+hao) % 4 == 0) {
14                     listIndex.add(i);                
15                 }        
16             }
17             //报数
18             hao = hao + list.size();
19             //删除报数为4的倍数的学生
20             for (int i = listIndex.size()-1; i >= 0; i--) {
21                 System.out.println("remove  "+list.get(listIndex.get(i)));
22                 int index = listIndex.get(i);
23                 list.remove(index);            
24             }
25             //继续报数递归
26             list = getNum(list, hao);
27         }        
28         return list;        
29     }

main方法

1     List<Integer> list = new ArrayList<Integer>();
2     for (int j = 1; j < 51; j++) {
3         list.add(j);
4     }
5     list = getNum(list, 1);
6     System.out.println("num  "+list.get(0));

执行过程

/**
*第1圈：[1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 45, 46, 47, 49, 50] 即将报数号： 51
*第2圈： [1, 3, 5, 6, 9, 10, 11, 14, 15, 17, 19, 21, 22, 25, 26, 27, 30, 31, 33, 35, 37, 38, 41, 42, 43, 46, 47, 49]  即将报数号：89
*第3圈： [1, 3, 5, 9, 10, 11, 15, 17, 19, 22, 25, 26, 30, 31, 33, 37, 38, 41, 43, 46, 47]  即将报数号：117
*第4圈： [1, 3, 5, 10, 11, 15, 19, 22, 25, 30, 31, 33, 38, 41, 43, 47]  即将报数号：138
*第5圈： [1, 3, 10, 11, 15, 22, 25, 30, 33, 38, 41, 47] 即将报数号：154
*第6圈： [1, 3, 11, 15, 22, 30, 33, 38, 47]  即将报数号：166
*第7圈： [1, 3, 15, 22, 30, 38, 47]  即将报数号：175
*第8圈： [1, 15, 22, 30, 47] 即将报数号：182
*第9圈： [1, 15, 30, 47] 即将报数号：187
*第10圈： [1, 30, 47] 即将报数号：191
*第11圈： [1, 47] 即将报数号：194
*第12圈： [1, 47] 即将报数号：196
*第13圈： [47] 即将报数号：198
*/

问题二

研究北京赛车PK10前几投注注数（不重复组合），开奖号码为：1~10不能重复，

如前二（冠亚必选），冠军选球：4 5 6 亚军选球：5 6 7 8 。投注注数（不重复组合）为10注。

如前三（前三必选），根据如下选球注数为72注。

如前四（前四必选），根据如下选球注数为110注。

代码如下

递归算法：

 1     /**
 2      * 递归处理前几
 3      * @param counts 注数
 4      * @param ball 球号
 5      * @param tb_ball 选球组合
 6      * @return
 7      */
 8     public static int getCount(int counts,String ball,List<List<Integer>> tb_ball){        
 9         List<Integer> t = null;
10         List<List<Integer>> tb_ball1 = new ArrayList<List<Integer>>();      
11         if(tb_ball.size()>0){
12             t = tb_ball.get(0);  
13             tb_ball1.addAll(tb_ball);
14             tb_ball1.remove(0);         
15         }
16         if (t!=null){
17             for(int k=0; k<t.size();k++){                        
18                 if(ball.indexOf(","+t.get(k)+",") >= 0){                                    
19                     continue;
20                 }                
21                 if (tb_ball1.size() == 0) {
22                     counts++;                
23                 } else {
24                     ball = ball + t.get(k)+",";    
25                     counts = getCount(counts,ball, tb_ball1);    
26                     ball = ball.replace(t.get(k)+",", "");
27                 }                          
28             }           
29         }         
30         return counts;
31     }

main方法

 1             int counts = 0;
 2             //如上前二测试
 3             List<List<Integer>> listAll = new ArrayList<List<Integer>>();
 4             List<Integer> listOne = new ArrayList<Integer>();
 5             listOne.add(4);
 6             listOne.add(5);
 7             listOne.add(6);
 8             List<Integer> listTwo = new ArrayList<Integer>();
 9             listTwo.add(5);
10             listTwo.add(6);
11             listTwo.add(7);
12             listTwo.add(8);
13             listAll.add(listOne);
14             listAll.add(listTwo);
15             counts = getCount(counts, ",", listAll);
16             System.out.println("前二注数为：" + counts);

结果：前二注数为：10

有兴趣的伙伴可以自己测试。