算法分析與設(shè)計(jì)及案例習(xí)題解析

1、習(xí) 題 解 析第1章1. 解析：算法主要是指求解問題的方法。計(jì)算機(jī)中的算法是求解問題的方法在計(jì)算機(jī)上的實(shí)現(xiàn)。2. 解析：算法的五大特征是確定性、有窮性、輸入、輸出和可行性。3. 解析：計(jì)算的算法，其中n是正整數(shù)?？梢匀⊙h(huán)變量i的值從1開始，算i的平方，取平方值最接近且小于或者等于n的i即可。4. 解析：可以使用反證法，設(shè)i=gcd(m, n)=gcd(n, m mod n)，則設(shè)m=a*i，n=b*i，且a與b互質(zhì)，這時(shí)m mod n=（a-x*b）*i，只需要證明b和a-x*b互質(zhì)，假設(shè)二者不互質(zhì)，可以推出a與b不互質(zhì)，因此可以得到證明。5. 解析：自然語言描述：十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制整數(shù)

2、采用“除2取余，逆序排列”法。具體做法是：用2整除十進(jìn)制整數(shù)，可以得到一個(gè)商和余數(shù)；再用2去除商，又會(huì)得到一個(gè)商和余數(shù)，如此進(jìn)行，直到商為0時(shí)為止，然后把先得到的余數(shù)作為二進(jìn)制數(shù)的低位有效位，后得到的余數(shù)作為二進(jìn)制數(shù)的高位有效位，依次排列起來。流程圖：如圖*.1圖*.1 十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)流程圖6. 解析：a.如果線性表是數(shù)組，則可以進(jìn)行隨機(jī)查找。由于有序，因此可以進(jìn)行折半查找，這樣可以在最少的比較次數(shù)下完成查找。b.如果線性表是鏈表，雖然有序，則只能進(jìn)行順序查找，從鏈表頭部開始進(jìn)行比較，當(dāng)發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的值大于待查找元素值，則查找失敗。7. 解析：本題主要是舉例讓大家了解算法的精確性。

3、過程中不能有含糊不清或者二義性的步驟。大家根據(jù)可行的方式總結(jié)一下閱讀一本書的過程即可。8. 解析：數(shù)據(jù)結(jié)構(gòu)中介紹的字典是一種抽象數(shù)據(jù)結(jié)構(gòu)， 由一組鍵值對(duì)組成， 各個(gè)鍵值對(duì)的鍵各不相同， 程序可以將新的鍵值對(duì)添加到字典中， 或者基于鍵進(jìn)行查找、更新或刪除等操作。由于本題已知元素唯一，因此大家可以據(jù)此建立一個(gè)自己的字典結(jié)構(gòu)。實(shí)現(xiàn)字典的方法有很多種： 最簡單的就是使用鏈表或數(shù)組， 但是這種方式只適用于元素個(gè)數(shù)不多的情況下； 要兼顧高效和簡單性，可以使用哈希表； 如果追求更為穩(wěn)定的性能特征， 并且希望高效地實(shí)現(xiàn)排序操作的話， 則可以使用更為復(fù)雜的平衡樹。在字典之上的主要操作可以有：創(chuàng)建操作，添加操作，

4、刪除操作，查找操作，以及必要的字典維護(hù)操作。第2章1. 解析：根據(jù)本章所述，遞歸算法和非遞歸算法的數(shù)學(xué)分析方法分為5個(gè)步驟。2. 解析： 本題相當(dāng)于對(duì)多項(xiàng)式找“主項(xiàng)”，也就是在除去常系數(shù)外，影響函數(shù)值遞增速度最快的項(xiàng)。a)b)c) ，c為常數(shù)d)e)3. 解析：本題中如果手套分左右手，則最優(yōu)情況選2只，最差情況選12只。本題中如果手套不分左右手，則最優(yōu)情況仍然選2只，最差情況選4只。從本題的初衷推測(cè)設(shè)置題目應(yīng)該是分左右手的手套，在考慮顏色的情況下，選擇一雙進(jìn)行匹配。4. 解析： 本題的一般解法可以使用高等數(shù)學(xué)中求二者比值的極限來確定結(jié)果。 a) 相同 b) 第一個(gè)小 c) 二者相同 d) 第一

