第2章作业答案2-3_2-15.ppt

第2章 递归与分治策略  作业 主定理的应用 1. T(n)=3T(n/7)+n k=3,m=7,d=1 有 kmd , T(n)=θ(nd) =θ(n) 2. T(n)=T(3n/7)+1 k=1,m=7/3,d=0,有 k=md , T(n)=θ(ndlogn)=θ(logn) 3. T(n)=16T(n/3)+n2 k=16,m=3,d=2,有 kmd , T(n)=θ(nlogmk) =θ(nlog316) 2－2判断7个二分搜索算法的正确性。 下面的7个算法与本章中的二分搜索算法BinarySearch略有不同。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。 二分搜索算法： templateclass Type int BinarySearch(Type a[ ], const Type x, int left, int right) { while (left=right){ int mid = (left+right)/2; if (x == a[mid]) return mid; if (x a[mid]) right = mid-1; else left = mid+1; } return -1; //未找到x } 2－2 （1） templateclass Type int BinarySearch1(Type a[ ], const Type x, int n) { int left=0; int right=n-1; while (left = right){ int middle = (left+right)/2; if (x == a[middle]) return middle; if (x a[middle]) left = middle; else right = middle; } return -1; } 2－2 （1） 不正确。与主教材中的算法Binary Search相比，数组段左、右游标left和right调整不正确，导致陷入死循环。 如：序列2 3 4 5，x=5时， left=0,right=3,mid=1,xa[1]=3,left=1 left=1,right=3,mid=2,xa[2]=4,left=2 left=2,right=3,mid=2,xa[2]=4,left=2 left=2,right=3,mid=2,xa[2]=4,left=2 陷入死循环 2－2 （1） 又如：序列2 3 4 5，x=1时 left=0,right=3,mid=1,xa[1]=3,right=1 left=0,right=1,mid=0,xa[0]=2, right=0 left=0,right=0,mid=0,xa[0]=2, right=0 left=0,right=0,mid=0,xa[0]=2, right=0 陷入死循环。 2－2 （2） templateclass Type int BinarySearch1(Type a[ ], const Type x, int n) { int left=0; int right=n-1; while (left right-1){ int middle = (left+right)/2; if (x a[middle]) right = middle; else left = middle; } if (x == a[left]) return left; return -1; } 2－2 （2） 不正确。与主教材中的算法Binary Search相比，数组段左、右游标left和right调整不正确，导致x=a[n-1]时返回错误结果。 如：序列2 3 4 5，x=5时， left=0,right=3,mid=1,xa[1]=3,left=1 left=1,right=3,mid=2,xa[2]=4,left=2 left=2,right-1=2,while循环结束 5==a[2]不为真 故return -1； 返回-1表示找不到x，这是一个错误的结论！ 2－2 （3） templateclass Type int BinarySearch1(Type a[ ], const Type x, int n)