第2章作業(yè)答案2-3_2-15

1、1第2章 遞歸與分治策略 作業(yè)2主定理的應(yīng)用 1. T(n)=3T(n/7)+n k=3,m=7,d=1 有 kmd , T(n)=(nlogmk) =(nlog316) 322判斷判斷7個二分搜索算法的正確性個二分搜索算法的正確性。 下面的下面的7個算法與本章中的二分搜索算法個算法與本章中的二分搜索算法BinarySearch略有不同。請判斷這略有不同。請判斷這7個算個算法的正確性。如果算法不正確，請說明產(chǎn)法的正確性。如果算法不正確，請說明產(chǎn)生錯誤的原因。如果算法正確，請給出算生錯誤的原因。如果算法正確，請給出算法的正確性證明法的正確性證明。4二分搜索算法二分搜索算法： template i

2、nt BinarySearch(Type a , const Type& x, int left, int right) while (left=right) int mid = (left+right)/2; if (x = amid) return mid; if (x amid) right = mid-1; else left = mid+1; return -1; /未找到未找到x 522 （1） template int BinarySearch1(Type a , const Type& x, int n) int left=0; int right=n-1; while (le

3、ft amiddle) left = middle; else right = middle; return -1; 622 （1） 不正確。與主教材中的算法不正確。與主教材中的算法Binary Search相比，數(shù)組段左、右游標(biāo)相比，數(shù)組段左、右游標(biāo)left和和right調(diào)整不正確，導(dǎo)致陷入死循環(huán)。調(diào)整不正確，導(dǎo)致陷入死循環(huán)。 如：序列如：序列2 3 4 5，x=5時，時， left=0,right=3,mid=1,xa1=3,left=1 left=1,right=3,mid=2,xa2=4,left=2 left=2,right=3,mid=2,xa2=4,left=2 left=2,r

4、ight=3,mid=2,xa2=4,left=2 陷入死循環(huán)陷入死循環(huán)722 （1） 又如：序列又如：序列2 3 4 5，x=1時時 left=0,right=3,mid=1,xa1=3,right=1 left=0,right=1,mid=0,xa0=2, right=0 left=0,right=0,mid=0,xa0=2, right=0 left=0,right=0,mid=0,xa0=2, right=0 陷入死循環(huán)。陷入死循環(huán)。822 （2） template int BinarySearch1(Type a , const Type& x, int n) int left=0;

