求组合c(n,m)的简单算法 （新手篇04）

• 萌宠菠菠乐园
• 2024-10-16 04:13

问题分析：求c(n,m)
算法设计： c(n,m)=c(n-1,m-1)+c(n-1,m)使用备忘录法避免重复求解 题目要求动态规划求组合，刚好其规律符合杨辉三角，第n+1行第m+1列，那么只要用杨辉三角的算法算出那个数。空间占用较大 由于杨辉三角性质可转化为求杨辉三角第n行m列的值使用循环队列和递推动态规划计算
算法实现（备忘录法）：
def cjs(n,m,c):
if(nm):
c[n][m]=1
return
if(m1 or n-m==1):
c[n][m]=n
return
if(c[n-1][m-1]==0):
cjs(n-1,m-1,c)
if(c[n-1][m]==0):
cjs(n-1,m,c)
c[n][m]=c[n-1][m-1]+c[n-1][m]

源代码：
#include<stdio.h>
#include<stdlib.h>
void cjs(int n, int m, int** c)
{
if (n<m)
{
printf(“输入错误，请重新输入”); //防止输入错误
}
if (n == m)
{
c[n][m] = 1;
c[n][0] = 1;
return;
}
if (m == 1 || n- m == 1)
{
c[n][m] = n;
c[n][n - m] = n;
return;
}
if (c[n - 1][m - 1] == 0) //递归
cjs(n - 1, m - 1, c);
if (c[n - 1][m] == 0)
cjs(n - 1, m, c); //递归
c[n][m] = c[n - 1][m - 1] + c[n - 1][m]; //求解
}
int main()
{
while(1)
{ int n, m;
printf(“请输入n和m的值n”);
scanf("%d %d", &n, &m);
int** c = (int**)calloc(n+1, sizeof(int));
for (int i = 0; i < n + 1; i++)
c[i] = (int*)calloc(m+ 1, sizeof(int)); //动态2维数组
cjs(n, m, c);
printf("%dn", c[n][m]);
//输出
}
}
运行结果图：

算法分析：双重for循环，时间复杂度为O(n^2)。

相关知识

求组合c(n,m)的简单算法 （新手篇04）
在python中，计算Sum = m + mm + mmm +mmmm+.....+mmmmm.....,输入两个数m,n。m的位数累加到n的值，列出算式并计算出结果：
英语翻译设图G有n个结点,以下算法产生的是最小生成树：a) 选取最小权边e1,置边数i=1,b) i=n
递归算法的时间复杂度分析
已知点C在线段AB上，线段AC=6cm，BC=4cm，点M，N分别是AC，BC的
由m=n能不能得到
请用C语言编出一个简单的宠物管理系统。
随机化算法(1) — 随机数
(SWUST OJ)《算法分析设计与实践》题库
C语言入门04

网址: 求组合c(n,m)的简单算法 （新手篇04） https://m.mcbbbk.com/newsview390277.html