【正文】 假定甲被帶到 C點(diǎn)后開始步行，這時(shí)乙步行到了 E點(diǎn)，丙返回的途中在 D遇到乙，然后帶上乙到 B時(shí)，甲也正好步行到 B。設(shè) AC=L，那么 : 甲從 A到 B的時(shí)間為： t1=AC/b + CB/a = L/b+(SL)/a 乙從 A到 B的時(shí)間為： t2=AE/a+ED/a+DC/b+CB/b 并且 , 并且， 由于甲到 C與乙到 E用的時(shí)間相等，所以： AE/a=L/b； 由于當(dāng)自行車返回到 D時(shí)，乙步行到 D，所以 EC/(a+b)=ED/a=DC/b，即 : ED =（ LL/b*a） /(a+b)*a /* ED=EC/(a+b)*a=(ACEC)/(a+b)*a */ DC =（ LL/b*a） /(a+b)*b /* DC=EC/(a+b)*b=(ACEC)/(a+b)*b */ 這樣， t1和 t2都描述成了關(guān)于 L的函數(shù)。 A D E C B L S 圖 自行車帶人問(wèn)題 2. 用二分法試探確定 C 下面用試探方法來(lái)確定 L（即 C的位置）。即先以中點(diǎn)作為設(shè)想的C，后分別計(jì)算 t1與 t2： 如果 t1t2，說(shuō)明甲坐自行車少了（ ba），即 C的實(shí)際位置應(yīng)當(dāng)在該 C點(diǎn)與 B之間，應(yīng)當(dāng)繼續(xù)在 CB之間找下一個(gè) C； 如此反復(fù)，就會(huì)越來(lái)越接近真正的 C點(diǎn)。 函數(shù)框架 define ERR 20 double putLen(double pf,double pt) { double lenth,ed,dc,t1,t2。 ed =（ lenthlenth/b*a） /(a+b)*a。 t1= lenth/b+(Slenth)/a。 if(abs(t1t2)ERR) return (lenth)。 if(t1 t2) putLen(pf,(pf+pt)/2)。用優(yōu)選法代替二分法，就是用 。 lenth = (pf+pt)*。 dc =（ lenthlenth/b*a） /(a+b)*b。 t2=lenth/b+ed/a+dc/b+(Slenth)/b。 if(t1 t2) putLen((pf+pt) *,pt)。 } void main() { printf(“\n甲乘自行車行 %，三人到 B的時(shí)間最短“，putLen(0,S)） 。 五、編程練習(xí) 1. 郵局的位置。現(xiàn)要修建一所郵局，若要使所有的人都方便，郵局應(yīng)建在什么位置上？ 提示：設(shè)郵局的位置為 P(xp,yp)；第 i家的位置為 pi，它與郵局之間的距離為 d（ p， pi）。 （ 1）起始條件：有黑白各 n個(gè)棋子（ n≥4）排成一行，開始時(shí)白色棋子全部在左邊，黑色棋子全部在右邊。 每次移動(dòng)兩個(gè)棋子，顏色不限； 不能調(diào)換兩個(gè)棋子的左右位置； （ 3）要求：最后移成黑白相間的一行。 五、編程練習(xí)（續(xù)） 3. 大整數(shù)乘法 問(wèn)題描述：通常在計(jì)算機(jī)中，整數(shù)的乘法運(yùn)算都是當(dāng)作基本運(yùn)算進(jìn)行的。這當(dāng)然是有限度的。另一種辦法就是用軟件的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算，實(shí)現(xiàn)大整數(shù)的精確表示并在計(jì)算結(jié)果中得到所有位數(shù)上的數(shù)字。 提示：設(shè) X和 Y分別是 m位和 n位的整數(shù)，為了計(jì)算它們的乘積 X*Y，可以用大小分別為m1和 n1的兩個(gè)整型數(shù)組，存儲(chǔ)這兩個(gè)整數(shù)中的各位。另外再定義一個(gè)大小為（ m1） *（ n1）的整型數(shù)組，存放積的各位。 設(shè)用 x、 y、 z分別存儲(chǔ)整數(shù) X、 Y和積，則可以先用下面的算法： 用 y[1]依次去乘數(shù)組 x的元素，積與 z[1]相加，再把個(gè)位存入 z[1]，把十位存入 z[2]； 用 y[i]依次去乘數(shù)組 x的元素，積與 z[i]相加，再把個(gè)位存入 z[i]，把十位存入 z[i+1]； 這里，考慮另一種思路，就是將 X和 Y用二分求解。 五、編程練習(xí)（續(xù)） 4. 循環(huán)賽日程表 問(wèn)題描述：設(shè)有 n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽。 每個(gè)選手必須與其他 n1個(gè)選手各賽一次 循環(huán)賽在 n1天內(nèi)結(jié)束。在表中的第 i行，第 j列處填入第 i個(gè)選手在第 j天所遇到的選手。 提示：按分治策略，可以將所有的選手分為兩半，則 n個(gè)選手的比賽日程表可以通過(guò) n/2個(gè)選手的比賽日程表來(lái)決定。這時(shí)只要讓這兩個(gè)選手進(jìn)行比賽就可以了。 首先考慮排選手 1~4前 3天的比賽日程（如左上角一塊）和選手5~8前 3天的比賽日程（如左下角一塊）；然后，將左上角小塊中的所有數(shù)字按其相對(duì)位置抄到右下角，又將左下角小塊中的所有數(shù)字按其相對(duì)位置抄到右上角，這樣就分別安排好了選手 1~4和選手 5~8在后 4天的比賽日程。 圖 八個(gè)選手的比賽日程表 回溯算法 經(jīng)常玩象棋的人，最不愿意對(duì)手悔棋。有時(shí)，退一步不行，還可能要退回幾步。它是一種系統(tǒng)的地窮舉問(wèn)題解答的方法。 ? 回溯過(guò)程可以用遞歸方法實(shí)現(xiàn)，也可以用迭代方法實(shí)現(xiàn)。統(tǒng)治這個(gè)地方的國(guó)王在宮殿深處供養(yǎng)著一頭怪獸 ——彌諾陶羅斯牛。 當(dāng)?shù)谒拇屋喌窖诺溥M(jìn)貢時(shí)，雅典國(guó)王愛(ài)琴的兒子狄修斯王子已長(zhǎng)成英俊青年，他不忍人民再遭受這種災(zāi)難，決定跟隨不幸的青年男女一起去克里特島殺死彌諾陶羅斯。在公主的幫助下，狄修斯王子終于殺死怪物，順利地走出宮殿。 二、克里特方法 1. 基本思路 為了說(shuō)明該題的解法，首先來(lái)看看聰明的克里特公主教給狄修斯王子探索迷宮的方法。 凡是走過(guò)的路徑，都鋪上一條線； 凡是鋪有兩條線的路一定是死胡同，不應(yīng)再走。這種算法稱為回溯（ backtracking）。 2. 迷宮的表示 ——數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 迷宮的表示方法很多，最直接的方法是采用矩陣模擬法，即把迷宮用一個(gè)二維數(shù)組來(lái)模擬。后面的解法都是基于該矩陣的。 入口 出口 2,2,2,2,2,2,2 2,0,0,0,0,0,2 2,0,2,0,2,0,2 2,0,0,2,0,2,2 2,2,0,2,0,2,2 2,0,0,0,0,0,2 2,2,2,2,2,2,2 (a)一個(gè)迷宮 （ b）模擬矩陣 圖 迷宮的模擬表示 3. 算法 用數(shù)組 maze存儲(chǔ)迷宮矩陣，則迷宮問(wèn)題的求解，可以歸結(jié)為在任一個(gè)節(jié)點(diǎn) maze[i][j]上，向四個(gè)候選節(jié)點(diǎn)：maze[i][j+1]、 maze[i+1][j]、 maze[i][j1]、 maze[i1][j]的搜索前進(jìn)過(guò)程。 i1,j i,j+1 i,j1 i+1,j i,j 圖 一個(gè)節(jié)點(diǎn)（ i， j）上的搜索 這樣將會(huì)出現(xiàn)如下三種情形： （ 1）若 4個(gè)候選節(jié)點(diǎn)中有 3個(gè)節(jié)點(diǎn)為不可到達(dá)節(jié)點(diǎn)，則稱該節(jié)點(diǎn)為“死點(diǎn)”（死胡同盡頭）。 判斷死點(diǎn)并進(jìn)行處理的算法為： if(maze[i1][j]==2 amp。 maze[i][j+1]==2 amp。 maze[i+1][j]==2) { maze[i][j]=2。} else if(maze[i][j+1]==2 amp。 maze[i+1][j]==2 amp。 maze[i][j1]==2) { maze[i][j]=2。 } else if(maze[i+1][j]==2 amp。 maze[i][j1]==2 amp。 maze[i1][j]==2) { maze[i][j]=2。 } else if(maze[i][j1]==2 amp。 maze[i1][j]==2 amp。 maze[i][j+1]==2) { maze[i][j]=2。 } （ 2）若該點(diǎn)不為死點(diǎn)，下一步將向一個(gè)候選節(jié)點(diǎn)搜索，稱其為已通過(guò)點(diǎn)，記以標(biāo)志：令 maze[i][j]=1，相當(dāng)于狄修斯放了一條線。 maze[i][j]=1。 maze[i][j]=1。 maze[i][j]=1。 maze[i][j]=1。 i。 j++。 i++。 j。 （ 3）探索結(jié)束的條件為： i=Ei amp。 j=Ej，即繼續(xù)探索的條件為： iEi || jEj。 int Si=1,Sj=1,Ei=5,Ej=5。 int count=0。amp。amp。 j。amp。amp。 i。amp。amp。 j++。amp。amp。 i++。 4. 程序（續(xù)） /***** 按順時(shí)針順序先走沒(méi)有走過(guò)的點(diǎn) *****/ if (maze[i1][j]==0) { i。} else if(maze[i][j+1]==0) { j++。} else if(maze[i+1][j]==0) { i++。} else if(maze[i][j1]==0) { j。} /***** 按順時(shí)針順序走走過(guò)的點(diǎn) *****/ else if(maze[i1][j]==1) { maze[i][j]=2。} else if(maze[i][j+1]==1) { maze[i][j]=2。} else if(maze[i+1][j]==1) { maze[i][j]=2。} else if(maze[i][j1]==1) { maze[i][j]=2。} count++。i=6。j=6。 printf(\n)。 /* 打印搜索步數(shù) */ } 5. 執(zhí)行結(jié)果 2,2,2,2,2,2,2 2,1,2,2,2,2,2 2,1,2,2,2,2,2 2,1,1,2,2,2,2 2,2,1,2,2,2,2 2,0,1,1,1,1,2 2,2,2,2,2,2,2 count=19 結(jié)果矩陣中的“ 1”為搜索后，找到的穿過(guò)迷宮的路線；“ 0”為未搜索過(guò)的節(jié)點(diǎn)。其基本思路如 圖 ，把對(duì)迷宮的搜索，看成一棵搜索樹的生成過(guò)程： （ 1）首先將根節(jié)點(diǎn)（入口處）壓入堆棧； （ 2） 按照下面的規(guī)則考察棧頂節(jié)點(diǎn)（圖中灰色節(jié)點(diǎn)）的可擴(kuò)展性（即前面還有路可走），直到找到一個(gè)解或得出無(wú)解（堆?？?——即返回到入口）的結(jié)論為止： 不可擴(kuò)展，則將棧頂節(jié)點(diǎn)彈出（圖中黑色的節(jié)點(diǎn)），繼續(xù)考察下一個(gè)節(jié)點(diǎn)。 (f) 節(jié)點(diǎn) (1,5)，(1,4)都不可再擴(kuò)展，被依次彈出 ┇ (2,1) SP (1,1) (1,2) (1,3) (2,3) (2,3) (1,1) (1,3) (5,3) (e) 節(jié)點(diǎn) ()不可擴(kuò)展，被彈出 (a) 在棧中壓入根節(jié)點(diǎn) (b) 擴(kuò)展節(jié)點(diǎn)(1,1)， 壓入兩個(gè)節(jié)點(diǎn) (c) 擴(kuò)展節(jié)點(diǎn)((2,1)， 壓入一個(gè)節(jié)點(diǎn) (d) 擴(kuò)展節(jié)點(diǎn)(5,2)，壓入節(jié)點(diǎn) (5,3)(5,1) ┇ (1,2) SP (1,1) (2,1) (1,1) ┇ SP ┇ (1,2) SP (1,1) (2,1) (3,1) (1,2) (5,3) SP (1,1) (2,1) (3,1) (3,2) (4,2) (5,3) ┇ (1,2) SP (1,1) (2,1) (5,1) (3,1) (3,2) (4,2) (5,2) … (1,1) (1,1) (2,1) (1,2) (1,1) (2,1) (3,1) (1,1) (4,2) (5,2) … (1,1)