【文章內(nèi)容簡(jiǎn)介】 ，CC；逆時(shí)針?lè)沁f歸算法產(chǎn)生的移動(dòng)序列為：C，O，C，O，…，C。① 當(dāng)n為奇數(shù)時(shí)，順時(shí)針遞歸算法Hanoi（n，A，B，C）產(chǎn)生的移動(dòng)序列為：Hanoi（n－1，A，C，B）產(chǎn)生的移動(dòng)序列，O，Hanoi（n－1，C，B，A）產(chǎn)生的移動(dòng)序列。Hanoi（n－1，A，C，B）和Hanoi（n－1，C，B，A）均為偶數(shù)圓盤(pán)逆時(shí)針移動(dòng)問(wèn)題。由數(shù)學(xué)歸納法知，產(chǎn)生的移動(dòng)序列均為：C，O，C，O，…，C。因此，Hanoi（n，A，B，C）產(chǎn)生的移動(dòng)序列為：C，O，C，O，…，C。② 當(dāng)n為偶數(shù)時(shí)，順時(shí)針遞歸算法Hanoi（n，A，B，C）產(chǎn)生的移動(dòng)序列為：Hanoi（n－1，A，C，B）產(chǎn)生的移動(dòng)序列，O，Hanoi（n－1，C，B，A）產(chǎn)生的移動(dòng)序列。Hanoi（n－1，A，C，B）和Hanoi（n－1，C，B，A）均為奇數(shù)圓盤(pán)逆時(shí)針移動(dòng)問(wèn)題。由數(shù)學(xué)歸納法知，產(chǎn)生的移動(dòng)序列均為：CC，O，CC，O，…，CC。因此，Hanoi（n，A，B，C）產(chǎn)生的移動(dòng)－序列為：CC，O，CC，O，…，CC。當(dāng)n為奇數(shù)和偶數(shù)時(shí)的逆時(shí)針遞歸算法也類(lèi)似。由數(shù)學(xué)歸納法即知，遞歸算法和非遞歸算法產(chǎn)生相同的移動(dòng)序列。 （3）雙色漢諾塔問(wèn)題：設(shè)A、B、C是三根金針。開(kāi)始時(shí)，在金針A上有n只紙盤(pán)，這些紙盤(pán)自下而上，由大到小地疊放一起，各紙盤(pán)從小到大編號(hào)為1，2，…，n，奇數(shù)編號(hào)圓盤(pán)為白色，偶數(shù)編號(hào)圓盤(pán)為黑色。如圖A2所示?，F(xiàn)要求將金針A上的這一疊紙盤(pán)移到金針B上，并仍按同樣順序疊置。圖A2 雙色漢諾塔問(wèn)題的初始狀態(tài)在移動(dòng)紙盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則（1）：每次只能移動(dòng)一個(gè)紙盤(pán)；規(guī)則（2）：任何時(shí)刻都不允許將較大的紙盤(pán)壓在較小的紙盤(pán)之上；規(guī)則（3）：任何時(shí)刻都不允許將同色圓盤(pán)疊在一起；規(guī)則（4）：在滿足移動(dòng)規(guī)則（1）和（3）的前提下，可將紙盤(pán)移至A，B，C中任一根金針上。試設(shè)計(jì)一個(gè)算法，用最少的移動(dòng)次數(shù)將塔座A上的n個(gè)圓盤(pán)移到塔座B上，并仍按同樣順序疊置。分析與解答：可用教材中的標(biāo)準(zhǔn)Hanoi塔算法。問(wèn)題是要證明標(biāo)準(zhǔn)Hanoi塔算法不違反規(guī)則（3）。用數(shù)學(xué)歸納法。設(shè)Hanoi（n，A，B，C）將塔座A上的n個(gè)圓盤(pán)，以塔座C為輔助塔座，移到目的塔座B上的標(biāo)準(zhǔn)Hanoi塔算法。歸納假設(shè)：當(dāng)圓盤(pán)個(gè)數(shù)小于n時(shí)，Hanoi（n，A，B，C）不違反規(guī)則（3），且在移動(dòng)過(guò)程中，目的塔座B上最底圓盤(pán)的編號(hào)與n具有相同奇偶性，輔助塔座C上最底圓盤(pán)的編號(hào)與n具有不同奇偶性。當(dāng)圓盤(pán)個(gè)數(shù)為n時(shí)，標(biāo)準(zhǔn)Hanoi塔算法Hanoi（n，A，B，C）由以下3個(gè)步驟完成。① Hanoi（n－1，A，C，B）；② Move（A，B）；③ Hanoi（n－1，C，B，A）。按歸納假設(shè)，步驟①不違反規(guī)則（3），且在移動(dòng)過(guò)程中，塔座C上最底圓盤(pán)的編號(hào)與n1具有相同奇偶性，塔座B上最底圓盤(pán)的編號(hào)與n1具有不同奇偶性，從而塔座B上最底圓盤(pán)的編號(hào)與n具有相同奇偶性，塔座C上最底圓盤(pán)的編號(hào)與n具有不同奇偶性。步驟②也不違反規(guī)則（3），且塔座B上最底圓盤(pán)的編號(hào)與n相同。按歸納假設(shè)，步驟③不違反規(guī)則（3），且在移動(dòng)過(guò)程中，塔座B上倒數(shù)第2個(gè)圓盤(pán)的編號(hào)與n－1具有相同奇偶性，塔座A上最底圓盤(pán)的編號(hào)與n－1具有不同奇偶性，從而塔座B上倒數(shù)第2個(gè)圓盤(pán)的編號(hào)與n具有不同奇偶性，塔座A上最底圓盤(pán)的編號(hào)與n具有相同奇偶性。因此在移動(dòng)過(guò)程中，塔座B上圓盤(pán)不違反規(guī)則（3），而且塔座B上最底圓盤(pán)的編號(hào)與n具有相同奇偶性，塔座C上最底圓盤(pán)的編號(hào)與n具有不同奇偶性。由數(shù)學(xué)歸納法即知，Hanoi（n，A，B，C）不違反規(guī)則（3）。第3章一、選擇題1. B 2. B二、填空題1. 235。logn＋12. 2n1三、簡(jiǎn)答題1. 將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的類(lèi)型相同問(wèn)題，這些子問(wèn)題相互獨(dú)立，以便各個(gè)擊破，分而治之。如果原問(wèn)題可分割成m個(gè)子問(wèn)題，1＜m≤n，并且這些子問(wèn)題都可解，然后求解這些問(wèn)題，那么就可利用這些子問(wèn)題的解求出原問(wèn)題的解；如果子問(wèn)題還比較復(fù)雜而不能直接求解，還可以繼續(xù)細(xì)分，直到子問(wèn)題足夠小，能夠直接求解為止。此外，為了得到原始問(wèn)題的解，必須找到一種途徑能夠?qū)⒏鱾€(gè)子問(wèn)題的解組合成原始問(wèn)題的一個(gè)完整答案。2. 將待查的數(shù)據(jù)與非降序數(shù)組中的中間元素進(jìn)行比較，若二者相等則表示查到；若該數(shù)據(jù)小于中間元素的值，則下次在數(shù)組的前半部分中繼續(xù)找；否則，在數(shù)組的后半部分中查找。即每次檢索將與待查數(shù)據(jù)的比較次數(shù)減半。如此繼續(xù)進(jìn)行下去，直到查到該值的元素或不存在所查找的數(shù)據(jù)。此種分治方法，稱為二分檢索。四、計(jì)算題1. 作一個(gè)“二分”檢索算法，它將原集合分成1/3和2/3大小的兩個(gè)子集。輸入：已按非減序分類(lèi)的n個(gè)元素的數(shù)組A和X，X是被檢索的項(xiàng)。A[0]未用。輸出：若X在A中，輸出下標(biāo)j滿足A[j]= X，否則輸出0。Int BinarySearch (A, n, X){ int k=1。 m=n。 while (k=m) { j = (k+m)/3。 /* j=(k+m)/3*/ if (X==A[j]) return j。 if (XA[j]) m= j1 else k= j+1。 return 0；}時(shí)間分析：比較次數(shù)2. 作一個(gè)“三分”檢索算法，它首先檢查1/3處的元素是否與X相等，然后檢查2/3處的元素，等等。這樣，或者找到X，或者將集合縮小到原來(lái)的1/3。試寫(xiě)出此算法并分析其復(fù)雜性。輸入：已安排減序分類(lèi)的n個(gè)元素的數(shù)組A和X，X是被檢索的項(xiàng)。A[0]未用。輸出：若X在A中，輸出下標(biāo)j滿足A[j]= X，否則輸出0。Int ThirdSearch(A,n, X){ int k =1。 m = n。 While (k=m) { i = (k + m )/3。 /* i = (k +m)/3 */ if (X==A[i]) return i。 if (XA[i]) m= i1 else { j = 2 (k + m)/3) /。 /* j = 2 (k + m)/3) */ if (X==A[j]) return j。 if (XA[j]) { k = i +1。m = j1} else k= j+1。 } } return 0；}時(shí)間分析：比較次數(shù)解得方程：T(n)=1+log 3 n3. 設(shè)計(jì)一個(gè)在有n個(gè)元素的集合中通過(guò)比較找出最大和次最大元素的算法，使其復(fù)雜度為n+logn2。算法：找最大和次大元素輸入：有n個(gè)元素的數(shù)組A輸出：最大和次最大元素Max和SubMax。void Find(A)//遞歸算法{ if(|A|==2) { 設(shè)A={a,b} (Max,SubMax) (Max(a,b),SubMax(a,b))。 } else { 把A分成兩個(gè)子集A1和A2，各有一半元素； (Max1,SubMax1) Find(A1)。 (Max2,SubMax2) Find(A2)。 SubMax3= Min(Max1, Max2)。 SubMax4= Max(SubMax1, SubMax2) (Max,SubMax) (Max(Max1, Max2),SubMax(SubMax3, SubMax4)) } }時(shí)間分析：T(n)為算法的最壞時(shí)間。當(dāng)n=2時(shí)，T(n)=1；當(dāng)n2時(shí)，則需要進(jìn)行兩次遞歸調(diào)用及之后的比較。故有： T(n) = 5 n/24. 求解最接近中位數(shù)的k個(gè)數(shù)：給定由n個(gè)互不相同的數(shù)組成的集合A以及正整數(shù)k≤n，設(shè)計(jì)一個(gè)O（n）時(shí)間復(fù)雜度的查找A中最接近A的中位數(shù)的k個(gè)數(shù)的算法。在采用分治法進(jìn)行查找時(shí)，為了滿足分治法的平衡原則，需要將數(shù)組分成兩個(gè)大小基本相同的子數(shù)組，其中的那個(gè)劃分點(diǎn)就是中位數(shù)。所以，中位數(shù)是指數(shù)組中能將數(shù)組劃分成兩個(gè)大小基本相同的兩個(gè)子數(shù)組的那個(gè)元素，即中位數(shù)是第 233。n／2249。 小的數(shù)。解析：（1）找出A中的中位數(shù)mid；（2）計(jì)算T = {|a mid|，a206。A}；（3）找出T的第k小元素b；（4）根據(jù)b找出所要的解{ |a mid|≤b，a206。A }。由于在最壞情況想選擇的時(shí)間復(fù)雜度為O（n）。所以，（1）和（3）需要O（n）次計(jì)算，（2）和（4）也只需要O（n）次計(jì)算。因此，本算法在最壞情況下，時(shí)間復(fù)雜度為O（n）。例如，A = {50，13，80，30，6，27，35}，k = 3，求最接近中位數(shù)的k個(gè)數(shù)。（1）找出A中的中位數(shù)mid：將A排序 = {6，13，27，30，35，50，80}，mid=30。（2）計(jì)算T = {|a mid|，a206。A}：T={20，13，50，0，24，3，5}。 （3）找出T的第k小元素b：T的第k小元素b = 5。（4）根據(jù)b找出所要的解{ a，|a mid|≤b，a206。A }：{30，27，35}。5. 求有序數(shù)組A和B的中位數(shù)設(shè)A［0∶n1］和B［0∶n1］為兩個(gè)數(shù)組，每個(gè)數(shù)組中含有n個(gè)已排好序的數(shù)。設(shè)計(jì)一個(gè)O(1ogn)時(shí)間復(fù)雜度的算法，找出A和B的2n個(gè)數(shù)的中位數(shù)median。解析：（1）算法設(shè)計(jì)思想。考慮問(wèn)題的一般性：設(shè)A［il：j1］和B［i2：j2］是A和B的排序好的子數(shù)組，且長(zhǎng)度同，即j1i1 = i2j2。找出這兩個(gè)子數(shù)組中2(j1i1＋1)個(gè)數(shù)的中位數(shù)。首先注意到，若A［i1］≤B［j2］，則中位數(shù)median滿足A［i1］≤median≤B［j2］。同理，若A［i1］≥B［j2］，則B［j2］≤median≤A［i1］。設(shè)m1＝(i1＋j1)／2，m2 = (i2＋j2)／2，則m1十m2 ＝ ((i1＋j1)／2＋(i2十j 2)／2＝i1＋(j1一i1)／2 + i2 ＋(j2—i2)／2＝i1＋i2＋(j1一i l)／2＋(j2—i2)／2。由于j1—i1＝j(luò)2—i2，故(j1一i1)／2＋(j2一i2)／2＝j(luò)1一i1＝j(luò)2一i2。因此，m1＋m2＝i1＋i 2＋jl一i1＝i2＋jl＝i1＋i2＋j2—i2＝i1＋j2。當(dāng)A［m1］＝B［m2］時(shí)，median＝A［m1］＝B［m2］。當(dāng)A［m1］＜B［m2］時(shí)，設(shè)median1是A［m1：jl］和B［j 2：m2］的中位數(shù)，則median＝Median1。當(dāng)A［m1］＞B［m2］時(shí)，設(shè)median2是A［i1：m1］和B［i2：j2］的中位數(shù)，類(lèi)似地有median＝median2。通過(guò)以上的討論，可以設(shè)計(jì)出查找兩個(gè)子數(shù)組A［i1:j1］和B［i2:j2］的中位數(shù)median的算法。（2）算法復(fù)雜性。設(shè)在最壞情況下，算法所需的計(jì)算時(shí)間為T(mén)(2n)。由算法中m1和m2的選取策略可知，在遞歸調(diào)用時(shí)，數(shù)組A和B的大小都減少了一半。因此，T(2n)滿足遞歸式：解此速歸方程可得：T(2n)＝O(logn)。比如 A={12，34，56，62，78，81，95}，B={23，38，45，67，89，103，120}。求數(shù)組A和B中位數(shù)。解析：m1＝(i1＋j1)／2＝3，m2 = (i2＋j2)／2＝3。 A［m1］＝ 62，B［m2］＝ 67，則根據(jù) 當(dāng)A［m1］＜B［m2］時(shí)，設(shè)median1是A［m1：jl］和B［i2：m2］的中位數(shù)，則median＝Median1。有：median＝ A［m1：jl］和B［i2：m2］的中位數(shù) ＝ A［3：6］和B［0：3］的中位數(shù) ＝ {62，78，81，95}和{23，38，45，67}的中位數(shù) ＝ 62再比如 A={12，34，56，62，78，81，95}，B={23，38，45，60，89，103，120}。求數(shù)組A和B中位數(shù)。解析：m1＝(i1＋j1)／2＝3，m2 = (i2＋j2)／2＝3。 A［m1］＝ 62，B［m2］＝ 60，則根據(jù) 當(dāng)A［m1］＞B［m2］時(shí)，設(shè)median2是A［i1：m1］和B［m2：j2］的中位數(shù)，類(lèi)似地有median＝median2。有：median＝ A［0：3］和B［3：6］的中位數(shù) ＝ A［3：6］和B［0：3］的中位數(shù) ＝ {12，34，56，62}和{60，89，103，120}的中位數(shù) ＝ 606. 利用整數(shù)相乘算法37計(jì)算兩個(gè)二進(jìn)制數(shù)1011和1101及兩個(gè)十進(jìn)制數(shù)3141和5327的乘積。解答：（1）x=1011, y=1101Mul(1011, 1101,4) // A=10, B=11, C=11, D=01 m1=Mul(A,C,n/2)=Mul(10,11,2) //遞歸調(diào)用 A=1, B=0, C=1, D=1 m1=Mul(A,C,n/2) =Mul(1,1,2/2)=1//遞歸調(diào)用并返回Mul(1,1,2/2) m2=Mul(AB,DC,n/2) =Mul(1,0,2/2)=0 m3=Mul(B,D,n/2) = Mul(0,1,2/2)=0 1*(1*22+(1+0+0)* 21+0)=110 //返回Mul(10,11,2)=110 m2=Mul(AB,DC,n/2)=Mul(1011,0111,2)= Mul(1,10,2) s=(1)*( 1)=1 A=0, B=1, C=1, D=0 m1= Mul(A,C,n/2) = Mul(0,1,2/2)=0 m2=Mul(AB,DC,n/2) = Mul(1,1,2/2)=1 m3= Mul(B,D,n/2) = Mul(1,0,2/2)=0 1*(0*22+(0+1+0)* 21+0)=10 m3= Mul(B,D,n/2) = Mul(11,01,2