5、個(gè)大 e) 二者相同 f) 第一個(gè)小5. 解析：a) b) c) d) 6. 解析：參見本章例2.7。第3章1. 解析：蠻力法主要依靠問題的定義，采用簡單直接的求解方法。由此決定了蠻力法是解決問題的最簡單也是最普遍的算法，同時(shí)其經(jīng)常作為簡單問題求解的方法和衡量其他算法的依據(jù)。2. 解析： 2，6，1，4，5，3，2選擇排序：|2614532i=0: min最后得2，交換二者。1|624532i=1: min最后得2，交換二者。12|64532i=2: min最后得6，交換二者。122|4536i=3: min最后得5，交換二者。1223|546i=4: min最后得5，交換二者12234|56

6、i=5: min最后得5。122345|6結(jié)束。冒泡排序：2614532214532|6i=0: 最大值6就位。12432|56i=1：第二大值5就位。1232|456i=2：第三大值4就位。122|3456i=3：第四大值3就位。12|23456i=4：第五大值2就位。1|223456i=5：第六大值2就位，剩余的1也就位，排序結(jié)束。3. 解析：選擇排序不穩(wěn)定，如3.1.1節(jié)例子：4,4,2。冒泡排序穩(wěn)定。4. 解析：如2題例子，到i=4時(shí)就沒有發(fā)生交換的活動(dòng)了。這時(shí)可以在冒泡排序的交換部分加入一個(gè)布爾變量，如本次循環(huán)中沒有發(fā)生交換，則以后的掃描就可以不進(jìn)行。5. 解析：如果n個(gè)點(diǎn)共線，則其

7、最近對(duì)只需要考察相鄰的點(diǎn)對(duì)，因此在對(duì)點(diǎn)進(jìn)行按行坐標(biāo)排序后，只需要兩兩計(jì)算相鄰兩點(diǎn)距離，就可以找到最近對(duì)。6. 解析：所有的過程與尋找二維空間中的最近點(diǎn)對(duì)類似，只是計(jì)算距離的公式變?yōu)椋簊qrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z)使用循環(huán)計(jì)算任意兩個(gè)點(diǎn)之間的距離，然后記錄最小值即可。類似的，如果推廣到n維空間，需要考慮空間中任意兩點(diǎn)的距離計(jì)算公式，同樣計(jì)算每兩個(gè)點(diǎn)之間的距離，并記錄最小距離即可。7. 解析：a) 線段的凸包為本身，極點(diǎn)為兩個(gè)端點(diǎn)。b) 正方形的凸包為本身，極點(diǎn)為四個(gè)頂點(diǎn)。c)

8、正方形的邊界不是凸包，凸包為正方形（包括邊界和內(nèi)部）。d) 直線的凸包為本身，沒有極點(diǎn)。8. 解析：哈密頓回路的窮舉查找算法，首選選擇起點(diǎn)（圖中任意一個(gè)點(diǎn)開始），之后不斷尋找下一個(gè)點(diǎn)，下一個(gè)點(diǎn)應(yīng)該滿足：1) 不在已經(jīng)走過的點(diǎn)中；2) 與上一個(gè)點(diǎn)有直連路徑。如果這樣能找到回到起點(diǎn)的路徑，并且遍歷所有點(diǎn)，則為一條哈密頓回路。然后依次進(jìn)行下一個(gè)可行點(diǎn)的選擇。9. 解析：生成給定元素的一個(gè)排列，通過連續(xù)比較它們之間的元素，檢查它們是否符合排序的要求。如果符合就停止，否則重新生成新的排列。最差情況生成排列的個(gè)數(shù)是，每趟連續(xù)元素比較次數(shù)為n-1次。所以效率類型為。第4章1. 解析：假定把16枚硬幣上網(wǎng)例子

