组合数的动态规划和递归算法

2024-01-11 07:42| 来源: 网络整理| 查看: 265

编写求解组合数C（m，n） 1、一维数组求解：把所有的都存储在一维数组a中，随着行数的增加可以求出第n行的每一个数，最后，数组中的第m个数就是要求的组合数的结果。伪代码描述：

int zuheshu(int m,int n) { int i,j; int a[100]; a[0]=1,a[1]=1; for i=0 to n do { a[i]=1; } for i=2 to n do for j=i-1 downto 1 do { a[j]=a[j]+a[j-1]; } return a[m]; }

c代码如下：

#include int zuheshu(int m,int n) { int i,j; int a[100];//利用一维数组来存储需要的组合数 a[0]=1,a[1]=1; for(i=0;i a[j]=a[j]+a[j-1]; }//算第n行的每一个元素，最后返回第m个元素就是所求的元素 return a[m]; } int main() { int n,m; int c=1; printf("Please input the number of m and n\n");//输入要求的组合数 scanf("%d",&m); scanf("%d",&n); c=zuheshu(m,n); printf("%d",c); }

结果如下：在这里插入图片描述

2、利用二维数组存储所要求的所有的组合数，组合数的顺序就是杨辉三角的顺序排列的，所以只要利用二维数组存储杨辉三角即可，杨辉三角的顺序就是除了第0列和对角线上的数为1外，其他的都是他的上面的数加上他的左面的数。伪代码描述：

main() { int a[100][100]; int i,j; int m,n; print('Please input the m and n'); input(m); sinput(n); for i=0 to n do { a[i][i]=1; a[i][0]=1; } fori=2 to n do for j=1to i-1 do { a[i][j]=a[i-1][j]+a[i-1][j-1]; } printf('a[n][m]'); }

c代码实现：

#include #define N 100 void main() { int a[100][100]; int i,j; int m,n; printf("Please input the m and n:\n"); scanf("%d",&m); scanf("%d",&n); for(i=0;i a[i][j]=a[i-1][j]+a[i-1][j-1]; } printf("%d\n",a[n][m]); }

结果如下图：在这里插入图片描述 3、递归算法求组合数的c语言表达出口的递归为m=0或者m=n的时候都为1；然后每一个的数都相当于返回的是（m,n-1）加上（m-1,n-1）最后的返回值就是我们要求得值。伪代码描述：

int diguizuhe(int m,int n) { if(m==0||m==n) return 1; else return diguizuhe(m,n-1)+diguizuhe(m-1,n-1); }

c代码描述：

#include int diguizuhe(int m,int n) { if(m==0||m==n) return 1; else return diguizuhe(m,n-1)+diguizuhe(m-1,n-1);//返回的就是最后求的结果 } int main() { int m,n; int c=1; printf("Please input the number of m and n:\n "); scanf("%d",&m); scanf("%d",&n);//输入组合数m和n的值并输出最后的结果 c=diguizuhe(m,n); printf("%d",c); }

最后的结果为：在这里插入图片描述

【本文地址】

组合数的动态规划和递归算法

组合数的动态规划和递归算法

今日新闻

推荐新闻