应用一个递归的方法来显示由一群人组队的所有可能方案(由n个每次挑k个)。编写递归的showTeams()方法和一个main()方法来提示用户输入人群的人数以及组队的人数,以此来作为 showTeams()的参数,然后显示所有的组合。

解决方案 »

  1.   


    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);
    }}
      

  2.   

    感谢你的方法,但是我觉得当n,k都很大的时候这个方法复杂度太高,我想用分治法来做,
    如(5,3)=(4,2)+(4,3),再依次分解(4,2),(4,3),这样的复杂度是O(nlogn)
    但是在递归我过程中我不知道怎么把选定的人答应出来。你有没什么方法?
      

  3.   

    一个数学问题而已 Cm人 n个人一组 方法 就有 m*(m-1)*(m-n+1)/1*2*n
      

  4.   


    这个是输出编号
    []里面放编号
    import java.util.Scanner;public class Choose {
    public static void showTeams(int[] array, int i, int chooseNum, int[] ) {
    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([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];
    int[]  = new int[total];
    for (int i = 0; i < array.length; ++i) {
    array[i] = 0;
    [i] = i + 1;
    }
    showTeams(array, 0, chooseNum, );
    }}
      

  5.   

    int a = Convert.ToInt32(Console.ReadLine());
                int c = Convert.ToInt32(Console.ReadLine());
                int k=1;
                int m=1;
                for (int i = a; i >= a-c+1; i--)
                {
                    k *= i;
                }
                for (int j = 1; j <= c; j++)
                {
                    m *= j;
                }
                int l = k / m;
                Console.WriteLine(l);
                Console.ReadLine(); l为 有多少种 k是你输入的人数  m是你需要的组队人数
      

  6.   

    我也来凑个热闹,
    贴个用泛型的
    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);
    }}
      

  7.   

    不错,就是n选k,递归为n-1选k-1
      

  8.   

    又是排列组合的问题,凑个热闹吧,递归和非递归写法
    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;
                    }
                }
            }
        }
    }
      

  9.   

    感谢你的方法,但是我觉得当n,k都很大的时候这个方法复杂度太高,我想用分治法来做,如(5,3)=(4,2) (4,3),再依次分解(4,2),(4,3),这样的复杂度是O(nlogn)但是在递归我过程中我不知道怎么把选定的人答应出来。你有没什么方法?你说得这个我知道,例如。是将五个分解成三个集合。
    考虑两种情况:1,假设最后一个元素单独一个集合,那么只需考虑将剩下的四个分解成两个集合…4→2
    2,假设最后一个元素不是单独一个集合。那么就考虑4→3。然后将最后一个分别加入即可。你的不适合你问的这个。记得有一楼是用二进制来做的。那个应该满足你问的。
      

  10.   

    感谢各位,在各位的指导下,我也写了一个方法,结帖前,把代码贴上。再次谢谢大家!
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;public class TeamChoice6 {
    int [] a;
    int end;
    List<Integer> selected = new ArrayList<Integer>();
        public TeamChoice6(int n, int k) {

    a = new int[n];
    for(int i=1;i<=n;i++)
    a[i-1] = i;
    end = a.length-1;
    } public  void showTeams(int start, int need) { 
    if(need == 0)
    System.out.println(selected);
    else{
    for(int i=start;i<=end -need+1;i++){
    selected.add(a[i]);
    showTeams(i+1,need-1);
    selected.remove(new Integer(a[i]));
    }
    }
         
        }    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
            System.out.println("please input amount of group: ");
            int n = sc.nextInt();
            System.out.println("please input amount of team: ");
            int k = sc.nextInt();
            sc.close();
            TeamChoice6 tc = new TeamChoice6(n,k);
            tc.showTeams(0,k);
        }}