计算组合数据的数目

- 日理万妓 2022-09-30 00:39 133阅读 0赞

public static int getCMN(int m, int n) \{ if (n == m) return 1; if (n == 1) return m; return getCMN(m - 1, n) + getCMN(m - 1, n - 1); \} static int comb2(int m, int k) \{ int count = 0; for (int i = m; i >= k; i--) \{ if (k > 1) count += comb2(i - 1, k - 1); else \{ return m; \} \} return count; \}

这里是两种计算组合数的方法。 大同小异。  
第一种的思路是：  
加入从8个里面选出6个，则是入选过程：当选出的6个包含第一个元素的时候，是c75（从后面的7个中选

出5个），再加上不包含第一个元素的情况（c76）。即：c86=c75+c76;  
第二种的思路是：  
第二种是第一种的变形，在第二种中，c86=c75（包含第一个元素，从后面7个中选出5）+c65（包含第二

个元素，从后面6个中选出5个）+c55（包含第三个元素，从后面的5个中选出5个）.

两种方法的效果是一样的。

POJ2245 code如下：

package test; import java.util.Scanner; class CMN \{ public static void main(String ars\[\]) \{ Scanner cin = new Scanner(System.in); String str = cin.nextLine(); while (!str.equals("0")) \{ String\[\] strs = str.split(" "); int n = Integer.parseInt(strs\[0\]); int\[\] makeup = new int\[6\]; int\[\] nums = new int\[n\]; for (int i = 1; i <= n; i++) \{ nums\[i - 1\] = Integer.parseInt(strs\[i\]); \} for (int i = 0; i < 6; i++) \{ makeup\[i\] = 0; \} dfs(nums, makeup, 6, 0, 0); System.out.println(); str = cin.nextLine(); \} \} static void dfs(int\[\] nums, int\[\] makeup, int n, int count, int p) \{ // count表示存储在makeup\[\]中数的个数，p表示轮到处理nums\[\]的第p个数。 if (count == n) \{ // 当makeup\[\]存满6个数则输入。 for (int i = 0; i < n - 1; i++) \{ System.out.print(makeup\[i\] + " "); \} System.out.print(makeup\[5\]); System.out.println(); return; \} if (p > nums.length - 1) return; // 如果p的位置是大于数组中的位置，则返回 makeup\[count\] = nums\[p\]; dfs(nums, makeup, n, count + 1, p + 1); // 添加num\[p\]到makeup\[dep\]中。 dfs(nums, makeup, n, count, p + 1); // 没添加num\[p\]到makeup\[dep\]中。 \} \}

思路跟上面求组合的个数的思路差不多。

还是以１　２　３　４　５　６　７　８为例，从这八个数中取出来６个。

一：１在取出的结果集的６个数中时候，付给第ｃｏｕｎｔ个ｍａｋｅｕｐ的数组元素，从后面的７个数中取其他５个数。

二：１不在取出的结果集的６个数中时候，从后面的７个数中取６个数。

其他的以此类推！