一个递归的小程序，求解
应用一个递归的方法来显示由一群人组队的所有可能方案(由n个每次挑k个)。编写递归的showTeams()方法和一个main()方法来提示用户输入人群的人数以及组队的人数，以此来作为 showTeams()的参数，然后显示所有的组合。
[解决办法]
假设5人编号为1.2.3.4.5
假设挑3个
排列如下；
123 124 125
134 135
234 235
245
345
看出规律了吧。
后面一个都比前面一个多1。如果最后一个达到最大值5了。就倒数第二个加一。。一直循环。用一个标记为位就可以了。无需用递归。我说的简单，这个规律很容易写代码出来。
手机打字。谅解。。。
[解决办法]
- Java code
import java.util.Scanner;/** * 输出1的被选中。0的未被选中 * @author * */public class Choose { public static void showTeams(int[] array, int i, int chooseNum) { if (i >= array.length) { int cnt = 0; for (int j = 0; j < array.length; ++j) cnt += array[j]; if (cnt == chooseNum) { for (int j = 0; j < array.length; ++j) System.out.print(array[j] + " "); System.out.println(); } return; } array[i] = 1; ++i; showTeams(array, i, chooseNum); array[i - 1] = 0; showTeams(array, i, chooseNum); } public static void main(String[] args) { int total, chooseNum; Scanner sc = new Scanner(System.in); total = sc.nextInt(); chooseNum = sc.nextInt(); int[] array = new int[total]; for (int i = 0; i < array.length; ++i) array[i] = 0; showTeams(array, 0, chooseNum); }}
[解决办法]
- Java code
这个是输出编号mark[]里面放编号import java.util.Scanner;public class Choose { public static void showTeams(int[] array, int i, int chooseNum, int[] mark) { if (i >= array.length) { int cnt = 0; for (int j = 0; j < array.length; ++j) cnt += array[j]; if (cnt == chooseNum) { for (int j = 0; j < array.length; ++j) { if (array[j] == 1) System.out.print(mark[j] + " "); } System.out.println(); } return; } array[i] = 1; ++i; showTeams(array, i, chooseNum, mark); array[i - 1] = 0; showTeams(array, i, chooseNum, mark); } public static void main(String[] args) { int total, chooseNum; Scanner sc = new Scanner(System.in); total = sc.nextInt(); chooseNum = sc.nextInt(); int[] array = new int[total]; int[] mark = new int[total]; for (int i = 0; i < array.length; ++i) { array[i] = 0; mark[i] = i + 1; } showTeams(array, 0, chooseNum, mark); }}
[解决办法]
我也来凑个热闹，
贴个用泛型的
- Java code
import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class ChooseMInN2 { static int total; static int need; static List<Integer> selected = new ArrayList<Integer>(); public static void showTeams(int current ) { if (selected.size()==need){ //成功 System.out.println(selected); return; } if (current>total) return; //失败 showTeams(current+1); //不加当前元素，继续探索 selected.add(current); showTeams(current+1); //加当前元素，继续探索 selected.remove(new Integer(current)); //回溯 } public static void main(String[] args) { Scanner sc = new Scanner(System.in); total = sc.nextInt(); need = sc.nextInt(); showTeams(1); }}
[解决办法]
又是排列组合的问题，凑个热闹吧，递归和非递归写法
- Java code
import java.util.*;public class Test { public static void main(String[] args) throws Throwable { Scanner sc = new Scanner(System.in); System.out.printf("please input amount of group: "); int n = sc.nextInt(); System.out.printf("please input amount of team: "); int k = sc.nextInt(); sc.close(); System.out.println("------method 1------"); showTeam(0, n, k, new StringBuilder()); //递归 System.out.println("------method 2------"); showTeam2(n, k); //非递归 } public static void showTeam(int start, int n, int k, StringBuilder buf) {//递归 if (k<1 || n<k || n<=start) return; if (k==1) { //递归结束 for (int i=start; i<n; i++) { System.out.printf("%s%d\n", buf.toString(), i+1); } return; } String s = buf.toString(); for (int i=start; i<n; i++) { buf.delete(0, buf.length()); buf.append(s).append(i+1); showTeam(i+1, n, k-1, buf); //递归调用 } } public static void showTeam2(int n, int k) { //非递归，模拟二进制进位， //二进制位是1表示选中，是0表示非选中 if (k<1 || n<k) return; int[] idx = new int[n]; //二进制位 idx[idx.length-1] = 1; //二进制最低位设置为1，表示选中 int cnt = 0; //选中的个数 StringBuilder buf = new StringBuilder(); while (idx[0] < 2) { cnt = 0; buf.delete(0, buf.length()); for (int i=0; i<idx.length; i++) { if (idx[i] == 1) { //如果二进制位是1 cnt++; //选中+1 buf.append(data[i]); //挑出对象 } } if (cnt == k) { //如果选中个数是k，则打印结果 System.out.println(buf); } idx[idx.length-1]++; //二进制进位 for (int i=idx.length-1; i>0; i--) { if (idx[i] == 2) { idx[i] = 0; idx[i-1]++; } else { break; } } } }}