作业答案2-3-2-15.ppt

《作业答案2-3-2-15.ppt》由会员分享，可在线阅读，更多相关《作业答案2-3-2-15.ppt（41页珍藏版）》请在三一办公上搜索。

1、1,第2章 递归与分治策略 作业,2,主定理的应用,1.T(n)=3T(n/7)+nk=3,m=7,d=1 有 kmd,T(n)=(nlogmk)=(nlog316),3,22判断7个二分搜索算法的正确性。,下面的7个算法与本章中的二分搜索算法BinarySearch略有不同。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。,4,二分搜索算法：,template int BinarySearch(Type a,const Type/未找到x,5,22（1）,template int BinarySearch1(Type a,const Ty

2、pe,6,22（1）,不正确。与主教材中的算法Binary Search相比，数组段左、右游标left和right调整不正确，导致陷入死循环。如：序列2 3 4 5，x=5时，left=0,right=3,mid=1,xa1=3,left=1left=1,right=3,mid=2,xa2=4,left=2left=2,right=3,mid=2,xa2=4,left=2left=2,right=3,mid=2,xa2=4,left=2陷入死循环,7,22（1）,又如：序列2 3 4 5，x=1时left=0,right=3,mid=1,xa1=3,right=1left=0,right=1,

3、mid=0,xa0=2,right=0left=0,right=0,mid=0,xa0=2,right=0left=0,right=0,mid=0,xa0=2,right=0陷入死循环。,8,22（2）,template int BinarySearch1(Type a,const Type,9,22（2）,不正确。与主教材中的算法Binary Search相比，数组段左、右游标left和right调整不正确，导致x=an-1时返回错误结果。如：序列2 3 4 5，x=5时，left=0,right=3,mid=1,xa1=3,left=1left=1,right=3,mid=2,xa2=4,

4、left=2left=2,right-1=2,while循环结束5=a2不为真故return-1；返回-1表示找不到x，这是一个错误的结论！,10,22（3）,template int BinarySearch1(Type a,const Type,11,22（3）,同（2），不正确。(3)中while(left+1!=right)等同于（2）的while(left=amiddle)left=middle;else right=middle;等同于（2）的if(x amiddle)right=middle;else left=middle;,12,22（4）,template int Bina

5、rySearch1(Type a,const Type,13,22（4）,不正确。与(5)相比，数组段左、右游标left和right调整不正确，导致陷入死循环。如：序列2 3 4 5，x=5时，left=0,right=3,mid=1,xa1=3,left=1left=1,right=3,mid=2,xa2=4,left=2left=2,right=3,mid=2,xa2=4,left=2left=2,right=3,mid=2,xa2=4,left=2 陷入死循环,14,22（5）,template int BinarySearch1(Type a,const Type,15,22（5）,正

6、确。用几个特殊实例证明其正确性。如：序列2 3 4 5，x=5时，left=0,right=3,mid=2,xa2=4,left=2left=2,right=3,mid=3,x=a3=5,left=3left=3,right=3,while循环结束5=a3,return 3;输出正确,16,22（5）,正确。用几个特殊实例证明其正确性。又如：序列2 3 4 5，x=2时，left=0,right=3,mid=2,xa2=4,right=1left=0,right=1,mid=1,xa1=3,right=0left=0,right=0,while循环结束2=a0,return 0;输出正确,17

7、,22（5）,正确。用几个特殊实例证明其正确性。如：序列2 3 4 5，x=7时，left=0,right=3,mid=2,xa2=4,left=2left=2,right=3,mid=3,x=a3=5,left=3left=3,right=3,while循环结束7!=a3,return-1;输出正确,18,22（5）,正确。用几个特殊实例证明其正确性。又如：序列2 3 4 5，x=1时，x=a0不成立，不进入while循环且x!=a0故 return-1，表示在序列2 3 4 5中没有1输出正确,19,22（5）,正确。用几个特殊实例证明其正确性。如：序列2 2 4 4 4，x=4时，lef

8、t=0,right=4,mid=2,x=a2=4,left=2left=2,right=4,mid=3,x=a3=4,left=3left=3,right=4,mid=4,x=a4=4,left=4left=4,right=4,while循环结束4=a4,return 4;输出正确,且有重复元素且x为重复元素的值时，返回最右边该值所在下标。,20,22（6）,template int BinarySearch1(Type a,const Type,21,22（6）,如：序列2 3 4 5，x=5时，left=0,right=3,mid=2,xa2=4,left=3left=3,right=3,

9、while结束5=a3,return 3;返回正确结果,22,22（6）,如：序列2 3 4 5，x=2时，left=0,right=3,mid=2,xa2=4,right=1left=0,right=1,mid=1,xa1=3,right=0 Left=right,while结束2=a0,return 0;返回正确结果,23,22（6）,如：序列2 2 4 4 4，x=4时，left=0,right=4,mid=2,x=a2=4,left=3left=3,right=4,mid=4,x=a4=4,left=5Leftright,while循环结束a5越界，return-1，输出不正确。结论：

10、与(5)相比，数组段左、右游标left和right调整不正确，导致有重复元素时返回错误结果。,24,22（7）,template int BinarySearch1(Type a,const Type,25,22（7）,不正确。与(5)相比，数组段左、右游标left和right调整不正确，导致x=a0时陷入死循环。如：序列2 3 4 5，x=2时，left=0,right=3,mid=2,xa2=4,right=2left=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,

11、xa1=3,right=1陷入死循环当x=a1时仍会陷入死循环，但是只要有一个实例证明输出不正确即可确认算法错误。,26,23 改写二分搜索算法,设a0:n-1是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相等，均为x在数组中的位置。,27,二分搜索算法,template int BinarySearch(Type a,const Type/未找到x,28,23 改写二分搜索算法,例：序列0 1 2 4 5，x=3left=0,right=4,mid=2,xa2=2,left=3left=3,

12、right=4,mid=3,xa3=4,right=2 left=3,right=2,while循环结束i=right=2;j=left=3/输出所求两个位置return 0;,29,23 改写二分搜索算法,解答：改写二分搜索如下：template int BinarySearch(Type a,const Type,30,2-15 求最大元素和最小元素的最优算法,给定数组a0:n-1,试设计一个算法，在最坏情况下用3n/2 2次比较找出a0:n-1中的最大元素和最小元素。提示：分别考虑有偶数个和奇数个元素的情况。以2 5 1 4，2 5 1 4 3为例,31,2-15 求最大元素和最小元素的

13、最优算法,分析与解答：对于a0:n-1，数组a有n个元素。(1)当n为偶数时，设n=2k，首先作k次比较ai:ai+k,0ik-1。当ai+kai时，交换两者的位置。这样经k次比较后有：aiai+k,0ik-1.,32,2-15 求最大元素和最小元素的最优算法,分析与解答：对于a0:n-1，数组a有n个元素。(1)当n为偶数时，.然后，用k-1次比较找出a0:k-1中最大元素，用k-1次比较找出ak:n-1中最小元素，即为我们所求的最大元素和最小元素。所用比较次数为:k+(k-1)+(k-1)=3k-2=3n/2-2,33,2-15 求最大元素和最小元素的最优算法,对于a0:n-1，数组a有n

14、个元素。(2)当n为奇数时，设n=2k1，先用对n为偶数时的方法找出a0:n-2中的最大元素和最小元素。,34,2-15 求最大元素和最小元素的最优算法,对于a0:n-1，数组a有n个元素。(2)当n为奇数时，.然后，将an-1与当前找出的最大元素和最小元素进行2次比较，即可确定我们所求的最大元素和最小元素。所用比较次数为:k+(k-1)+(k-1)+2=3k=3(n-1)/2=3n/22,35,2-15 求最大元素和最小元素的最优算法,template int Min_Max(Type a,int n,int min,int max)for(i=0;i ai+k)swap(ai,ai+k);

15、swap(si,si+k);,36,2-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在数组中的位置。,38,2-3 正确答案1,int BinarySearch(Type a,const Type,39,2-3 几种出错情况,while(left=right)出错情况：if(left=right)或while(leftright),40,2-3 几种出错情况,int BinarySearch(Type a,const Type&x,int left,int right，int&i,int&j)出错情况：int BinarySearch(Type a,const Type&x,int left,int right，int i,int j),41,2-3 正确答案2,int BinarySearch(Type a,const Type,