9、看作一個(gè)大的問題。（1）把這一問題分成兩個(gè)小問題，隨機(jī)選擇8個(gè)硬幣作為第一組稱為A組，剩下的8個(gè)硬幣作為第二組稱為B組；這樣，就把16個(gè)硬幣的問題分成兩個(gè)8個(gè)銀幣的問題來解決；（2）判斷A組和B組中是否有偽幣，可以使用儀器比較A組硬幣和B組硬幣的重量；假如兩組硬幣重量相等，則可以判斷偽幣不存在；假如兩組硬幣重量不相等，則存在偽幣，并且可以判斷它位于較輕的那一組硬幣中；（3）假設(shè)B是輕的那一組，因此再把它分成兩組，每組有4個(gè)硬幣，稱其中一組為B1，另一組為B2，比較這兩組，肯定有一組輕一些，假設(shè)B1輕，則偽幣在B1中，再將B1分為兩組，每組有兩個(gè)硬幣，稱其中一組為B1a,另一組為B1b。比較這兩

10、組，可以得到一個(gè)較輕的組，由于這個(gè)組織有兩個(gè)硬幣，因此不必再細(xì)分。比較組中兩個(gè)硬幣的重量，可以立即知道哪個(gè)硬幣輕一些，輕幣就是要找的偽幣；最終，比較次數(shù)為4次。2. 解析：逆序?qū)κ侵冈谛蛄衋0,a1,a2.an中，若aij)，則(ai,aj)上一對(duì)逆序?qū)?。而逆序?shù)是指序列中逆序?qū)Φ膫€(gè)數(shù)。例如： 1 2 3是順序，則逆序數(shù)是0；1 3 2中(2,3)滿足逆序?qū)Φ臈l件，所以逆序數(shù)只有1； 3 2 1中(1,2)(1,3)(2,3)滿足逆序?qū)Γ阅嫘蚴?。由定義不能想象，序列n的逆序數(shù)范圍在0,n*(n-1)/2，其中順序時(shí)逆序數(shù)為 0，完全逆序時(shí)逆序數(shù)是n*(n-1)/2。對(duì)于一個(gè)數(shù)組s將其分為

11、2個(gè)部分s1和s2，求s1和s2的逆序?qū)€(gè)數(shù)，再求s1和s2合并后逆序?qū)Φ膫€(gè)數(shù)：這個(gè)過程與merge排序的過程是一樣的，可以使用merge排序求得。代碼如下：/a為字符數(shù)組，len為字符數(shù)組的長度int number = 0; /number表示逆序?qū)Φ膫€(gè)數(shù)void copy(char *dest, char *src, int l, int r)while(l = r) destl = srcl; l+; void mergeSort(char *a, int size)char *b = (char*)malloc(sizeof(char) * size);mergePass(a, b,

12、0, size - 1);free(b);void mergePass(char *a, char *b, int l, int r) int m; if(l r) m = (l + r) / 2; mergePass(a,b,l,m); mergePass(a,b,m+1,r); merge(a,b,l,m,r); copy(a,b,l,r);void merge(char *a, char *b, int l, int m, int r)int i = l, j = m + 1;while( i = m & j = r) if(ai = aj) bl+ = ai+; else bl+ =

