【正文】 立起對(duì)應(yīng)關(guān)系，將所有情況列舉一遍，再找出其中步驟最少的輸出。procedure pages(k:integer)。begin {main} readln(n,r)?！据斎搿?村莊數(shù)n和各村之間的路程(均是整數(shù))。自己駕車旅游時(shí)總會(huì)碰到加油和吃飯的問(wèn)題，在出發(fā)之前，駕車人總要想方設(shè)法得到從一個(gè)城市到另一個(gè)城市路線上的加油站的列表，列表中包括了所有加油站的位置及其每升的油價(jià)()。)；第二個(gè)實(shí)數(shù)是汽車每升油能行駛的公里數(shù)；第三個(gè)實(shí)數(shù)是汽車在出發(fā)地加滿油箱時(shí)的費(fèi)用(單位元)；一個(gè)整數(shù)是1到50間的數(shù)，表示從出發(fā)地到目的地線路上加油站的數(shù)目?？梢杂眠@樣的方法：先找出第一個(gè)要停下的加油站，判斷其后面的加油站是否可以到達(dá)，如果不可到達(dá)就必須在這里停下來(lái)加油；否則就找出可以到達(dá)但如果只用一半汽油則無(wú)法到達(dá)的所有加油站，依次進(jìn)行?？??！据斎搿? 文件第一行是兩個(gè)數(shù)字n(0n50，表示路燈的總數(shù))和c(1＝c=n老張所處位置的路燈號(hào))； 接下來(lái)n行，每行兩個(gè)數(shù)據(jù)，表示第1盞到第n盞路燈的位置和功率。 對(duì)于每一個(gè)所處位置，都可以選擇向左或向右，不管是向左還是向右，相應(yīng)耗電的變化都跟上面所述一樣。 如果n再大一些，如到300以上，上述方法也有它的局限性，此時(shí)最好從動(dòng)態(tài)規(guī)劃法或貪心法的角度去思考。 比較向左與向右的情況，找出比較好的一種確定方法。 現(xiàn)在已知老張走的速度為1m/s，每個(gè)路燈的位置（是一個(gè)整數(shù)，即距路線起點(diǎn)的距離，單位：m）、功率（W），老張關(guān)燈所用的時(shí)間很短而可以忽略不計(jì)。從第一個(gè)加油站開始，依次選擇所要停下的下一個(gè)加油站，從而找出總費(fèi)用最少的方案，加油站數(shù)目最多為50，這樣回溯不會(huì)進(jìn)行得很深?！据斎搿? 第一行是一個(gè)實(shí)數(shù)，是從出發(fā)地到目的地的距離(單位：km)。如果step還小于n，那么將還沒(méi)有到過(guò)的村莊一個(gè)一個(gè)地試過(guò)去，再調(diào)用下一步road(step+1，新到的村莊號(hào))。為了提高效率，他從商店出發(fā)到每個(gè)村莊一次，然后返回商店所在的村，假設(shè)商店所在的村莊為1，他不知道選擇什么樣的路線才能使所走的路程最短。 end。var a:array[0..max]of integer。解決問(wèn)題可以從D序列出發(fā)反過(guò)來(lái)看，當(dāng)前要到D的字符在哪里，如果在A，再看它前面有沒(méi)有字符，如果有，先讓它們進(jìn)棧(B或C)，否則直接到D；如果在B，看是否是棧頂元素，如果是，直接到D，否則將上面的字符進(jìn)C；如果在C，看是否是棧頂元素，如果是，直接到D，否則無(wú)法進(jìn)行操作，因?yàn)橹荒芟蛴也荒芟蜃?，這時(shí)要回溯。從起點(diǎn)開始往下的一層層的結(jié)點(diǎn)，看起來(lái)如同樹枝一樣，對(duì)于其中的“枯枝”——明顯無(wú)用的節(jié)點(diǎn)可以先行“剪掉”，從而提高搜索速度。 如果沒(méi)有一條可行的路則輸出1。我們可以從最后一步來(lái)思考： 最后一次關(guān)的可能是第一個(gè)燈也可能是最后一個(gè)燈，哪種情況所費(fèi)的功小就選哪種； 最后一次關(guān)的是第一個(gè)燈的話，說(shuō)明最后的方向是從最后到最前(右邊到左邊)，最后倒數(shù)第二次的方向?yàn)閺淖蟮接遥瘘c(diǎn)可能是原始起點(diǎn)(此時(shí)是第一趟)，也可能是原始起點(diǎn)左邊的點(diǎn)(此時(shí)至少是第二趟)，一個(gè)個(gè)地試過(guò)去，先設(shè)拐一次彎，有可能拐的點(diǎn)都試過(guò)去，再試有兩次拐彎換方向的情況，當(dāng)再多的拐彎超過(guò)已有的解時(shí)就不要再向下試了。 向左走時(shí)，相應(yīng)地可以減小左邊應(yīng)費(fèi)的功，而增加右邊應(yīng)費(fèi)的功，如果到一個(gè)點(diǎn)(一盞路燈處)所要時(shí)間為t，減少的功為(p_left+w[i])*t，增加的功為p_right*2t。他每天都是在天亮?xí)r首先關(guān)掉自己所處位置的路燈，然后可以向左也可以向右去關(guān)燈?！据敵觥?就一個(gè)數(shù)據(jù)，【樣例】 600 40 128 3 200 350 500 365【算法分析】 駕車者從出發(fā)地出發(fā)后對(duì)于每個(gè)加油站都可能有兩種操作，一是進(jìn)去加油買食品，二是不進(jìn)去繼續(xù)前行(如果當(dāng)前汽車的余油可以的話)，這樣有n個(gè)加油站最多可能有2n種選擇。 （6）駕車者都知道自己的汽車每升汽油能夠行駛的里程數(shù)。 用一個(gè)過(guò)程road(step，line：byte)來(lái)描述走的狀況，其中step是當(dāng)前已到村莊數(shù)、line是當(dāng)前所在的村莊。當(dāng)全部選取完時(shí)，i回到了0，a[0]的值增加1后變?yōu)?，這是整個(gè)選取過(guò)程結(jié)束的條件。 writeln?！据敵觥? 所有的組合，每一個(gè)組合占一行且其中的元素按由小到大的順序排列，每個(gè)元素占三個(gè)字符的位置，所有的組合也按字典順序?！据敵觥?可以調(diào)度則輸出最短的調(diào)度序列，不可以調(diào)度時(shí)則輸出‘NO’。這類問(wèn)題也可以歸為搜索的問(wèn)題，如果m和n的值相對(duì)比較大，則解可能很多，若題目只要找到一條路就結(jié)束程序時(shí)，在程序的輸出部分后面加上一個(gè)halt就行了?！据斎搿? 第一行是兩個(gè)數(shù)m，n(1m，n15)，接下來(lái)是m行n列由1和0組成的數(shù)據(jù)，最后兩行是起始點(diǎn)和結(jié)束點(diǎn)。如果這些函數(shù)依賴中不包含冗余依賴，則輸出“No redundant FDs”信息。在AB、BC、CA、AC、CB和BA中，所有的依賴都是冗余的。 冗余依賴 源程序名 redund.???（pas, c, cpp）可執(zhí)行文件名 輸入文件名 輸出文件名 【問(wèn)題描述】 在設(shè)計(jì)關(guān)系數(shù)據(jù)庫(kù)的表格時(shí)，術(shù)語(yǔ)“函數(shù)依賴”（FD）被用來(lái)表示不同域之間的關(guān)系。下面我們給出一個(gè)游戲的具體例子： 若給出的4個(gè)操作數(shù)是：7，則一種可能的解答是1+2+3*7=24。【輸入】 一個(gè)整數(shù)n（1=n=15）【輸出】 一個(gè)整數(shù)，即可能輸出序列的總數(shù)目?！緲永? 6 6 3 3 6【算法分析】 從起點(diǎn)開始往下走(只有兩個(gè)方向可以走)，如果某個(gè)方向可以走再繼續(xù)下一步，直到終點(diǎn)，此時(shí)計(jì)數(shù)。第一章 回溯法 馬攔過(guò)河卒源程序名 knight.???（pas, c, cpp）可執(zhí)行文件名 輸入文件名 輸出文件名 【問(wèn)題描述】棋盤上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。【輸出】 一個(gè)數(shù)據(jù)，表示所有的路徑條數(shù)。請(qǐng)你編程求出對(duì)于給定的n，計(jì)算并輸出由操作數(shù)序列1，2，…，n，經(jīng)過(guò)一系列操作可能得到的輸出序列總數(shù)。注意：所有的中間結(jié)果須是整數(shù)，所以一些除法運(yùn)算是不允許的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。如果所有的情況都找過(guò)后仍然沒(méi)有，則輸出無(wú)解的信息。例如，如果組里包括依賴AB、BC和AC，那么第三個(gè)依賴是冗余的，因?yàn)橛駽可以用前兩個(gè)依賴得到（域A確定了域B的值，同樣域B確定了域C的值)。 如果許多函數(shù)依賴的序列都能被用來(lái)說(shuō)明一個(gè)依賴是冗余的，則輸出其中最短的證明序列。如果一條路都不可行，則輸出相應(yīng)信息(用l表示無(wú)路)。 這個(gè)查找過(guò)程用search來(lái)描述如下：procedure search(x, y, b, p)；{x，y表示某一個(gè)點(diǎn)，b是已經(jīng)過(guò)的點(diǎn)的情況，p是已走過(guò)的路} begin for i:＝1 to 4 do{分別對(duì)4個(gè)點(diǎn)進(jìn)行試探} begin 先記住當(dāng)前點(diǎn)的位置，已走過(guò)的情況和走過(guò)的路； 如果第i個(gè)點(diǎn)(xl，y1)可以走，則走過(guò)去； 如果已達(dá)終點(diǎn)，則輸出所走的路徑并置有路可走的信息， 否則繼續(xù)從新的點(diǎn)往下查找search(xl，y1，b1，p1)； end； end；【思考與提高】 該程序通過(guò)引進(jìn)新的變量和數(shù)組來(lái)繼續(xù)新的查找，如果不引進(jìn)新的變量和數(shù)組，那么每一次返回時(shí)要將原來(lái)的值還原才行，如果那樣，程序應(yīng)如何修改?其實(shí)那樣更加符合回溯的思想——換條路再試?！据斎搿?一個(gè)數(shù)n(1n27)及由n個(gè)小寫字母組成的字符串。 例如n＝5，r＝3，所有組合為： l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5【輸入】 一行兩個(gè)自然數(shù)n、r(1n21，1＝r＝n)。 {選取一個(gè)元素} if k=r then begin for j:=1 to r do write(a[j]:3)。如果選取第i個(gè)元素時(shí)選擇了a[i]，根據(jù)輸出條件應(yīng)有a[i]i＝nr，如果不滿足這個(gè)條件說(shuō)明當(dāng)前第i個(gè)元素已再無(wú)數(shù)可取，要進(jìn)行回溯，將其值減1，退到上一步將上一步原來(lái)的值再增加1，重復(fù)上述過(guò)程。當(dāng)村莊數(shù)n比較大時(shí)這種方法就不太適用了。 （5）(四舍五入)。一條線路上的加油站根據(jù)其到出發(fā)地的距離遞增排列并且都不會(huì)大