关于算法:组合

在数学中,咱们学习了,排列组合,排列是有序的,组合是无程序的。在做算法题时,咱们也会遇到这种。
so,明天来理下,怎么写组合。

举个例子,桌子上有3个球A,B,C,咱们取2个,无放回的取,有几种状况?算一下:也就是C(3,2)=3。

须要解决的问题

那么先理下思路,咱们须要解决哪几个问题:

  1. 要怎么示意3个数是否被取了呢,我想,弄一个int数组把他们的初值置为0,就像int a = {0,0,0},如果他被取了,就把它置为1,三个int别离代表ABC。
  2. 而后就是从箱子里取球,是组合是吧。
  3. 最初,满足条件,输入咱们失去的组合。

计划

第一步,咱们曾经解决了,怎么示意球被取出来了。
第二步,组合:
咱们想下,以下场景:

  • 从桌子上取A,那么就是BC求组合,取B,就是AC求组合,取C,就是AB求组合
  • 持续反复,求BC的组合,就是取B进去,求C的组合,再像这样持续套娃。。。。都是调用的同一个办法,可想而知,是一个递归。

那么定义一个函数,它的作用是从a中取球,取到满足条件输入组合。再定义一个index,示意我获得是哪一个球。之后,咱们取球,如果要选,把a[index]置为1,参数curr示意曾经取了多少个球,所以也须要+1,而后再去取下一个球。如此重复。

当然咱们也能够不取这个球,不取这个球,就要把它置为0,然而须要index++,因为不取这个球,那还是须要去取下一个球,比方不取A,然而咱们还是要去BC。

紧接着找到递归进口,也就是取完2个球,或者3个球都被取完了。失去之后,就把它打印进去。也就是调用show(a[])办法。

show办法:遍历i数组,如果a[i]==1,即咱们取了,就把他输入。(char)('A'+i)+" "这也是个小细节。

代码

/*从5个小球中取出三个小球*/
public class 组合 {
    static int count;
    //很显著是一个组合问题,不必思考排列,排列的话,就能够用全排列
    public static void main(String[] args) {
        int a[] = {0,0,0};
        method1(a,0,2,0);
        System.out.println(count);
    }

    /**
     * 作用: 从a中取球,取到2个球有哪几种组合
     *
     * @param a 数组a示意以后被选中的数
     * @param index 以后被选中的数的索引
     * @param sum  要选中多少个数
     * @param curr  以后曾经选中了多少个数
     */
    private static void method1(int a[], int index, int sum, int curr) {
        if (curr == sum){
            show(a);
            count++;
            return;
        }
        //如果数组都选完了,就不能选了,之所以index == a.length,是因为最初一个也要被选
        if (index == a.length){
            return;
        }
        //以后地位要选,将这个地位改为1
        a[index] = 1;
        //判断下一个数是否要选
        method1(a,index+1,sum,curr+1);
        //以后这个地位不选,将这个地位改为0
        a[index] = 0;
        method1(a,index+1,sum,curr);

    }

    private static void show(int[] a) {
        for (int i =0; i < a.length;i++){
            if (a[i] == 1 ){
                System.out.print((char)('A'+i)+" ");//变成char与int相加为int,所以再把它变成char
            }
        }
        System.out.println();
    }
}

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理