13、aj+;number += m-i+1; while(i = m) bl+ = ai+; while(j 2時(shí)，先求出序列A1.n-1中的第1大元素x1和第2大元素x2；然后，通過2次比較即可在三個(gè)元素x1，x2和An中找出第2大元素，該元素即為A1.n中的第2大元素。SecondElement (Alow.high, max1, max2) /假設(shè)主程序中調(diào)用該過程條件為high-low=2 if(high-low=2) if(AlowAhigh) max2=Alow; max1=Ahigh; else max2=Ahigh; max1=Alow; else SecondElement (A

14、low . high,x1,x2); if(x1=An) max2=x2; max1=x1; else max2=An; max1=x1; 該算法的時(shí)間復(fù)雜度滿足如下遞歸方程：T(n)=T(n-1)+2; T(2)=1。解得T(n)=2n-3。4. 解析：如果在算法SELECT執(zhí)行中每次標(biāo)準(zhǔn)元素都恰好選取的是序列中的真正中值元素，那算法的行為與二分查找算法類似。最壞情況下，每次在原序列的一半上進(jìn)行查找。此時(shí)如果標(biāo)準(zhǔn)元素得到時(shí)間為T（n）；如果標(biāo)準(zhǔn)元素得到時(shí)間為T（1），則算法的最壞情況時(shí)間與二分檢索一樣，為T（logn）。5. 解析：對(duì)于兩棵二叉樹T1和T2，若其根結(jié)點(diǎn)值相同，且其左右子樹分別

15、對(duì)應(yīng)相同，則T1=T2，否則T1T2。其描述如下：Boolean BTEQUAL(BT T1, BT T2) if(T1= =NULL&T2=NULL) return True; /均為空樹 if(T1&T2&T1.data=T2.data&BTEQUAL(T1.lchild,T2.lchild) &BTEQUAL (T1.lchild,T2.lchild) return True; return False;6. 解析：快速分類算法是根據(jù)分治策略設(shè)計(jì)出來的算法。其關(guān)鍵步驟就是“劃分”：根據(jù)某個(gè)元素v為標(biāo)準(zhǔn)，將序列中的元素重新整理，使得整理后的序列中v之前的元素都不大于v，而v之后的元素都不小

16、于v。此時(shí)，元素v即找到了其最終的位置。要得到序列的排序結(jié)果，再只需對(duì)v之前的元素和v之后的元素分別排序即可，這可通過遞歸處理來完成。7. 解析：當(dāng)序列中的元素都相同時(shí)，每次執(zhí)行算法SPLIT時(shí)，僅出現(xiàn)一次元素交換，即將序列的第一個(gè)元素與最后一個(gè)元素交換，且劃分元素的新位置為該序列的最后一個(gè)位置。因此，在元素均相同的數(shù)組A1.n上，算法QUICKSORT的執(zhí)行特點(diǎn)為：每次劃分后剩下A1.n-2未處理，第n-1此劃分后剩下A1（已有序）。在這類實(shí)例上，算法的執(zhí)行時(shí)間為：(n-1)+(n-2)+2+1=(n2)，屬于最壞的情況。此外，算法最后所得結(jié)果中各元素順序如下：A2,A3,A4,An,A1（

17、這里，Ai表示輸入時(shí)的第i個(gè)元素，i=1,2,n）。8. 解析：算法QUICKSORT所需要的工作空間是指其遞歸執(zhí)行時(shí)所需要的?？臻g，其大小與遞歸調(diào)用的深度成比例?？紤]算法在n個(gè)元素上執(zhí)行時(shí)的遞歸調(diào)用樹，樹最高可為T(n)，最矮可為T(logn)。所以，算法所需的工作空間在T(logn)到T(n)之間變化。第5章1. 解析：0個(gè)元素的冪集為空集；1個(gè)元素的冪集為空集和本身；（可以看做空集并空集加入元素的集合）2個(gè)元素的冪集為1個(gè)元素的冪集和該冪集中每個(gè)集合加入新元素的集合的并集；類似的繼續(xù)下去可以生成n個(gè)元素的冪集。2. 解析：插入排序：2，6，1，4，5，3，22|614532i=1：A1插

18、入26|14532i=2：A2插入126|4532i=3：A3插入1246|532i=4：A4插入12456|32i=5：A5插入123456|2i=6：A6插入1223456|結(jié)束3. 解析：對(duì)照給出的算法，進(jìn)行鏈表插入排序。這時(shí)，每次進(jìn)行插入時(shí)均需要從鏈表頭部節(jié)點(diǎn)開始，尋找插入位置。因此要設(shè)置相鄰的兩個(gè)指針，用于尋找插入位置。具體請(qǐng)大家自己完成。4. 解析：折半插入排序：/輸入：待排序數(shù)組A0.n-1/輸出：排好序后的數(shù)組A0.n-1void ISort(&A0.n-1)/* v用來保存待插入元素；s, t, k 分別是插入位置尋找時(shí)使用的指針，s指向頭，t指向尾，k指向中間。*/for(

19、i=1; i=s & vAk)if(vAk)s=k+1;k=;elset=k-1;k=;if(Ak=k; j-)Aj+1 = Aj;Ak = v;；最差效率為：。5. 解析：用減一法進(jìn)行拓?fù)渑判?，每次刪除入度為0的結(jié)點(diǎn)即可，所有可能情況共有7種：d-a-b-c-g-e-f；d-a-b-c-g-f-e；d-a-b-g-c-e-f；d-a-b-g-c-f-e；d-a-c-b-g-e-f；d-a-c-b-g-f-e；d-a-b-g-e-c-f。同樣，可以用深度優(yōu)先遍歷時(shí)，出棧順序的逆序作為拓?fù)渑判颉?解析：字典序列算法是一種非遞歸算法。而它正是STL中Next_permutation的實(shí)現(xiàn)算法。它的