5、 int right=n-1; while (left right-1) int middle = (left+right)/2; if (x a1=3,left=1 left=1,right=3,mid=2,xa2=4,left=2 left=2,right-1=2,while循環(huán)結(jié)束循環(huán)結(jié)束 5=a2不為真不為真 故故return -1； 返回返回-1表示找不到表示找不到x，這是一個錯誤的結(jié)論！，這是一個錯誤的結(jié)論！1022 （3） template int BinarySearch1(Type a , const Type& x, int n) int left=0; int right

6、=n-1; while (left +1!= right) int middle = (left+right)/2; if (x = amiddle) left = middle; else right = middle; if (x = aleft) return left; return -1; 1122 （3） 同（同（2），不正確。），不正確。 (3)中中while (left +1!= right) 等同于（等同于（2）的）的while (left = amiddle) left = middle; else right = middle; 等同于（等同于（2）的）的 if (x a

7、middle) right = middle; else left = middle;1222 （4） template int BinarySearch1(Type a , const Type& x, int n) if(n0 & x=a0) int left=0; int right=n-1; while (left right) int middle = (left+right)/2; if (x a1=3,left=1 left=1,right=3,mid=2,xa2=4,left=2 left=2,right=3,mid=2,xa2=4,left=2 left=2,right=3,

8、mid=2,xa2=4,left=2 陷入死循環(huán)陷入死循環(huán)1422 （5） template int BinarySearch1(Type a , const Type& x, int n) if(n0 & x=a0) int left=0; int right=n-1; while (left right) int middle = (left+right+1)/2; if (x a2=4,left=2 left=2,right=3,mid=3,x=a3=5,left=3 left=3,right=3,while循環(huán)結(jié)束循環(huán)結(jié)束 5=a3,return 3; 輸出正確輸出正確1622 （5）

9、 正確。用幾個特殊實例證明其正確性。正確。用幾個特殊實例證明其正確性。 又如：序列又如：序列2 3 4 5，x=2時，時， left=0,right=3,mid=2,xa2=4,right=1 left=0,right=1,mid=1,xa2=4,left=2 left=2,right=3,mid=3,x=a3=5,left=3 left=3,right=3,while循環(huán)結(jié)束循環(huán)結(jié)束 7!=a3,return -1; 輸出正確輸出正確1822 （5） 正確。用幾個特殊實例證明其正確性。正確。用幾個特殊實例證明其正確性。 又如：序列又如：序列2 3 4 5，x=1時，時，x=a0不成立，不進入

10、不成立，不進入while循環(huán)循環(huán)且且x!=a0故故 return -1，表示在序列，表示在序列2 3 4 5中沒有中沒有1 輸出正確輸出正確1922 （5） 正確。用幾個特殊實例證明其正確性。正確。用幾個特殊實例證明其正確性。 如：序列如：序列2 2 4 4 4，x=4時，時， left=0,right=4,mid=2,x=a2=4,left=2 left=2,right=4,mid=3,x=a3=4,left=3 left=3,right=4,mid=4,x=a4=4,left=4 left=4,right=4,while循環(huán)結(jié)束循環(huán)結(jié)束 4=a4,return 4; 輸出正確輸出正確,且有

11、重復(fù)元素且且有重復(fù)元素且x為重復(fù)元素為重復(fù)元素的值時，返回最右邊該值所在下標(biāo)。的值時，返回最右邊該值所在下標(biāo)。2022 （6） template int BinarySearch1(Type a , const Type& x, int n) if(n0 & x=a0) int left=0; int right=n-1; while (left right) int middle = (left+right+1)/2; if (x a2=4,left=3 left=3,right=3, while結(jié)束結(jié)束 5=a3,return 3; 返回正確結(jié)果返回正確結(jié)果2222 （6） 如：序列如：序

12、列2 3 4 5，x=2時，時， left=0,right=3,mid=2,xa2=4,right=1 left=0,right=1,mid=1,xright,while循環(huán)結(jié)束循環(huán)結(jié)束 a5越界，越界，return -1，輸出不正確。，輸出不正確。 結(jié)論結(jié)論：與：與(5)相比，數(shù)組段左、右游標(biāo)相比，數(shù)組段左、右游標(biāo)left和和right調(diào)整不正確，導(dǎo)致有重復(fù)元素時返回錯誤結(jié)果。調(diào)整不正確，導(dǎo)致有重復(fù)元素時返回錯誤結(jié)果。2422 （7） template int BinarySearch1(Type a , const Type& x, int n) if(n0 & x=a0) int lef

13、t=0; int right=n-1; while (left right) int middle = (left+right+1)/2; if (x amiddle) right = middle; else left = middle; if (x = aleft) return left; return -1; 2522 （7） 不正確。與不正確。與(5)相比，數(shù)組段左、右游標(biāo)相比，數(shù)組段左、右游標(biāo)left和和right調(diào)整不正確，導(dǎo)致調(diào)整不正確，導(dǎo)致x=a0時陷入死循環(huán)。時陷入死循環(huán)。 如：序列如：序列2 3 4 5，x=2時，時， left=0,right=3,mid=2,xa2=4

14、,right=2 left=0,right=2,mid=1,xa1=3,right=1 left=0,right=1,mid=1,xa1=3,right=1 left=0,right=1,mid=1,xa1=3,right=1 陷入死循環(huán)陷入死循環(huán) 當(dāng)當(dāng)x=a1時仍會陷入死循環(huán)，但是只要有一個時仍會陷入死循環(huán)，但是只要有一個實例證明輸出不正確即可確認(rèn)算法錯誤。實例證明輸出不正確即可確認(rèn)算法錯誤。2623 改寫二分搜索算法 設(shè)a0:n-1是已排好序的數(shù)組。請改寫二分搜索算法，使得當(dāng)搜索元素x不在數(shù)組中時，返回小于x的最大元素位置i和大于x的最小元素位置j。當(dāng)搜索元素在數(shù)組中時，i和j相等，均為x

15、在數(shù)組中的位置。27二分搜索算法二分搜索算法template int BinarySearch(Type a , const Type& x, int left, int right) while (left=right) int mid = (left+right)/2; if (x = amid) return mid; if (x a2=2,left=3left=3,right=4,mid=3,xa3=4,right=2 left=3,right=2,while循環(huán)結(jié)束循環(huán)結(jié)束i=right=2; j=left=3 /輸出所求兩個位置輸出所求兩個位置return 0;2923 改寫二分搜

16、索算法解答：改寫二分搜索如下：template int BinarySearch(Type a ,const Type& x,int left,int right, int &i, int &j ) while (left=right) int mid = (left+right)/2; if (x = amid) i=j=mid; return 1; if (x aiai 時，交換兩者的位置。時，交換兩者的位置。這樣經(jīng)這樣經(jīng)k k次比較后有：次比較后有： aiaiai+kai+k, , 0ik-1.0ik-1.322-15 求最大元素和最小元素的最優(yōu)算法求最大元素和最小元素的最優(yōu)算法 分析與

17、解答：對于分析與解答：對于a0:n-1a0:n-1，數(shù)組，數(shù)組a a有有n n個元素。個元素。 (1)(1)當(dāng)當(dāng)n n為偶數(shù)時，為偶數(shù)時，. 然后，用然后，用k-1k-1次比較找出次比較找出a0:k-1a0:k-1中最大元素，用中最大元素，用k-1k-1次比較找出次比較找出ak:n-1ak:n-1中最小元素，即為我們所中最小元素，即為我們所求的最大元素和最小元素。所用比求的最大元素和最小元素。所用比較次數(shù)為較次數(shù)為: : k+(k-1)+(k-1)=3k-2=3n/2-2 k+(k-1)+(k-1)=3k-2=3n/2-2332-15 求最大元素和最小元素的最優(yōu)算法求最大元素和最小元素的最優(yōu)算

18、法對于對于a0:n-1a0:n-1，數(shù)組，數(shù)組a a有有n n個元素。個元素。(2)(2)當(dāng)當(dāng)n n為奇數(shù)時，設(shè)為奇數(shù)時，設(shè)n=2kn=2k1 1，先，先用對用對n n為偶數(shù)時的方法找出為偶數(shù)時的方法找出a0:n-2a0:n-2中的最大元素和最小元中的最大元素和最小元素。素。342-15 求最大元素和最小元素的最優(yōu)算法求最大元素和最小元素的最優(yōu)算法 對于對于a0:n-1a0:n-1，數(shù)組，數(shù)組a a有有n n個元素。個元素。 (2)(2)當(dāng)當(dāng)n n為奇數(shù)時，為奇數(shù)時，. 然后，將然后，將an-1an-1與當(dāng)前找出的最與當(dāng)前找出的最大元素和最小元素進行大元素和最小元素進行2 2次比較，次比較，即

19、可確定我們所求的最大元素和最即可確定我們所求的最大元素和最小元素。所用比較次數(shù)為小元素。所用比較次數(shù)為: : k+(k-1)+(k-1)+2=3k=3(n-1)/2 k+(k-1)+(k-1)+2=3k=3(n-1)/2 = =3n/23n/222352-15 求最大元素和最小元素的最優(yōu)算法求最大元素和最小元素的最優(yōu)算法template int Min_Max(Type a , int n, int min, int max) for (i=0; in; i+) si=i; /記錄元素下標(biāo)記錄元素下標(biāo) k = n/2; for (i=0; i ai+k) swap(ai , ai+k); sw

20、ap(si , si+k); 362-15 求最大元素和最小元素的最優(yōu)算法求最大元素和最小元素的最優(yōu)算法 min =MIN (a, 0, k-1); /獲取獲取a0ak-1中最小值的位置中最小值的位置 max=MAX(a, k, 2k-1); /獲取獲取aka2k-1中最大值的位置中最大值的位置 if(2*kamax) max=n-1; if (an-1amin) min=n-1; max= smax; /最大元素在原數(shù)組中的位置最大元素在原數(shù)組中的位置 min = smin; /最小元素在原數(shù)組中的位置最小元素在原數(shù)組中的位置 37作業(yè)中存在的問題 2-3 改寫二分搜索算法，改寫二分搜索算法，返回小于返回小于x的的最大元素位置最大元素位置i和大于和大于x的最小元素位置的最小元素位置j。當(dāng)找到與。當(dāng)找到與x同的元素時，同的元素時，i和和j相同，相同，均為均為x在數(shù)組中的位置。在數(shù)組中的位置。382-3 正確答案正確答案1 int BinarySearch(Type a , const Type& x, int lef