【正文】 , , , , , , , , 五、編程練習(xí) 1. 歸并排序（ Merging sort）：“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表列合并為一個(gè)新的有序表列。歸并排序就是把一個(gè)具有 n 個(gè)數(shù)據(jù)的序列看作 n個(gè)有序的子序列，不斷兩兩歸并，最后形成一個(gè)有序序列。顯然這是一種分治策略。 歸并排序的關(guān)鍵是歸并。下面介紹一種歸并算法： 設(shè)序列 a(low,high)由兩個(gè)有序子序列組成： a(low,mid)和a(mid,high)。歸并按如下步驟進(jìn)行： （ 1）設(shè)置一個(gè)與序列 a大小相等的數(shù)組 b，用三個(gè)指針 i,j,k,分別指向a(low,mid)， a(mid,high)和 b的首部； （ 2）重復(fù)執(zhí)行下列操作： 如果 a[i]=a[j]，則執(zhí)行 b[k++]=a[i++]；否則執(zhí)行b[k++]=a[j++]。直至有一個(gè)子序列取完。 將未取完的子序列放入 b的尾部； 將 b復(fù)制到 a。 請?jiān)O(shè)計(jì)一個(gè)歸并排序的 C語言程序。 自行車帶人問題 一、問題描述 A、 B兩地相距 S公里。甲、乙、丙三人要利用一輛自行車從 A地趕往 B地。但是該自行車只能帶一人。若人的步行速度為 a公里 /小時(shí)，自行車的速度為 b公里 /小時(shí)（ ba）。問如何利用自行車，才能使三人盡快全部到達(dá) B？ 二、算法分析 1. 基本思路 若要三人盡快到達(dá) B，就要考慮當(dāng)一個(gè)人騎自行車帶一個(gè)人走的同時(shí)，另一個(gè)人也同時(shí)開始步行，并且自行車不是到達(dá) B后再返回去接步行的人，而是在中途返回去接步行的人，讓原來帶的人步行到終點(diǎn)。選擇合適的自行車返回點(diǎn)，使自行車接上原來步行的人后，與中途下車的人同時(shí)到達(dá)。這樣用的時(shí)間最短。 圖 。 A D E C B L S 圖 自行車帶人問題 假定甲被帶到 C點(diǎn)后開始步行，這時(shí)乙步行到了 E點(diǎn)，丙返回的途中在 D遇到乙，然后帶上乙到 B時(shí)，甲也正好步行到 B。問題的關(guān)鍵是求 C的位置。設(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ù)。如果任意給定一個(gè) L，就可以通過判定 t1與 t2是否相等，得知該 L是否正確。 A D E C B L S 圖 自行車帶人問題 2. 用二分法試探確定 C 下面用試探方法來確定 L（即 C的位置）。 首先考慮用二分法，進(jìn)行試探。即先以中點(diǎn)作為設(shè)想的C，后分別計(jì)算 t1與 t2： 如果 t1=t2，該點(diǎn)即為 C； 如果 t1t2，說明甲坐自行車少了（ ba），即 C的實(shí)際位置應(yīng)當(dāng)在該 C點(diǎn)與 B之間，應(yīng)當(dāng)繼續(xù)在 CB之間找下一個(gè) C； 如果 t1t2，說明甲坐自行車多了，即 C的實(shí)際位置應(yīng)當(dāng)在該 C點(diǎn)與 A之間，應(yīng)當(dāng)繼續(xù)在 AC之間找下一個(gè) C。 如此反復(fù)，就會越來越接近真正的 C點(diǎn)。由于，查找的區(qū)間越來越小，當(dāng)上一個(gè) C與新的 C之間的距離小于某個(gè)給定的誤差范圍時(shí)，就可以認(rèn)為找到了 C。 函數(shù)框架 define ERR 20 double putLen(double pf,double pt) { double lenth,ed,dc,t1,t2。 lenth = (pf+pt)/2。 ed =（ lenthlenth/b*a） /(a+b)*a。 dc =（ lenthlenth/b*a） /(a+b)*b。 t1= lenth/b+(Slenth)/a。 t2=lenth/b+ed/a+dc/b+(Slenth)/b。 if(abs(t1t2)ERR) return (lenth)。 if(t1 t2) putLen((pf+pt)/2,pt)。 if(t1 t2) putLen(pf,(pf+pt)/2)。 } 3. 使用優(yōu)選法代替二分法 優(yōu)選法比二分法具有較快的收斂性。用優(yōu)選法代替二分法，就是用 。 三、程序 include include define S 120220 define ERR 200 define a 30 define b 70 double putLen(double pf,double pt) { double lenth,ed,dc,t1,t2。 lenth = (pf+pt)*。 ed =（ lenthlenth/b*a） /(a+b)*a。 dc =（ lenthlenth/b*a） /(a+b)*b。 t1= lenth/b+(Slenth)/a。 t2=lenth/b+ed/a+dc/b+(Slenth)/b。 if(abs(t1t2)ERR) return (lenth)。 if(t1 t2) putLen((pf+pt) *,pt)。 if(t1 t2) putLen(pf,(pf+pt)*)。 } void main() { printf(“\n甲乘自行車行 %，三人到 B的時(shí)間最短“，putLen(0,S)） 。 } 四、運(yùn)行結(jié)果 甲乘自行車行 ，三人到 B的時(shí)間最短。 五、編程練習(xí) 1. 郵局的位置。某小區(qū)有 n戶居民，各家的人口分別為 W W … 、Wn。現(xiàn)要修建一所郵局，若要使所有的人都方便，郵局應(yīng)建在什么位置上？ 提示：設(shè)郵局的位置為 P(xp,yp)；第 i家的位置為 pi，它與郵局之間的距離為 d（ p， pi）。 2. 棋子移動問題。 （ 1）起始條件：有黑白各 n個(gè)棋子（ n≥4）排成一行，開始時(shí)白色棋子全部在左邊，黑色棋子全部在右邊。 （ 2）移動規(guī)則： 每次移動兩個(gè)棋子，顏色不限； 可以移動到左邊的空位，也可以移動到右邊的空位上； 不能調(diào)換兩個(gè)棋子的左右位置； 每次移動必須跳過若干棋子（不可平移）。 （ 3）要求：最后移成黑白相間的一行。 試給出移動程序。 五、編程練習(xí)（續(xù)） 3. 大整數(shù)乘法 問題描述：通常在計(jì)算機(jī)中，整數(shù)的乘法運(yùn)算都是當(dāng)作基本運(yùn)算進(jìn)行的。但是，它的前提是計(jì)算機(jī)硬件要能夠?qū)⒓舆\(yùn)算的整數(shù)以及積直接表示和處理。這當(dāng)然是有限度的。為了處理很大的整數(shù)，一種辦法是用浮點(diǎn)數(shù)來表示，但只能近似地表示它們的大小，并且計(jì)算結(jié)果中的有效數(shù)字也受到限制。另一種辦法就是用軟件的方法來實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算，實(shí)現(xiàn)大整數(shù)的精確表示并在計(jì)算結(jié)果中得到所有位數(shù)上的數(shù)字。 程序設(shè)計(jì)要求：設(shè)計(jì)一個(gè)有效的算法，進(jìn)行兩個(gè) n位大整數(shù)的乘法運(yùn)算。 提示：設(shè) X和 Y分別是 m位和 n位的整數(shù)，為了計(jì)算它們的乘積 X*Y，可以用大小分別為m1和 n1的兩個(gè)整型數(shù)組，存儲這兩個(gè)整數(shù)中的各位。存儲時(shí)，將個(gè)位、十位、百位、千位、萬位 … ，分別存儲在下標(biāo)為 0、 … 的數(shù)組元素中。另外再定義一個(gè)大小為（ m1） *（ n1）的整型數(shù)組，存放積的各位。這樣，就可以按照小學(xué)中學(xué)習(xí)的算式方法來進(jìn)行計(jì)算了。 設(shè)用 x、 y、 z分別存儲整數(shù) X、 Y和積，則可以先用下面的算法： 用 y[0]依次去乘數(shù)組 x的元素，把積中的個(gè)位存入 z[0]，把十位存入 z[1]； 用 y[1]依次去乘數(shù)組 x的元素，積與 z[1]相加，再把個(gè)位存入 z[1]，把十位存入 z[2]； … 用 y[i]依次去乘數(shù)組 x的元素，積與 z[i]相加，再把個(gè)位存入 z[i]，把十位存入 z[i+1]； … 這就說明，當(dāng)規(guī)模較小時(shí)，問題非常容易求解。 這里，考慮另一種思路，就是將 X和 Y用二分求解。具體算法請讀者自己考慮。 五、編程練習(xí)（續(xù)） 4. 循環(huán)賽日程表 問題描述：設(shè)有 n=2k個(gè)運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： 每個(gè)選手必須與其他 n1個(gè)選手各賽一次 每個(gè)選手一天只能參賽一次 循環(huán)賽在 n1天內(nèi)結(jié)束。 程序設(shè)計(jì)要求：請按此要求將比賽日程表設(shè)計(jì)成有 n行和 n1列的一個(gè)表。在表中的第 i行，第 j列處填入第 i個(gè)選手在第 j天所遇到的選手。其中 1≤i≤n， 1≤j≤n1。 提示：按分治策略，可以將所有的選手分為兩半，則 n個(gè)選手的比賽日程表可以通過 n/2個(gè)選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)行劃分，直到只剩下兩個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這兩個(gè)選手進(jìn)行比賽就可以了。 圖 8個(gè)選手的比賽日程表。 首先考慮排選手 1~4前 3天的比賽日程（如左上角一塊）和選手5~8前 3天的比賽日程（如左下角一塊）；然后，將左上角小塊中的所有數(shù)字按其相對位置抄到右下角，又將左下角小塊中的所有數(shù)字按其相對位置抄到右上角，這樣就分別安排好了選手 1~4和選手 5~8在后 4天的比賽日程。 按此思路容易構(gòu)思具有任意多個(gè)選手的比賽日程表。 圖 八個(gè)選手的比賽日程表 回溯算法 經(jīng)常玩象棋的人，最不愿意對手悔棋。所謂悔棋，就是下棋下到感覺情況不妙時(shí)，要退回到前一步的狀態(tài)上重新考慮。有時(shí)，退一步不行，還可能要退回幾步。這種不良的棋風(fēng)，用到解題上卻倒是一種非常有用的方法，稱之為回溯（ back tracking）。它是一種系統(tǒng)的地窮舉問題解答的方法。 使用回溯策略一般有如下的過程： ? 回溯策略的過程： （ 1）為問題定義一個(gè)解空間（ solution space），這個(gè)空間必須至少包含問題的一個(gè)解（可能是最優(yōu)的）； （ 2）以某個(gè)已知解（輸入）為根，把解空間組織成樹結(jié)構(gòu)； （ 3）從樹根出發(fā)，按照深度優(yōu)先方法，對解空間的每個(gè)狀態(tài)進(jìn)行搜尋，直到找到需要的解或最終得到?jīng)]解的結(jié)論為止； （ 4）在搜尋過程中，發(fā)現(xiàn)在所在的支路上無法再向前推進(jìn)時(shí)，即返回到前一個(gè)節(jié)點(diǎn)，找沒有搜尋過的支路進(jìn)行搜尋。 ? 回溯過程可以用遞歸方法實(shí)現(xiàn)，也可以用迭代方法實(shí)現(xiàn)。 迷宮問題 一、問題 在遠(yuǎn)古時(shí)候的克里特島上，有一座有無數(shù)宮殿的迷宮 ——宮殿的通道曲折復(fù)雜，進(jìn)去很難找到出口。統(tǒng)治這個(gè)地方的國王在宮殿深處供養(yǎng)著一頭怪獸 ——彌諾陶羅斯牛。為了養(yǎng)活它，國王要希臘的雅典每 9年進(jìn)貢 7對青年男女來。 當(dāng)?shù)谒拇屋喌窖诺溥M(jìn)貢時(shí)，雅典國王愛琴的兒子狄修斯王子已長成英俊青年，他不忍人民再遭受這種災(zāi)難，決定跟隨不幸的青年男女一起去克里特島殺死彌諾陶羅斯。 在克里特島，英俊的王子以機(jī)智和勇敢贏得了聰明的克里特公主的芳心。在公主的幫助下，狄修斯王子終于殺死怪物，順利地走出宮殿。 試用 C程序找出一條探索迷宮的路徑。 二、克里特方法 1. 基本思路 為了說明該題的解法，首先來看看聰明的克里特公主教給狄修斯王子探索迷宮的方法。公主送給狄修斯王子一把劍和一團(tuán)線，要狄修斯按照下面的規(guī)則邊走邊放線： 凡是走過的路徑，都鋪上一條線； 每到一個(gè)岔口，先走沒有放過線的路走； 凡是鋪有兩條線的路一定是死胡同，不應(yīng)再走。 這個(gè)規(guī)則說明了一種回溯算法：向一個(gè)特定的方向探索前進(jìn)，找不到解，就返回去，找另一條可能的路徑往下搜索；凡是已搜索過的狀態(tài)（位置），不再搜索。這種算法稱為回溯（ backtracking）?；厮菔侨藗兦蠼鈴?fù)雜問題時(shí)常用的一種方法。 2. 迷宮的表示 ——數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 迷宮的表示方法很多，最直接的方法是采用矩陣模擬法，即把迷宮用一個(gè)二維數(shù)組來模擬。在 圖 ，把 (a)所示的迷宮模擬為圖（ b）所示的二維數(shù)組，用“ 0”表示可通行部分，用“ 2”表示不可通行部分。后面的解法都是基于該矩陣的。除此之外，還有狀態(tài)圖、鄰接矩陣等表示法，它們都要使用二維數(shù)組，這里暫不介紹。 入口 出口 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存儲迷宮矩陣，則迷宮問題的求解，可以歸結(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)過程。如 圖 。 i1,j i,j+1