20、整體思想是讓排列成為可遞推的數(shù)列，也就是說從前一狀態(tài)的排列，可以推出一種新的狀態(tài)，直到最終狀態(tài)。比如說，最初狀態(tài)是12345，最終狀態(tài)是54321。其實(shí)我覺得這跟我們手動(dòng)做全排列是一樣的。首先是12345，然后12354，然后12435，12453.逐漸地從后往前遞增?？纯此惴枋觯?首先，將待排序列變成有序（升序）序列。然后，從后向前尋找，找到相鄰的兩個(gè)元素，TiTi(很多時(shí)候k=j)，找到它，交換Ti跟Tk，并且將Tj到Tn(Tn是最后一個(gè)元素)的子序列進(jìn)行倒置操作。輸出此序列。并回到第二步繼續(xù)尋找ij。例如839647521是數(shù)字19的一個(gè)排列。從它生成下一個(gè)排列的步驟如下：自右至左找出

21、排列中第一個(gè)比右邊數(shù)字小的數(shù)字4 839647521在該數(shù)字后的數(shù)字中找出比4大的數(shù)中最小的一個(gè)5 839647521將5與4交換 839657421將7421倒轉(zhuǎn) 839651247所以839647521的下一個(gè)排列是839651247。839651247的下一個(gè)排列是839651274。以下是C語言的代碼：#include #define MAX 1000int n=4; int setMAX=1,2,3,4;int flag=0;/swap a and bvoid s *a,int *b) int temp=*a; *a=*b; *b=temp;/reverse a range of a

22、 setvoid reverse(int start,int end) int index_r=0; int new_end=end-start; for(index_r=0;index_r=new_end/2;index_r+) sindex_r+start,&setnew_end-index_r+start);void set_print() int index; for(index=0;index0;index_i-) if(setindex_i0;index_k-) if(setindex_ksetindex_i) break; sindex_i,&setindex_k); rever

23、se(index_j,n-1); find_next();int main() int count=1; int i=n-1; while(i=0) set0=count+; find_next(); s0,&seti); reverse(1,n-1); i-; return 0;7. 解析：說到漢諾塔問題，首先想到的是最經(jīng)典的遞歸解法。在求格雷碼的方法中，提到可以觀察格雷碼每一次改變的位數(shù)和漢諾塔每次移動(dòng)的盤子的編號(hào)，從而產(chǎn)生一種不需要遞歸和堆棧的漢諾塔解法。在生成格雷碼的算法中，依次改變的位數(shù)是最低位和從右往左數(shù)第一個(gè)1所在位的左一位，對(duì)應(yīng)漢諾塔的盤子就是最小的盤子和中間某個(gè)盤子。最小的盤

24、子有兩種可能的移動(dòng)方案，其他的盤子只有一種可能。對(duì)于最小盤子移動(dòng)到的柱子的解決方法是，根據(jù)觀察，當(dāng)盤子總數(shù)是奇數(shù)時(shí)，最小盤子的位置依次是“3-2-1-3-2-1.”；當(dāng)總數(shù)是偶數(shù)時(shí)，這個(gè)順序是“2-3-1-2-3-1.”。據(jù)此從格雷碼到漢諾塔的一種對(duì)應(yīng)解決方案就產(chǎn)生了。如下是非遞歸方法的代碼。int main()char digitMAX; int positionMAX; int i,j; for(i = 0; i 20) break; if(even) coutposition0circleiendl; position0 = circlei; i = (+i)%3; FLIP_DIGIT

