作业答案PPT精品文档

1、1第2章 递归与分治策略 作业2主定理的应用 1. T(n)=3T(n/7)+n k=3,m=7,d=1 有 kmd , T(n)=(nlogmk) =(nlog316) 322判断判断7个二分搜索算法的正确性个二分搜索算法的正确性。 下面的下面的7个算法与本章中的二分搜索算法个算法与本章中的二分搜索算法BinarySearch略有不同。请判断这略有不同。请判断这7个算个算法的正确性。如果算法不正确，请说明产法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算生错误的原因。如果算法正确，请给出算法的正确性证明法的正确性证明。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相比，数组段左、右游标相比，数组段左、右游标left和和right调整不正确，导致陷入死循环。调整不正确，导致陷入死循环。 如：序列如：序列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 陷入死循环陷入死循环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 陷入死循环。陷入死循环。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循环结束循环结束 5=a2不为真不为真 故故return -1； 返回返回-1表示找不到表示找不到x，这是一个错误的结论！，这是一个错误的结论！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 陷入死循环陷入死循环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循环结束循环结束 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循环结束循环结束 7!=a3,return -1; 输出正确输出正确1822 （5） 正确。用几个特殊实例证明其正确性。正确。用几个特殊实例证明其正确性。 又如：序列又如：序列2 3 4 5，x=1时，时，x=a0不成立，不进入

10、不成立，不进入while循环循环且且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循环结束循环结束 4=a4,return 4; 输出正确输出正确,且有

11、重复元素且且有重复元素且x为重复元素为重复元素的值时，返回最右边该值所在下标。的值时，返回最右边该值所在下标。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结束结束 5=a3,return 3; 返回正确结果返回正确结果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循环结束循环结束 a5越界，越界，return -1，输出不正确。，输出不正确。 结论结论：与：与(5)相比，数组段左、右游标相比，数组段左、右游标left和和right调整不正确，导致有重复元素时返回错误结果。调整不正确，导致有重复元素时返回错误结果。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)相比，数组段左、右游标相比，数组段左、右游标left和和right调整不正确，导致调整不正确，导致x=a0时陷入死循环。时陷入死循环。 如：序列如：序列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 陷入死循环陷入死循环 当当x=a1时仍会陷入死循环，但是只要有一个时仍会陷入死循环，但是只要有一个实例证明输出不正确即可确认算法错误。实例证明输出不正确即可确认算法错误。2623 改写二分搜索算法 设a0:n-1是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相等，均为x

15、在数组中的位置。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循环结束循环结束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+kai时，交换两者的位置。时，交换两者的位置。这样经这样经k k次比较后有：次比较后有： aiai+k, aiai+k, 0ik-1.0ik-1.322-15 求最大元素和最小元素的最优算法求最大元素和最小元素的最优算法

17、分析与解答：对于分析与解答：对于a0:n-1a0:n-1，数组，数组a a有有n n个元素。个元素。 (1)(1)当当n n为偶数时，为偶数时，. 然后，用然后，用k-1k-1次比较找出次比较找出a0:k-1a0:k-1中最大元素，用中最大元素，用k-1k-1次比较找出次比较找出ak:n-1ak:n-1中最小元素，即为我们所中最小元素，即为我们所求的最大元素和最小元素。所用比求的最大元素和最小元素。所用比较次数为较次数为: : k+(k-1)+(k-1)=3k-2=3n/2-2 k+(k-1)+(k-1)=3k-2=3n/2-2332-15 求最大元素和最小元素的最优算法求最大元素和最小元素的

18、最优算法对于对于a0:n-1a0:n-1，数组，数组a a有有n n个元素。个元素。(2)(2)当当n n为奇数时，设为奇数时，设n=2kn=2k1 1，先，先用对用对n n为偶数时的方法找出为偶数时的方法找出a0:n-2a0:n-2中的最大元素和最小元中的最大元素和最小元素。素。342-15 求最大元素和最小元素的最优算法求最大元素和最小元素的最优算法 对于对于a0:n-1a0:n-1，数组，数组a a有有n n个元素。个元素。 (2)(2)当当n n为奇数时，为奇数时，. 然后，将然后，将an-1an-1与当前找出的最与当前找出的最大元素和最小元素进行大元素和最小元素进行2 2次比较，次比

19、较，即可确定我们所求的最大元素和最即可确定我们所求的最大元素和最小元素。所用比较次数为小元素。所用比较次数为: : k+(k-1)+(k-1)+2=3k=3(n-1)/2 k+(k-1)+(k-1)+2=3k=3(n-1)/2 = =3n/223n/22352-15 求最大元素和最小元素的最优算法求最大元素和最小元素的最优算法template int Min_Max(Type a , int n, int min, int max) for (i=0; in; i+) si=i; /记录元素下标记录元素下标 k = n/2; for (i=0; i ai+k) swap(ai , ai+k);

20、 swap(si , si+k); 362-15 求最大元素和最小元素的最优算法求最大元素和最小元素的最优算法 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; /最大元素在原数组中的位置最大元素在原数组中的位置 min = smin; /最小元素在原数组中的位置最小元素在原数组中的位置 37作业中存在的问题 2-3 改写二分搜索算法，改写二分搜索算法，返回小于返回小于x的的最大元素位置最大元素位置i和大于和大于x的最小元素位置的最小元素位置j。当找到与。当找到与x同的元素时，同的元素时，i和和j相同，相同，均为均为x在数组中的位置。在数组中的位置。382-3 正确答案正确答案1 int BinarySearch(Type a , const Type& x, int lef