算法设计与分析第五章算法设计与分析第五章.doc

第五章 作业答案 1、 伪代码：假设查找范围是有序的，ab 1. low=1；high=n； //设置初始查找区间 2. 测试查找区间［low，high］是否存在，若不存在，则查找失败； 否则 3. 取中间点mid=(low+high)/2; 比较a，b与r[mid]，有以下三种情况： 3.1 若ar[mid]，则high=mid-1；查找在左半区进行，转2； 3.2 若br[mid]，则low=mid+1；查找在右半区进行，转2； 3.3 若ar[mid]并且br[mid]，则在左半区对a用折半查找找到对应的r[i]=ar[i-1]a，在右半区对b用折半查找r[j]=br[j+1]b； 4. r[i]到r[j]之间的元素即为问题的解 参考代码： #includeiostream.h int i=0; int j=0;//存储a-b的所有元素的起始下标和终止下标 int finda(int s[],int begin,int end,int a)//查找边界为a的元素 { if(begin==end)return begin; else { int m=(begin+end)/2; if(s[m]==a)return m; else if(s[m]a)return finda(s,begin,m,a); else return finda(s,m+1,end,a); } } int findb(int s[],int begin,int end,int b)//查找边界为b的元素 { if(begin==end){ if(s[begin]b) return begin-1; else return begin; } else { int m=(begin+end)/2; if(s[m]==b)return m; else if(s[m]b)return findb(s,m+1,end,b); else return findb(s,begin,m,b); } } void find(int s[],int begin,int end,int a,int b)//缩小a-b的查找范围 { if(begin==end){ if(s[begin]=a)i=begin; else if(s[begin]=b)j=begin; } else { int m=(begin+end)/2; if(s[m]a) find(s,m+1,end,a,b); else if(s[m]b)find(s,begin,m,a,b); else { i=finda(s,begin,m,a); j=findb(s,m+1,end,b); } } } void main() { int s[]={1,2,5,8,11,24,31,40}; int a=2; int b=30; find(s,0,7,a,b); coutiendsjendl; } 4、 参考代码：根据程序运行结果显示使用两种方法生成的堆序列不一定一样 #includeiostream.h const int N=8; void SiftHeap(int r[],int k,int n) { int i=k,j=2*i; int temp; while(j=n) { if(jnr[j]r[j+1])j++; if(r[i]r[j])break; else { temp=r[i]; r[i]=r[j]; r[j]=temp; i=j;j=2*i; } } } void InsertHeap(int r[],int k) { int i=k,j; int temp; while(i!=1) { j=i/2; if(r[i]r[j])break; else{ temp=r[i]; r[i]=r[j]; r[j]=temp; i=j; } } } void main() { int s[N+1],s1[N+1]; //输入s和s1 for(int i=1;i=N;i++){cins[i];s1[i]=s[i];} //利用筛选法生成堆 for(i=N;i=1;i--)SiftHeap(s,i,N); //利用插入法生成堆 for(i=1;i=N;i++)InsertHeap(s1,i); //输出s和s1 for(i=1;i=N;i++) couts[i]endss1[i]endl; }