2011年計算機等級考試二級C輔導實例編程(5)

　　所以，要計算問題的最優(yōu)值 dmax ，需要分別計算出 D(1) 、 D(2) 、…… D(n) 的值，然后將它們進行比較，找出其中的最大值。根據(jù)上面分析出來的遞歸方程，我們完全可以設計一個遞歸函數(shù)，采用自頂向下的方法計算 D(i) 的值。然后，對 i 從 1 到 n 分別調(diào)用這個遞歸函數(shù)，就可以計算出 D(1) 、 D(2) 、…… D(n) 。但這樣將會有大量的子問題被重復計算。比如在調(diào)用遞歸函數(shù)計算 D(1) 的時候，可能需要先計算 D(5) 的值;之后在分別調(diào)用遞歸函數(shù)計算 D(2) 、 D(3) 、 D(4) 的時候，都有可能需要先計算 D(5) 的值。如此一來，在整個問題的求解過程中， D(5) 可能會被重復計算很多次，從而造成了冗余，降低了程序的效率。

　　其實，通過以上分析，我們已經(jīng)知道： D(n)=1 。如果將 n 作為階段對問題進行劃分，根據(jù)問題的動態(tài)規(guī)劃遞歸方程，我們可以采用自底向上的方法依次計算出 D(n-1) 、 D(n-2) 、…… D(1) 的值。這樣，每個 D(i) 的值只計算一次，并在計算的同時把計算結果保存下來，從而避免了有些子問題被重復計算的情況發(fā)生，提高了程序的效率。算法代碼如下：

　　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語言常見知識點總結