排列组合的实现Cmn，Amn

2023-09-06 06:52| 来源: 网络整理| 查看: 265

递归方法:

public class Combination { /** * 计算从m个元素中选n个元素的组合数Cmn * @param m 总共有m个元素 * @param n 从中选n个元素 * @return 组合数Cmn的值 */ public static int Cmn(int m, int n) { if (n == 0 || n == m) { return 1; } else { // 两者可能，一个是选了n中的一个元素此时是Cmn(m-1, n-1)，另一个是没选n中元素是Cmn(m-1, n)。 return Cmn(m-1, n-1) + Cmn(m-1, n); } } /** * 计算从m个元素中选n个元素的排列数Amn * @param m 总共有m个元素 * @param n 从中选n个元素 * @return 排列数Amn的值 */ public static int Amn(int m, int n) { if (n > m) { return 0; // 选的元素个数大于总共的元素个数，无法排列，返回0 } else if (n == 0) { return 1; // 选的元素个数为0，只有一种排列方式 } else { return m * Amn(m-1, n-1); } } }

非递归方法（自己手动实现模仿计算方式）: 注意：再调用这个函数之前，用Cmn注意将N选比较小的。不然数据容易溢出（）具体看后续例题

public static int myCmn(int m, int n) { if (n>m){ return 0; } long res = 1; for (int i = m; i > m-n; i--) { res=res*i; } for (int i = 1; i m){ return 0; } int res = 1; for (int i = m; i > m-n; i--) { res=res*i; } return res; }

剑指 Offer II 098. 路径的数目

class Solution { public int uniquePaths(int m, int n) { int sum = m-1+n-1; int downStep = m > n?n-1:m-1; return Cmn(sum,downStep); } public int Cmn(int m, int n) { if (m < n) { return 0; } long res = 1; for (int i = m, j = 1; j

【本文地址】

排列组合的实现Cmn，Amn

排列组合的实现Cmn，Amn

今日新闻

推荐新闻