【正文】 那里購買一定量的牛奶，才能使包裝牛奶制造商所要付出的錢最少。 ? 具體算法實現(xiàn)：將所有的價格按照從小到大的排序，然后順序購買，即每次向當(dāng)前價格最低的那個農(nóng)民購買牛奶，如果該農(nóng)民手上的牛奶數(shù)量不足以滿足需求，則繼續(xù)向下一個農(nóng)民購買，以此類推，直到買到足夠多的牛奶，此時得到的即為最優(yōu)解。 ? k,t:longint。 rewrite(out)。 b[j]:=t。 end else begin k:=k+a[i]*n。已知第 i種貨物的重量為 Wi，其總價值為 Pi，設(shè)定 M， Wi， Pi均為整數(shù)，編程確定一個裝貨方案， ? 使得裝入背包中的貨物總價值最大。 ? 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。所以多多總共耗費體力 =3+12=15。該資源一次只能被一個活動所占用，每一個活動有一個開始時間 bi和結(jié)束時間 ei（ bi≤ei ）。 type node=record no:integer。 readln(n)。a[i]:=t。 end。end。 ? Min2— 在由 i站直接可達(dá)的所有油站中，單位油價最便宜（但高于 i站）的一個油站。 ? 算法框架： ? K:=0。 ? if (min2=0)or(pjpmin2) then min2:=j。 {汽車抵達(dá) min1站時油正好耗盡 } ? k:=min1。每個線段由它的兩個端點 ai和bi確定， i=1， 2， ?? ， N。接下來就有這么多行（按照坐標(biāo)升序排列的剩下的線段），每行兩個整數(shù)分別表示一條線段的左端點和右端點。 ? 求解問題時，我們就從初始的一個或若干個數(shù)據(jù)項出發(fā)，通過遞推關(guān)系式逐步推進，從而得到最終結(jié)果?，F(xiàn)在從鍵盤輸入 n、 m，要你計算出卒從 A點能夠到達(dá) B點的路徑條數(shù)。因此司機必須設(shè)法在沿途建立幾個儲油點，使卡車能順利穿越沙漠，試問司機如何建立這些儲油點？每一儲油點應(yīng)存多少油才能使卡車以消耗最少汽油的代價通過沙漠（結(jié)果保留小數(shù)點后兩位）？ ? 編程計算及打印建立的儲油點序號，個儲油點距離沙漠邊緣出發(fā)的距離及儲油量。 dis[1]=500。 {從 i=1處開始向始點倒推 } ? dis[1]:=500。 {置始點至終點的距離值 } ? d1:=1000dis[k1]。 ? writeln(s)。 ? begin ? if i=1 then f:=1 ? else f:=f(i1)+i。 這種利用遞歸函數(shù)或遞歸方法解決問題的過程稱為遞歸算法。 ? var ? n:integer。 fac(4) 4* fac(3) 3* fac(2) 2* fac(1) 1* fac(0) 1 1 2 6 24 邊界條件 ? 例題：利用遞歸調(diào)用技術(shù)求斐波那契數(shù)列的第 N項。 ? begin ? readln(n)。歐幾里得算法基于的方法是重復(fù)應(yīng)用等式 gcd(m,n)=gcd(n,m mod n)，直到 m mod n等于 0。 ? end。gcd=39。n=39。 ? begin ? r:=m mod n。利用這個方法，可以較快地求出兩個自然數(shù)的最大公因數(shù)。 ? begin ? if k=2 ? then fac:=1 ? else fac:=fac(k1)+fac(k2)。 ? writeln(n,?!=?,fac(n))。當(dāng) n的值遞減至 0時， n!=1，從而使遞歸得以結(jié)束。這是因為按照上面的程序執(zhí)行，f(0)=f(1)+0，要求 f(1)就要求f(2)， … 如此下去 f(i)永遠(yuǎn)無法得到解， “ 遞 ” 的過程一去不復(fù)返，直到耗盡系統(tǒng)分配的空間，怎能“ 歸來 ” 呢。 ? var ? n:integer。 ? begin ? s:=0。 ? until d=1000。為了在 i=n處取得 500*nL汽油，卡車至少從始點開 n+1次滿載車至 i=n，加上從i=n返回始點的 n趟返程空車，合計 2n+1次， 2n+1趟的總耗油量應(yīng)正好為（ 1000dis[n]） （ 2n+1），即始點藏油為 oil[n]+(1000dis[n]) （ 2n+1） dis[n] 1000－ dis[n] 終點 始點 i=0 i=n ? 算法框架： ? k:=1。兩點之間的距離必須滿足在耗油最少的條件下使 i點儲足 500iL汽油的要求（ 0≤i ≤ n 1）。則，可得如下遞推公式： ? F[i， j]=0 { g[i,j]=1 } ? F[i， 0]= F[i1， 0] { i0,g[i,j]=0 } ? F[0， j]= F[0， j1] { j0,g[i,j]=0 } ? F[i， j]= F[i1， j]+ F[i， j1] { i0,j0,g[i,j]=0 } ? 解決遞推類型問題有三個重點： ? 一是如何建立正確的遞推關(guān)系式，二是遞推關(guān)系有何性質(zhì)，三是遞推關(guān)系式如何求解。卒不能通過對方馬的控制點。 遞推與遞歸 ? 遞推是一種簡潔高效的數(shù)學(xué)模型，如我們熟悉的 Fibonacci數(shù)列問題，F(xiàn)（ 1） =0， F（ 2） =1，在 n2時有： F（ n1） +F（ n2）。接下來有 N行，每行有兩個空格隔開的整數(shù)，表示一條線段的兩個端點的坐標(biāo)。 ? until k=n+1。 {若 min1站位于 k站左方， ? 則不需加油 } ? cost:=cost+pk*need。 ? while (jn+1)and(Dj– Dk ≤C*D2 )do { 在 k站直接可達(dá)的所有油站中，計算油價低于 k站且距離 最近的一個油站序號 min1和油價最低的一個油站序號 min2} ? begin ? j:=j+1。設(shè) k表示當(dāng)前站（ 0 ≤ k ≤ n+1 ）； j表示由 k站駛往的下一目的站（ k j ≤ n+1 ） 。汽車目前在 i站（ 0≤i≤n ），應(yīng)加多少油，駛往哪一站可以是得整個行程的花費最少？我們不妨采用下面的貪心策略： ? 下一個目的站的單位油價盡可能低于 i站，如果所有可能到達(dá)油站的單位油價都高于 i站的話，則下一個目的站的單位油價亦應(yīng)該盡可能的便宜。 39。 if k=n then begin a[i].next:=k。 if ki then begin t:=a[k]。 i,j,k,s,l,m,n:integer。然后依次分析遞增序列中的活動 2至活動 n，每次將與 s中的活動兼容的活動加入到集合 s中。 ? 【 樣例輸入 】 ? 3 1 2 9 ? 【 樣例輸出 】 ? 15 ? 【 數(shù)據(jù)規(guī)模 】 對于 30％的數(shù)據(jù)，保證有 n=1000： 對于 50％的數(shù)據(jù)，保證有 n=5000； 對于全部的數(shù)據(jù)，保證有 n=10000?？梢韵葘? 2堆合并，新堆數(shù)目為 3，耗費體力為 3。 ? begin ? 讀入數(shù)據(jù)； ? 計算貨物的單位重量價值 Ti，并將它們按從大到小排序； ? 依次選擇單位重量較大的貨物放入背包，直至不能放入； ? 輸出最大價值總和 S和裝貨方案； ? end. ? 例題：合并果子（ noip 042） ? 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。 close(output)。 if n=b[i] then begin k:=k+a[i]*b[i]。 ? t:=b[i]。39。 ? m:integer。 ? 輸出：一個整數(shù)，表示包裝牛奶制造商拿到所需的牛奶所要付出的最小費用。 ? 包裝牛奶制造公司從一些農(nóng)民那里購買牛奶，每個農(nóng)民賣給牛奶制造公司的價格不一定相同，而且，一只母牛一天只能生產(chǎn)一定量的牛奶，因此農(nóng)民每一天只能有一定量的牛奶可以賣。L39。 lp:=lp+1。 rp:=rp1； end。 ? if SA=SB then j:=1 else begin ? j:=0。 ? A?。? 5 ? B?。? 3 ? 有效策略：若能夠讓 A方取走 “ 數(shù)和較大的奇（偶）位置上的所有數(shù) ” ，則 A方勝。只允許從數(shù)列兩頭取數(shù)。Case 39。 readln。 f:array[0..5000] of boolean。 ? 樣例輸入： 2 5 ? 1 7 2 10 9 ? 6 11 ? 62 63 54 66 65 61 57 56 50 53 48 ? 00 ? 樣例輸出： Case 1:2 ? Case 2:4 ? 問題分析： ? 開辟一個足夠大的一維數(shù)組，下標(biāo)表示所有可能的紙牌的分值，用“ *” 標(biāo)記該分值的紙牌是你的，則樣例第一組數(shù)據(jù)如下： ? 一維數(shù)組記錄的分?jǐn)?shù) ? 由于題目是問至少能贏多少輪，也就是說在你現(xiàn)有分值的情況下讓你盡可能的多贏。如果你的牌最大則你就贏了這輪，接著開始下一輪。 s[j]:=s[j+1]。 program ex8_zuidashu。 ? 例題 8：最大數(shù)問題 ? 設(shè)有 n個正整數(shù)（ n≤20），將它們連成一排，組成一個最大的多位整數(shù)。 s:=s1。 n =178543 {刪掉 8} 17543 {刪掉 7} 1543 {刪掉 5} 143 {刪掉 4} 13 字符串類型存貯 n program ex6_shanshu。 ? 貪心法從問題的某一個初始解出發(fā)，采用逐步構(gòu)造最優(yōu)解的方法向給定目標(biāo)推進。 writeln(39。 x0:=0。 ? for n1:=0 to 3 do ? for n2:=0 to 3n1 do ? for n3:=0 to 3n1n2 do ? for n4:=0 to 3n1n2n3 do ? if n1+n2+n3+n4=3 then begin ? sum:=n1*a+n2*b+n3*c+n4*d。 {程序優(yōu)化 } ? 設(shè)四種郵票的面值分別為 a， b， c， d，根據(jù)題意設(shè) ? abcd，因此 a=1，用循環(huán)語句完成搜索。 ? j:=0。 {記錄能量的刻度 } ? f:boolean。 ? 這樣解的范圍就從百萬數(shù)量級變成了十萬的數(shù)量級，大大減少了運行次數(shù)。 ? end. ? 例題 5：一根 29cm長的尺子，只允許在上面刻 7個刻度，要能用它量出1—29cm的各種長度。bb[h]:=1。 ? fillchar(bb,sizeof(bb),0)。 ? begin ? readln(p)。 ? end。 ? begin ? for t:=39。 ? 【 問題分析 】 ： ? 假設(shè)小偷是 “ thisman”，由于 “ thisman”的取值無非是 ‘ A?、 ‘ B?、‘ C?、 ‘ D?，如果我們讓 “ thisman”的取值依次是 ‘ A?～ ‘ D?，分別對 4個關(guān)系式求值，如果為 “ True”的表達(dá)式有 3個那么這時 “ thisman”的值就是問題的解。 ? 要用枚舉法解決問題，首先需要知道解的范圍并能以合適的方法列舉，其次要對問題的約束條件進行精確的描述，這兩個環(huán)節(jié)有一個疏漏就有可能丟失正確解或多出錯誤解。重復(fù)這個過程直到所有同學(xué)手中的糖果數(shù)一致。 {讀入測試數(shù)據(jù)的個數(shù) } ? for i:=1 to num do ? begin ? readln(n)。 ? 輸入：第一行中輸入一個整數(shù)表示有多少組測試數(shù)據(jù)。每個房間中鎖著一個犯人。 ? 一