《作业答案2-3-2-15》由会员分享，可在线阅读，更多相关《作业答案2-3-2-15（41页珍藏版）》请在金锄头文库上搜索。
1、1,第2章 递归与分治策略 作业,2,主定理的应用,1. T(n)=3T(n/7)+n k=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
2、a , const Type ,6,22 （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,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,
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 陷入死循环。,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
4、=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，这是一个错误的结论！,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 a
5、middle) right = middle; else left = middle;,12,22 （4）,template int BinarySearch1(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=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,mid=2,xa2
6、=4,left=2 陷入死循环,14,22 （5）,template int BinarySearch1(Type a , const Type ,15,22 （5）,正确。用几个特殊实例证明其正确性。 如：序列2 3 4 5，x=5时， left=0,right=3,mid=2,xa2=4,left=2 left=2,right=3,mid=3,x=a3=5,left=3 left=3,right=3,while循环结束 5=a3,return 3; 输出正确,16,22 （5）,正确。用几个特殊实例证明其正确性。 又如：序列2 3 4 5，x=2时， left=0,right=3,mid=
7、2,xa2=4,right=1 left=0,right=1,mid=1,xa1=3,right=0 left=0,right=0,while循环结束 2=a0,return 0; 输出正确,17,22 （5）,正确。用几个特殊实例证明其正确性。 如：序列2 3 4 5，x=7时， left=0,right=3,mid=2,xa2=4,left=2 left=2,right=3,mid=3,x=a3=5,left=3 left=3,right=3,while循环结束 7!=a3,return -1; 输出正确,18,22 （5）,正确。用几个特殊实例证明其正确性。 又如：序列2 3 4 5，x
8、=1时， x=a0不成立，不进入while循环 且x!=a0 故 return -1，表示在序列2 3 4 5中没有1 输出正确,19,22 （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; 输出正确,且有重复元素且x为重复元素的值时，返回最右边该值所在下标。,20,22 （
9、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=3 left=3,right=3, while结束 5=a3,return 3; 返回正确结果,22,22 （6）,如：序列2 3 4 5，x=2时， left=0,right=3,mid=2,xa2=4,right=1 left=0,right=1,mid=1,xa1=3,right=0 Left=right,while结束 2=a0,return 0; 返回正确结果,23
10、,22 （6）,如：序列2 2 4 4 4，x=4时， left=0,right=4,mid=2,x=a2=4,left=3 left=3,right=4,mid=4,x=a4=4,left=5 Leftright,while循环结束 a5越界，return -1，输出不正确。 结论：与(5)相比，数组段左、右游标left和right调整不正确，导致有重复元素时返回错误结果。,24,22 （7）,template int BinarySearch1(Type a , const Type ,25,22 （7）,不正确。与(5)相比，数组段左、右游标left和right调整不正确，导致x=a0时
11、陷入死循环。 如：序列2 3 4 5，x=2时， left=0,right=3,mid=2,xa2=4,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时仍会陷入死循环，但是只要有一个实例证明输出不正确即可确认算法错误。,26,23 改写二分搜索算法,设a0:n-1是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数
12、组中时，i和j相等，均为x在数组中的位置。,27,二分搜索算法,template int BinarySearch(Type a , const Type /未找到x ,28,23 改写二分搜索算法,例：序列0 1 2 4 5 ， x=3 left=0,right=4,mid=2,xa2=2,left=3 left=3,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 Binar
13、ySearch(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 求最大元素和最小元素的最优算法,分析与解答：对于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 求最大元素和最小元素
14、的最优算法,分析与解答：对于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个元素。 (2)当n为奇数时，设n=2k1，先用对n为偶数时的方法找出a0:n-2中的最大元素和最小元素。,34,2-15 求最大元素和最小元素的最优算法,对于a0:n-1，数组a有n个元素。 (2)当n为奇数时， 然后，将an-1与当前找出的最
15、大元素和最小元素进行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); 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
