在数学中,咱们学习了,排列组合,排列是有序的,组合是无程序的。在做算法题时,咱们也会遇到这种。
so,明天来理下,怎么写组合。
举个例子,桌子上有 3 个球 A,B,C,咱们取 2 个,无放回的取,有几种状况?算一下:也就是 C(3,2)=3。
须要解决的问题
那么先理下思路,咱们须要解决哪几个问题:
- 要怎么示意 3 个数是否被取了呢,我想,弄一个 int 数组把他们的初值置为 0,就像
int a = {0,0,0}
, 如果他被取了,就把它置为 1,三个 int 别离代表 ABC。 - 而后就是从箱子里取球, 是组合是吧。
- 最初,满足条件,输入咱们失去的组合。
计划
第一步,咱们曾经解决了,怎么示意球被取出来了。
第二步,组合:
咱们想下,以下场景:
- 从桌子上取 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();}
}