25、(digit0); else for(j = 0 ; j n & digitj=0; j+) ; if(j = n-1) break; FLIP_DIGIT(digitj+1); coutpositionj+16-positionj+1-position0endl; positionj+1 = 6-positionj+1-position0; FLIP(even); cout=endl; system(pause); return 0;8. 解析：nm5234266813136 6272+136 3544 11088+544+1361768=1088+544+1369. 解析：順序查找的平均效

26、率約為：。最高效的排序算法其效率為：。因此，如果只做一次查找，不需要進(jìn)行排序后再折半查找。10. 解析： 構(gòu)造2-3樹的數(shù)據(jù)結(jié)構(gòu)。之后建立插入節(jié)點(diǎn)和分裂的算法。第6章1. 解析：以所經(jīng)過的權(quán)值之和最大值為例進(jìn)行說明。行進(jìn)的過程中，每次只有兩種選擇：向左或向右。一個(gè)有n層的數(shù)字三角形的完整路徑有2n條，所以當(dāng)n比較大的時(shí)候，搜索全部路徑，從中找出最大值，效率較低。采用動(dòng)態(tài)規(guī)劃方法實(shí)現(xiàn)。用d(i,j)表示從位置(i,j)出發(fā)時(shí)得到的最大值（包括位置(i,j)本身），可以寫出最大值的遞歸方程：由于遞歸方程中包含了重復(fù)子問題，直接采用遞歸方程求解， 效率較低。采用動(dòng)態(tài)規(guī)劃的備忘錄方法，用一張二維表記錄

27、中間過程的值，可以把時(shí)間效率提高到n2。2. 解析：采用動(dòng)態(tài)規(guī)劃方法實(shí)現(xiàn)。用fi表示以ai為結(jié)尾的最長上升子序列的長度，可建立如下遞歸方程： f是單調(diào)遞增的，因?yàn)槿绻衖=fj，那么fi必定可以被fj的內(nèi)容所更新。每處理到一個(gè)ai，要找到一個(gè)k滿足fk1= ai，并用ai更新fk，最終maxk|fk!=就是答案?？梢跃帉懗鰰r(shí)間復(fù)雜度為O(n2)的動(dòng)態(tài)規(guī)劃算法。3. 解析：用sumi,j表示將從第i顆石子開始的接下來j顆石子合并所得的分值。用fi,j表示將第從第i顆石子開始的接下來j顆石子合并所得的重量的最小值。有如下遞歸方程：可以編寫出時(shí)間復(fù)雜度為O(n3)的動(dòng)態(tài)規(guī)劃算法。如果采用四邊形不等式

28、優(yōu)化動(dòng)態(tài)規(guī)劃算法，可得到時(shí)間復(fù)雜度為O(n2)的動(dòng)態(tài)規(guī)劃算法，是一種比較高效的優(yōu)化算法。4. 解析：按照動(dòng)態(tài)規(guī)劃求解多階段決策的思路，每投資一個(gè)項(xiàng)目作為一個(gè)階段，將原問題劃分階段，從而將靜態(tài)模型轉(zhuǎn)化為動(dòng)態(tài)。用xk(k=1,2,3)表示第k個(gè)項(xiàng)目的投資額，其中用sk表示投資第k個(gè)項(xiàng)目前的資金數(shù)(k=1,2,3,4，k=4為虛設(shè)的階段)，則有0xksk 以及sk+1 = sk -xk 成立。用vk(sk, xk)表示在當(dāng)前在資金數(shù)為sk，投資額為xk的情況下的投資效益值。為便于理解，如下圖所示表示各階段內(nèi)容。效益值v3(s3, x3)效益值v2(s2, x2)效益值v1(s1,x1)s3s2s1x

