《编写用动态规划法求组合数的算法》由会员分享，可在线阅读，更多相关《编写用动态规划法求组合数的算法（3页珍藏版）》请在装配图网上搜索。
1、题目：编写用动态规划法求组合数(Cm )的算法。n1问题分析：题目要求用动态规划法计算(Cm ),动态规划法是把多阶段过程转化为一系列单阶段n问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的方法。我把它 转化为 Cmn=C(m-l)n+C(m-l)(n-l)来求解。2数学建模：要计算Cmn=C(m-1)n+C(m-1)(n-1),建立的数学模型为：I 0行II 1行1212 行13313 行146414 行而要求的结果就是第m行第n列的数字，构造一个动态数组a100,每一次生成一行，而生 成下一行时根据上一行的数据动态更新数组中的内容，就可以实现本算法了。3算法设计：首先接收
2、用户输入的m,n的值，算法开始时，令a0=1，表示第0行，然后利用for 循环，依次依照aj=aj+aj-1来依次更新第1到第m行的数组，然后输出第m行的第n 列就行了。For循环为：for(i=1;iv=m;i+) for(ai=1,j=i-1;j=1;j-) aj+=aj-1;4算法复杂度：由上述算法可知，在更新第i层时，需要i-1个步骤，所以总的复杂度为1+2+3+.+ (m-1),即n的平方。5代码实现：#includeviostream using namespace std;#define SIZE 200 int main()int m,n;int cmn(int m,int n
3、);coutvv编写用动态规划法求组合数Cmn的算法vvendl; coutvvplease enter the m,n (m=n):;cinmn;coutvvcmn(m,n)vvendl;return 0; int cmn(int m,int n)int aSIZE;int i,j;a0=1;for(i=l;iv=m;i+) for(ai=l,j=i-l;j=l;j-) aj+=aj-1;return an;6运行结果:E:烯程l篇去年坐Debu小貫法作业編写用动态规划法求组合数Sn的算法(.m=n ) : 3 1enterplease3please10please35 please36 please 252 please 455 please 3921225 please enterenterenterenterenterenterenterthethethethethethethetherij. nrij. nrij. nrij. nrij-n(.m=n j : 5 3(.m=n ) : 7 4(.m=n ) : 9 2(.m=n ) ：15(m=n) ：100 4(.m=n:
编写用动态规划法求组合数的算法
