2011年计算机等级考试二级C辅导实例编程(5)

　　所以，要计算问题的最优值 dmax ，需要分别计算出 D(1) 、 D(2) 、…… D(n) 的值，然后将它们进行比较，找出其中的最大值。根据上面分析出来的递归方程，我们完全可以设计一个递归函数，采用自顶向下的方法计算 D(i) 的值。然后，对 i 从 1 到 n 分别调用这个递归函数，就可以计算出 D(1) 、 D(2) 、…… D(n) 。但这样将会有大量的子问题被重复计算。比如在调用递归函数计算 D(1) 的时候，可能需要先计算 D(5) 的值;之后在分别调用递归函数计算 D(2) 、 D(3) 、 D(4) 的时候，都有可能需要先计算 D(5) 的值。如此一来，在整个问题的求解过程中， D(5) 可能会被重复计算很多次，从而造成了冗余，降低了程序的效率。

　　其实，通过以上分析，我们已经知道： D(n)=1 。如果将 n 作为阶段对问题进行划分，根据问题的动态规划递归方程，我们可以采用自底向上的方法依次计算出 D(n-1) 、 D(n-2) 、…… D(1) 的值。这样，每个 D(i) 的值只计算一次，并在计算的同时把计算结果保存下来，从而避免了有些子问题被重复计算的情况发生，提高了程序的效率。算法代码如下：

　　for(i=n-2;i>=0;i--){ //从后往前计算d[i]值

　　for(j=i+1;j

　　if((array[j]<=array[i])&&(d[i]

　　d[i]=d[j]+1;

　　}

　　}

　　}

　　dmax = 0;

　　xh = 1;

　　for(i=0;i

　　if(d[i]>dmax){

　　dmax = d[i];

　　xh = i;

　　}

　　}

　　cout<

　　cout<

　　int temp = xh;

　　for(i=xh+1;i

　　if(d[i]==d[temp]-1){

　　temp = i;

　　cout<

　　}

　　}

　　cout<

　　2011计算机等级二级C语言五套模拟试题及答案

　　计算机等级考试二级C语言历年真题汇总(2005-2010)

　　2011年计算机等级考试二级C语言常见问题汇总

　　计算机等级考试二级C语言常见知识点总结