29、3x2x1 項(xiàng)目1 項(xiàng)目2 項(xiàng)目3s4投資效益階段表示圖根據(jù)以上分析，可寫出求解問題的遞歸式和特殊值： 采用逆序倒推的方法，先計(jì)算在第三階段，即投資項(xiàng)目3時(shí)的最大效益，再考慮第二階段，即投資項(xiàng)目2時(shí)的最大效益，此時(shí)利用遞歸公式，其最大效益的獲得是在所有在第二階段的當(dāng)前效益與第三階段最大效益的累加和中求取最大值，同樣方法獲取第一階段的最大效益。5. 解析：利用高斯公式，從1到n的自然數(shù)之和為：1+2+3+n=n*(n+1)/2。題目要求：對(duì)于從1到N的連續(xù)整集合，劃分為兩個(gè)子集合，且保證每個(gè)集合的數(shù)字和是相等的。因而，劃分之后每個(gè)子集全的數(shù)字應(yīng)該為n*(n+1)/2的一半，即n*(n+1)/4由

30、于兩個(gè)子集中都是整數(shù)，所以n*(n+1)必為偶數(shù)，則可以設(shè)s=n*(n+1),并判斷s%4 ，則，s/=4是劃分之后子集合的數(shù)字和。dynj數(shù)組表示任意個(gè)數(shù)加起來等于j的組數(shù)，則有下面公式成立：dynj= dynj+dynj-i; 其中dynj-i表示加起來等于j-i的組數(shù)，利用上述公式，可得到問題的解。6. 解析：按照樣例輸入：即3 42 -1 50 51 3 -1 6-1 8 9 10則表示迷宮如下：ai,j保存第i行第j列的寶藏價(jià)值。令fi,j為從（1，1）走過第i行第j列時(shí)所能收集的寶藏的最大價(jià)值。有如下遞歸方程：同時(shí)滿足：ai,j-1初始 采用動(dòng)態(tài)規(guī)劃算法，利用遞推公式構(gòu)造并求解二維

31、表fi,j，目標(biāo)即求解出fn,m即可。7. 解析：按照樣例輸入如下：5 6 44 3 4 4 5ai表示第i首歌曲的長度。令fi,j,k表示前i首歌曲，用j張光盤，另加k分鐘能夠發(fā)行的最多歌曲樹木。有如下遞歸方程： 采用動(dòng)態(tài)規(guī)劃算法，利用遞推公式構(gòu)造并求解二維表fi,j,k，目標(biāo)即求解出fn,m,0或fn,m-1,t即可。8. 解析：按照樣例輸入如下：ACDEFABCDE令fi,j為將A的前i個(gè)字符變成B的前j個(gè)字符所用的最少操作步數(shù)。從后向前依次比較分析，fi,j有以下三種情況；(1)刪除A 中的前i-1 個(gè)字符中的最后一個(gè)字符，問題變?yōu)閷 中前i-1 個(gè)字符轉(zhuǎn)換為B 中的前j 個(gè)字符，即

32、：fI,j=fi-1,j+1;(2)在A 的前i-1 個(gè)字符中的最后插入一個(gè)字符，插入后使ai+1=bj，問題變?yōu)閷 中的前i 個(gè)字符轉(zhuǎn)換為B 中的前j-1 個(gè)字符，即：iI,j=fi,j-1+1;(3)將A 中的一個(gè)字符轉(zhuǎn)換為另一個(gè)字符。如果ai=bj，則fi,j=fi-1,j-1如果aibj，將ai 換成bj；則fi,j=fi-1,j-1+1綜上所述，有如下遞歸方程：初始 采用動(dòng)態(tài)規(guī)劃算法，利用遞推公式構(gòu)造并求解二維表fi,j，目標(biāo)即求解出fn,m即可。第7章1. 解析：由待排序數(shù)據(jù)可知，最小值為92，最大值為98，由此可創(chuàng)建一個(gè)長度為7的數(shù)組C，Ci（-1i0&PatternLengt

33、h0&i=0 & Patternj=Texti+j)/從右向左匹配j-;if(j=-1)/在文本中找到了模式，返回對(duì)應(yīng)位置return i;else/本輪匹配失敗，模式右移printf(n模式第%d次移動(dòng)距離：%d,count+1,DiscTexti+PatternLength-1-A);i=i+DiscTexti+PatternLength-1-A;count+;return -1;/在完成所有輪次匹配后，文本中沒有出現(xiàn)模式，返回-1void main()char Text80=FAILUREEISATHEBMOTHERCCFDSUCCESS;/定義文本char Pattern80=SUCC

