1、1、算24點(diǎn) 【問題描述】 幾十年前全世界就流行一種數(shù)字游戲，至今仍有人樂此不疲在中國我們把這種游戲稱為“算24點(diǎn)”。您作為游戲者將得到4個(gè)19之間的自然數(shù)作為操作數(shù)，而您的任務(wù)是對(duì)這4個(gè)操作數(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)是不合法的）。下面我們給出一個(gè)游戲的具體例子： 若給出的4個(gè)操作數(shù)是：1、2、3、7，則一種可能的解答是1+2+3*7=24。 【輸入】 只有一行，四個(gè)1到9之間的自然數(shù)。 【輸出】 如果有

2、解的話，只要輸出一個(gè)解，輸出的是三行數(shù)據(jù)，分別表示運(yùn)算的步驟。其中第一行是輸入的兩個(gè)數(shù)和一個(gè)運(yùn)算符和運(yùn)算后的結(jié)果，第二行是第一行的結(jié)果和一個(gè)輸入的數(shù)據(jù)、運(yùn)算符、運(yùn)算后的結(jié)果；第三行是第二行的結(jié)果和輸入的一個(gè)數(shù)、運(yùn)算符和“=24”。如果兩個(gè)操作數(shù)有大小的話則先輸出大的。 如果沒有解則輸出“No answer!”就一個(gè)數(shù)據(jù)，是精確到0.1元的最小的加油和吃飯費(fèi)用 【樣例】 point24.inpoint24.out 1 2 3 72+1=3 7*3=21 21+3=24,【算法分析】 計(jì)算24點(diǎn)主要應(yīng)用四種運(yùn)算開始狀態(tài)有四個(gè)操作數(shù)，一個(gè)運(yùn)算符對(duì)應(yīng)兩個(gè)操作數(shù)，所以一開始選擇兩個(gè)操作數(shù)分別對(duì)四個(gè)操作符

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

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

5、汽車每升油能行駛的公里數(shù)；第三個(gè)實(shí)數(shù)是汽車在出發(fā)地加滿油箱時(shí)的費(fèi)用(單位元)；一個(gè)整數(shù)是1到50間的數(shù)，表示從出發(fā)地到目的地線路上加油站的數(shù)目。 接下來n行都是兩個(gè)實(shí)數(shù)，第一個(gè)數(shù)表示從出發(fā)地到某一個(gè)加油站的距離(單位：km)；第二個(gè)實(shí)數(shù)表示該加油站汽油的價(jià)格(單位：元)。 數(shù)據(jù)項(xiàng)中的每個(gè)數(shù)據(jù)都是正確的，不需判錯(cuò)。一條線路上的加油站根據(jù)其到出發(fā)地的距離遞增排列并且都不會(huì)大于從出發(fā)地到目的地的距離。 【輸出】 就一個(gè)數(shù)據(jù)，是精確到0.1元的最小的加油和吃飯費(fèi)用,【樣例】 our.out 600379.6 40 8.5 128 3 200 3.52 350 3.45 500 365 【算法分析】 駕車者從出發(fā)地出發(fā)后對(duì)于每個(gè)加油站都可能有兩種操作，一是進(jìn)去加油買食品，二是不進(jìn)去繼續(xù)前行(如果當(dāng)前汽車的余油可以的話)，這樣有n個(gè)加油站最多可能有2n種選擇。由于加油站數(shù)目不太多，可以采用回溯的算法來解決問題。從第一個(gè)加油站開始，依次選擇所要停下的下一個(gè)加油站，從而找出總費(fèi)用最少的方案，加油站數(shù)目最多為50，這樣回溯不會(huì)進(jìn)行得很深。在選擇下一個(gè)要停下的加油站時(shí)比較麻煩，不能完全一個(gè)一個(gè)地試過去，這樣時(shí)間太長(zhǎng)。可以用這樣