pascal回朔法講解實(shí)用教案

1、1、算24點(diǎn) 【問題描述】 幾十年前全世界就流行一種數(shù)字游戲，至今仍有人樂此不疲在中國我們把這種游戲稱為“算24點(diǎn)”。您作為游戲者將得到4個19之間的自然數(shù)作為操作數(shù)，而您的任務(wù)是對這4個操作數(shù)進(jìn)行適當(dāng)?shù)乃阈g(shù)運(yùn)算，要求運(yùn)算結(jié)果等于24。 您可以使用的運(yùn)算只有：+，-，*，/，您還可以使用（）來改變運(yùn)算順序。注意：所有的中間結(jié)果須是整數(shù)，所以一些除法運(yùn)算是不允許的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。下面我們給出一個游戲的具體例子： 若給出的4個操作數(shù)是：1、2、3、7，則一種可能的解答是1+2+3*7=24。【輸入】 只有一行，四個1到9之間的自然數(shù)?！据敵觥?如果有解的

2、話，只要輸出一個解，輸出的是三行數(shù)據(jù)，分別表示運(yùn)算的步驟。其中第一行是輸入的兩個數(shù)和一個運(yùn)算符和運(yùn)算后的結(jié)果，第二行是第一行的結(jié)果和一個輸入的數(shù)據(jù)、運(yùn)算符、運(yùn)算后的結(jié)果；第三行是第二行的結(jié)果和輸入的一個數(shù)、運(yùn)算符和“=24”。如果兩個操作數(shù)有大小的話則先輸出大的。 如果沒有解則輸出“No answer!”就一個數(shù)據(jù)，是精確(jngqu)到元的最小的加油和吃飯費(fèi)用【樣例】1 2 3 72+1=3 7*3=2121+3=24第1頁/共5頁第一頁，共6頁?！舅惴ǚ治觥坑嬎?4點(diǎn)主要應(yīng)用四種運(yùn)算開始狀態(tài)有四個操作數(shù)，一個運(yùn)算符對應(yīng)兩個操作數(shù)，所以一開始選擇兩個操作數(shù)分別對四個操作符進(jìn)行循環(huán)(xnhun

3、)檢測，每一次運(yùn)算后產(chǎn)生了新的數(shù)，兩個數(shù)運(yùn)算變成一個數(shù)，整體是少了一個操作數(shù)，所以四個數(shù)最終是三次運(yùn)算。由于操作的層數(shù)比較少(只有三層)，所以可以用回溯的算法來進(jìn)行檢測，當(dāng)找到一個解時便結(jié)束查找。如果所有的情況都找過后仍然沒有，則輸出無解的信息。第2頁/共5頁第二頁，共6頁。2、駕車旅游 【問題描述】 如今許多普通百姓家有了私家車，一些人喜愛自己駕車從一個城市到另一個城市旅游。自己駕車旅游時總會碰到加油和吃飯的問題，在出發(fā)之前，駕車人總要想方設(shè)法得到從一個城市到另一個城市路線上的加油站的列表，列表中包括了所有加油站的位置及其每升的油價(如元/L)。駕車者一般都有以下的習(xí)慣： （1）除非汽車無法

4、用油箱里的汽油達(dá)到下一個加油站或目的地，在油箱里還有不少于最大容量一半的汽油時，駕駛員從不在加油站停下來； （2）在第一個停下的加油站總是將油箱加滿； （3）在加油站加油的同時，買快餐等吃的東西花去20元。 （4）從起始城市出發(fā)時油箱總是滿的。 （5）加油站付錢總是精確到元(四舍五入)。 （6）駕車者都知道自己的汽車每升汽油能夠行駛的里程數(shù)。 現(xiàn)在要你幫忙做的就是編寫一個程序，計算出駕車從一個城市到另一個城市的旅游在加油和吃飯方面最少的費(fèi)用。【輸入】 第一行是一個實(shí)數(shù)，是從出發(fā)地到目的地的距離(單位：km)。 第二行是三個實(shí)數(shù)和一個整數(shù)，其中第一個實(shí)數(shù)是汽車油箱的最大容量(單位：I。)；第二個

5、實(shí)數(shù)是汽車每升油能行駛的公里數(shù)；第三個實(shí)數(shù)是汽車在出發(fā)地加滿油箱時的費(fèi)用(單位元)；一個整數(shù)是1到50間的數(shù)，表示從出發(fā)地到目的地線路上加油站的數(shù)目。 接下來n行都是兩個實(shí)數(shù)，第一個數(shù)表示從出發(fā)地到某一個加油站的距離(單位：km)；第二個實(shí)數(shù)表示該加油站汽油的價格(單位：元)。 數(shù)據(jù)項中的每個數(shù)據(jù)都是正確的，不需判錯。一條線路上的加油站根據(jù)(gnj)其到出發(fā)地的距離遞增排列并且都不會大于從出發(fā)地到目的地的距離?！据敵觥烤鸵粋€數(shù)據(jù)，是精確到元的最小的加油和吃飯費(fèi)用第3頁/共5頁第三頁，共6頁?！緲永?0 8.5 128 3500 365【算法分析】 駕車者從出發(fā)地出發(fā)后對于每個加油站都可能有兩

6、種操作，一是進(jìn)去加油買食品，二是不進(jìn)去繼續(xù)前行(如果當(dāng)前汽車的余油可以的話)，這樣有n個加油站最多可能有2n種選擇(xunz)。由于加油站數(shù)目不太多，可以采用回溯的算法來解決問題。從第一個加油站開始，依次選擇(xunz)所要停下的下一個加油站，從而找出總費(fèi)用最少的方案，加油站數(shù)目最多為50，這樣回溯不會進(jìn)行得很深。在選擇(xunz)下一個要停下的加油站時比較麻煩，不能完全一個一個地試過去，這樣時間太長。可以用這樣的方法：先找出第一個要停下的加油站，判斷其后面的加油站是否可以到達(dá)，如果不可到達(dá)就必須在這里停下來加油；否則就找出可以到達(dá)但如果只用一半汽油則無法到達(dá)的所有加油站，依次進(jìn)行停靠。第4頁/共5頁第四頁，共6頁。感謝您的觀看(gunkn)！第5頁/共5頁第五頁，共6頁。NoImage內(nèi)容(nirng)總結(jié)1、算24點(diǎn)。” 就一個數(shù)據(jù)，是精確到元的最小的加油(ji yu)和吃飯費(fèi)用。如果所有的情況都找過后仍然沒有，則輸出無解的信息。（3）在加油(ji yu)站加油(ji yu)的同時，買快餐等吃的東西花去20元。（6）駕車者都知道自