34、E;/定義并初始化模式int n;/定義模式在文本中的位置int i;for(i=0;i-1)printf(n模式在文本中的位置是：%d,n+1);elseprintf(n模式?jīng)]有在文本中出現(xiàn)!);printf(n模式共向右移動(dòng)了%d次！n,count);4. 解析：C語言中的關(guān)鍵字為：auto、break、case、char、const、continue、default、do、double、else、enun、extern、float、for、goto、if、int、long、register、return、short、signed、sizeof、static、struct、switch、t

35、ypedef、union、unsigned、void、volatile、while各記錄的散列地址如下：f(auto)=1、f(break)=2、f(case)=3、f(char)=3、f(const)=3、f(continue)=3、f(default)=4、f(do)=4、f(double)=4、f(else)=5、f(enum)=5、f(extern)=5、f(float)=6、f(for)=6、f(goto)=7、f(if)=9、f(int)=9、f(long)=12、f(register)=18、f(return)=18、f(short)=19、f(signed)= 19、f(siz

36、eof)= 19、f(static)= 19、f(struct)= 19、f(switch)= 19、f(typedef)=20、f(union)=21、f(unsigned)=21、f(void)=22、f(volatile)=22、f(while)=23散列表如下：散列地址123456789記錄指針記錄autobreakcasedefaultelsefloatgotoNULLif記錄NULLNULLchardoenumforNULLint記錄constdoubleexternNULLNULL記錄continueNULLNULL記錄NULL散列地址1011128記錄指針記錄NULLNULLl

37、ongNULLNULLNULLNULLNULLregister記錄NULLreturn記錄NULL散列地址19226記錄指針記錄shorttypedefunionvoidwhileNULLNULLNULL記錄signedNULLunsignedvolatileNULL記錄sizeofNULLNULL記錄static記錄struct記錄switch記錄NULL平均查找長度=（115+29+34+42+51+61）/262.465. 解析：#includestdio.h#includestring.h#define RecordNum 32/定義記錄個(gè)數(shù)#define HashTableNum 3

38、2/定義散列表大小struct HashType/定義記錄類型char str80;struct HashType *next;int count=0;/定義查找次數(shù)/定義并初始化記錄數(shù)據(jù)struct HashType HashDataRecordNum= auto,NULL,break,NULL,case,NULL,char,NULL,const,NULL,continue,NULL,default,NULL,do,NULL,double,NULL,else,NULL,enum,NULL,extern,NULL,float,NULL,for,NULL,goto,NULL,if,NULL,in

39、t,NULL,long,NULL,register,NULL,return,NULL,short,NULL,signed,NULL,sizeof,NULL,static,NULL,struct,NULL,switch,NULL,typedef,NULL,union,NULL,unsigned,NULL,void,NULL,volatile,NULL,while,NULL;int HashAddressHashTableNum;/定義散列地址數(shù)組struct HashType *HashTableHashTableNum;/定義散列表數(shù)組struct HashType *p,*q;/定義搜索鏈表

40、指針void CalculateHashAddress()/根據(jù)散列函數(shù)計(jì)算各記錄散列地址,散列函數(shù)：f(s)int i,j,HashSumTemp;for(i=0;iRecordNum;i+)HashAddressi=HashDatai.str0-a+1;void CalculateHashTable()/將各記錄的指針分布到散列表中int i;for(i=0;iHashTableNum;i+)/初始化散列表HashTablei=NULL;for(i=0;inext;q-next=&HashDatai;/查找記錄時(shí)，先計(jì)算其散列地址int CalculateSearchRecordHashAddress(char record)return record0-a+1;void SearchRecord()/根據(jù)散列地址判斷待查找記錄的有無char record80;int SearchRecordHashAddress;printf(n請(qǐng)輸入待查找的記錄：);gets(record);SearchRecordHashAddress=Calcul