pascal回朔法講解實用教案

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

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

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

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

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

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