6.6、设a[1…n]是一个由n个整数组成的数组，x为一整数。给出一个分治算法，找出x在 a**现的频度，即x在a**现的次数。你的算法的时间复杂度是什么？
输入：整数数组a[1…n]，整数x
输出：x在数组a[1…n]**现的频度。
frequence(a,1,h,x)
过程 frequence (a,low,high,x)
1. if high – low = 0
2. if a[low] =x return 1
3. else return 0;
4. end if
5. if high – low > 0
6. mid ← low+high)/2
7. return frequence(a,low,mid,x)+frequence(a,low+1,high,x)
8. end if
t(n)=o(n)
6.16、考虑以下mergesort的修改算法。我们将算法应用到输入数组a[1…n]上并不断递归调用，直到子问题的规模变得相对很小，即m或是小于m。
此时转向insertsor， 并将其运用到小的那部分，因此修改算法的第一个检验条件将变为。
if (high – low + 1 <=m) then insertsort(a[low...high])
在修改算法的运行时间仍不变的前提下，用n来表示m的最大值因是多少？为简单起见，可以假定n是2的幂。
输入：待排序数组a[low,..high]
输出：a[low…high]按非降序排列。
mergesort(a[low…high])
过程 mergesort(a, low,high)
low2. if (high – low + 1 <=m) then insertsort(a,low,high)
3. else
4. mid← (low+high)/2
5. mergesort(a, low, mid)
6. mergesort(a, mid+1, high)
7. merge(a, low, mid, high)
8. end if
9. end if
m<=2log n +1
6.38、解释当输入已按降序排列时算法quicksort的行为，可以假定输入元素是互不相同的。
算法quicksort是这样的：
1、设置两个变量start、end，排序开始的时候：start=1，end=n；
2、以第一个数组元素作为关键数据，赋值给pivot，即 pivot=arry[1]；
3、从end开始向前搜索，即由后开始向前搜索（end--）找到第一个小于pivot的值 arry[end]，并与arry[start]交换，即swat(arry,start,end)；
4、从start开始向后搜索，即由前开始向后搜索（start++）找到第一个大于pivot 的arry[start]，与arry[end]交换，即swat(arry,start,end);
5、重复第步，直到 start==end，这个时候arry[start]=arry[end]=pivot， 而pivot的位置就是其在整个数组中正确的位置；
6、通过递归，将问题规模不断分解。将pivot两边分成两个数组继续求新的pivot， 最后解出问题。
但是当输入已按降序排列时，假定输入元素有n个且互不相同。那么第一次执行第5步时，arry[1]和arry[n]交换。然后通过递归，出现arry[2]和arry[n-1]交换arry[3]和arry[n-2]交换。
如果n是偶数，最后一次交换的是arry[n/2]和arry[n/2 +1]；如果n是奇数，最后一次交换的是arry[（n-1）/2]和arry[（n+1）/2 ]。
算法设计与分析第四五章作业答案
第四章。4 1证明 归纳法证明定理结论正确。记 d v,w 是由 v到达某一可到达结点 w w v 的最短路径长度。若 d v,w 1,则显然这样的所有 w都将被访问。假设对所有 d v,w r 的结点都可被访问。则当 d v,w r 1时有 设 w是 v中 d v,w r 1的一个结点设 u是从 ...
算法与分析平时作业
1 给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。a int binarysearch type a,const type x,int l,int r return 1 答 正确。b int binarysearch type a,const type x,int l,int r...
数值分析与算法作业
第七章上机题作业。1 解 由于步长h要改变，故将其设为变量，则编程实现romberg求积算法7.1的程序为 romberg 使用romberg积分算法求积分值。function i,n,err romberg fun,a,b,h,ep fun是被积函数，a,b是积分下 上限，h是步长，ep是误差精度...