算法设计技巧及分析 沙特 递归分治部分答案

《算法设计技巧及分析 沙特 递归分治部分答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、5.33算法：EX5_33输入：已排序的数组A[1,…,n]，整数x输出：如果A中存在两个数，它们的和是x，则输出这两个数，若不存在，则输出nonefind(1,n)endEX5_33过程：find(s,t)//确定A[s,…,t]中是否存在两个数，它们的和是x，如果存在则输出这两个数，若不存在，则输出noneifs=tthenoutputnone;elseifsxthenfind(s,t-1);elseA[s]+A[t]find(s+1,t);end

2、ifendifendfind6.6EX6_6输入：输出：num=count(1,n,x);endEX6_6过程count(low,high,x)//ifhigh=lowthenifA[low]=xthenreturn1elsereturn0elsemid=(low+high)/2returncount(low,mid)+count(mid+1,high)endifendcount递归出口high

3、igh(T->left);right=high(T->right);return1+max{left,right}endifendhigh递归出口T->left==nullandT->right==nullthenreturn0?全局变量？6.52算法SECONDVALUE输入：正整数n和存储n个元素的数组a[1..n]输出：数组a的第二大元素(x1,x2)=secondvalue(1,n,a);returnx2;endSECONDVALUE过程secondvalue(low,high,a)//返回数对(x1,x2)其中x1>=x2ifhigh-low=0th

4、enreturn(a[low],-∞);//这个地方有修改elseifhigh-low=1thenifa[high]>=a[low]thenreturn(a[high],a[low]);elsereturn(a[low],a[high]);endifendifendifmid=(low+high)/2;(x1,x2)=secondvalue(low,mid,a);(y1,y2)=secondvalue(mid+1,high,a);returnx1,x2,y1,y2中最大和最小元素对;