【正文】 個(gè)數(shù) a b+1， 如此下去直至黑板上剩下一個(gè)數(shù) ， 在所有按這種操作方式最后得到的數(shù)中 ， 最大的記作 max， 最小的記作 min，則該數(shù)列的極差定義為 M=maxmin。i=i+1) print(data[i],39。 and length(n) 1) delete(n,1,1)。 delete(n,j,1)。 j=j1。 if (jj1) data[i]=j+i。 j=1。 len=length(n)。 算法 2如下： Delete_digit（ ） {char n[100]。 } 算法說明 1： 注意記錄刪除位置不一定是要?jiǎng)h除數(shù)字 d的下標(biāo)，因?yàn)橛锌赡?d的前或后有可能已經(jīng)有字符被刪除， d的前面已經(jīng)有元素刪除容易想到，但一定不要忽略了其后也有可能已刪除了字符，實(shí)例 2中刪除 1時(shí)，其后的 2已被刪除。i=s。039。i=i+1) { j=leni+1。 break。j=j+1) if (n[j]n[j+1]) //貪婪選擇 {delete(n,j,1)。 for (i=0。 len=length(n)。} Delete_digit（ ） {char n[100]。按題目要求 設(shè)置數(shù)組 data記錄刪除的數(shù)字所在位置 delete(char n,int b,int k) {int i。 2） 同樣還是利用數(shù)組 ， 記錄未刪除字符的下標(biāo) ， 粗略的過程如下： n=“1 2 4 3 5 8 3 3” 0 0 0 0 0 0 4比 3大 刪除 “ 1 2 3 5 8 3 3” 1 2 4 5 0 0 8比 3大 刪除 “ 1 2 3 5 3 3” 1 2 4 5 0 5比 3大 刪除 “ 1 2 3 3 3” 1 2 4 7 8 這時(shí)數(shù)組好象是數(shù)據(jù)庫中的索引文件 。這樣可能會(huì)有比較多字符移動(dòng)操作，算法效率不高。特別地還要考慮若結(jié)果串是“ 0000”時(shí)，不能將全部 “ 0”都刪除，而要保留一個(gè) “ 0”最后輸出。 由此可知通過實(shí)例設(shè)計(jì)算法時(shí) ， 枚舉的實(shí)例一定要有全面性 ，實(shí)例最好要能代表所有可能的情況 ， 或者在必要時(shí)多列舉幾個(gè)不同的實(shí)例 。根據(jù)輸出要求設(shè)置數(shù)組 ， 在刪除數(shù)字時(shí)記錄其位置 。編程對(duì)給定的 N和 S， 尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小 。 貪婪算法 沒有固定的算法框架 ， 算法設(shè)計(jì)的關(guān)鍵是貪婪策略的選擇 。 一定要注意 ， 選擇的貪婪策略要具有 無后向性 。 輸入數(shù)據(jù)均不需判錯(cuò) 。 上節(jié) 下節(jié) 可絕對(duì)貪婪問題 問題分析 在位數(shù)固定的前提下 ， 讓高位的數(shù)字盡量小其值就較小 ， 依據(jù)此貪婪策略就可以解決這個(gè)問題 。 再看以下兩個(gè)實(shí)例又可總結(jié)出一些需要算法特殊處理的情況 。 由此可以看出進(jìn)行算法設(shè)計(jì)時(shí)，從具體到抽象的歸納一定要選取大量不同的實(shí)例，充分了解和體會(huì)解決問題的過程、規(guī)律和各種不同情況，才能設(shè)計(jì)出正確的算法。 1） 可以利用數(shù)組記錄字符的存在狀態(tài) ， 元素值為 “ 1”表示對(duì)應(yīng)數(shù)字存在 ， 元素值為 “ 0”表示對(duì)應(yīng)數(shù)字已刪除 。 此方式同樣存在操作比較復(fù)雜的問題 。 for(i=b。 int s,i,j,j1,c,data[100],len。 if(slen) {print(“data error”)。i=s 。 if (jj1) data[i]=j+i。 } if( jlength(n)) break。delete(n,j,1)。 and length(n) 1) delete(n,1,1)。i=i+1) print(data[i],39。要想使記錄刪除的位置操作簡(jiǎn)便，使用算法設(shè)計(jì) 1中的介紹第二種刪除方式最簡(jiǎn)單，請(qǐng)讀者嘗試實(shí)現(xiàn)這個(gè)設(shè)計(jì)。 int s,i,j,c,data[100],len。 if(slen) {print(“data error”)。 j1=0。 else data[i]=data[i1]1。} } for (i=i。 data[i]=j。 print(n)。 39。 問題分析 算法設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 算法分析 上節(jié) 下節(jié) 問題分析 和上一個(gè)例題一樣 ， 我們通過實(shí)例來認(rèn)識(shí)題目中描述的計(jì)算過程 。這是一道兩次運(yùn)用貪心策略解決的問題 。 所以不但要選取最大和最小 ， 還必須記錄它們的位置 ， 以便將其覆蓋 。 int s1,s2。 print(“input these data”)。 b[j]=a[j]。 while (n2) { max2(a,n)。} return(a[1]* a[2]+1)。} else { s1=2。j++) { if (a[j]a[s1]) { s2=s1。 while (n2) { min2(a,n)。} return(a[1]* a[2]+1)。} else { s1=2。j++) if (a[j]a[s1]) { s2=s1。 由于計(jì)算最大結(jié)果和計(jì)算最小結(jié)果需要獨(dú)立進(jìn)行 ,所以算法的空間復(fù)雜度為 O(2n)。 問題分析 數(shù)學(xué)模型 算法設(shè)計(jì) 算法 上節(jié) 下節(jié) 問題分析 基本思想是 ， 逐步選擇分?jǐn)?shù)所包含的最大埃及分?jǐn)?shù) ， 這些埃及分?jǐn)?shù)之和就是問題的一個(gè)解 。 這樣我們就找到了分?jǐn)?shù) F所包含的 “ 最大的 ” 埃及分?jǐn)?shù)就是 1/C。否則轉(zhuǎn)步驟 (2). 上節(jié) 下節(jié) 例： 7/8=1/2+1/3+1/24的解題步驟： 同樣用變量 A表示分子 ， 變量 B表示分母； C=8+1=2 /說明 7/81/2， 打印 1/2 A=7*28=6， B=B*C=16 /在計(jì)算 7/81/2=(7*28)/(7*2)=6/16=A/B C=16/6+1=3 /說明 16/61/3， 打印 1/3 A=6*316=2， B=B*C=16*3=48 /在計(jì)算 6/161/3=(6*316)/(16*3)=2/48=A/B A1但 B/A為整數(shù) 24， 打印 1/24 結(jié)束 . 上節(jié) 下節(jié) 算法 main（） { int a,b,c。 input(b)。 if (b mod a =0 ) { print (+1/。 } } 【 例 4】 幣種統(tǒng)計(jì)問題 【 例 5】 取數(shù)游戲 上節(jié) 下節(jié) 相對(duì)或近似貪婪問題 ， 貪婪策略都是適用的 ，因此我們稱它們?yōu)?“ 可絕對(duì)貪婪問題 ” 。請(qǐng)編程完成 。這樣，七種 幣值就可表示為 B[i],i=1,2,3,4,5,6,7。 input(n)。 for(j=1,j=7。} } for(i=1?！?,否則將會(huì)重復(fù)計(jì)算 。 在這樣的幣值種類下 ,再用貪婪算法就行不通了 ,比如某人工資是 140,按貪婪算法140=100*(1張 )+20*(2張 )共需要 3張 ,而事實(shí)上 ,只要取 2張 70面額的是最佳結(jié)果 ,這類問題可以考慮用動(dòng)態(tài)規(guī)劃算法來解決 。 問題分析 算法設(shè)計(jì) 算法說明 算法分析 上節(jié) 下節(jié) 問題分析 這個(gè)游戲一般假設(shè)取數(shù)者只能看到 2n個(gè)數(shù)中兩邊的數(shù) ,用貪婪算法的情況 : 若一組數(shù)據(jù)為： 6,16,27,6,12,9,2,11,6,5。 這時(shí)一般的策略是用 近似貪婪算法 。 這是對(duì)第一個(gè)回合的分析，顯然對(duì)以后整個(gè)取數(shù)過程都適用。 算法設(shè)計(jì) ：有了以上建立的高效數(shù)學(xué)模型，算法就很簡(jiǎn)單了，算法只需要分別計(jì)算一組數(shù)的奇數(shù)位和偶數(shù)位的數(shù)據(jù)之和，然后就先了取數(shù)者就可以確定必勝的取數(shù)方式了。 main( ) {int i,s1,s2,data。i=n。 if(s1s2) print(“first take left”)。 當(dāng)達(dá)到某算法中的某一步不需要再繼續(xù)前進(jìn)時(shí) ， 算法停止 。 更準(zhǔn)確的方法是通過數(shù)學(xué)方法證明問題對(duì)貪婪策略的選用性 。 上節(jié) 下節(jié) : 首先貪婪算法的原理是通過局部最優(yōu)來達(dá)到全局最優(yōu) ,采用的是逐步構(gòu)造最優(yōu)解的方法 。 上節(jié) 下節(jié) 在動(dòng)態(tài)規(guī)劃算法策略中 ， 體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進(jìn)行決策 , 并通過多階段決策來最終解決問題 。 上節(jié) 下節(jié) 動(dòng)態(tài)規(guī)劃 我們通過一個(gè)簡(jiǎn)單的例子來說明動(dòng)態(tài)規(guī)劃的多階段決策與貪婪算法有什么區(qū)別 。用貪婪的策略，則路徑和分別為： 9+15+8+9+10=51 （自上而下）， 19+2+10+12+9=52（自下而上）。 上節(jié) 下節(jié) 以上的決策結(jié)果將五階數(shù)塔問題變?yōu)?4階子問題，遞推 出第四層與第五層的和為 : 21(2+19),28(18+10),19(9+10),21(5+16)。二維數(shù)組 a的存儲(chǔ)內(nèi)容如下： d[n][j]=data[n][j] j=1,2,?? ,n； i=n1,n2,?? 1， j=1,2,?? ,i；時(shí) d[i][j]=max(d[i+1][j]， d[i+1][j+1])+data[i][j] 最后 a[1][1]存儲(chǔ)的就是問題的結(jié)果。 上節(jié) 下節(jié) 數(shù)塔問題的算法 main( ) { int a[50][50][3],i,j,n。 input(n)。 a[i][j][2]=a[i][j][1]。i) for (j=1 。} else { a[i][j][2]=a[i][j][2]+a[i+1][j+1][2]。 j=1。 j=j+a[i][j][3]。 上節(jié) 下節(jié) 動(dòng)態(tài)規(guī)劃算法的問題及決策應(yīng)該具有三個(gè)性質(zhì)：最優(yōu) 化原理、無后向性、子問題重疊性質(zhì)。 上節(jié) 下節(jié) 算法框架 2. 動(dòng)態(tài)規(guī)劃的基本思想 動(dòng)態(tài)規(guī)劃方法的基本思想是 ， 把求解的問題分成許多