2011年計(jì)算機(jī)等級(jí)考試二級(jí)C輔導(dǎo)實(shí)例編程(5)

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

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

　　for(i=n-2;i>=0;i--){ //從后往前計(jì)算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計(jì)算機(jī)等級(jí)二級(jí)C語(yǔ)言五套模擬試題及答案

　　計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言歷年真題匯總(2005-2010)

　　2011年計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言常見(jiàn)問(wèn)題匯總

　　計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言常見(jiàn)知識(shí)點(diǎn)總結(jié)