算法分析与设计重点课后习题答案.doc

《算法分析与设计重点课后习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题13．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。//采用分治法//对数组先进行快速排序//在依次比较相邻的差#includeusingnamespacestd;intpartions(intb[],intlow,inthigh){intprvotkey=b[low];b[0]=b[low];while(low=prvotkey)--high;b[low]=b[high];while(low

2、;b[high]=b[low];}b[low]=b[0];returnlow;}voidqsort(intl[],intlow,inthigh){intprvotloc;if(low

3、从第一个排到第n个}intmain(){inta[11]={0,2,32,43,23,45,36,57,14,27,39};intvalue=0;//将最小差的值赋值给valuefor(intb=1;b<11;b++)cout<

4、相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。#includeusingnamespacestd;intmain(){inta[]={1,2,3,6,4,9,0};intmid_value=0;//将“既不是最大也不是最小的元素”的值赋值给它for(inti=0;i!=4;++i){if(a[i+1]>a[i]&&a[i+1]

5、]>a[i+2]){mid_value=a[i+1];cout<usingnamespacestd;intmain(){doublevalue=0;for(intn=1;n<=10000;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<

6、{intS=0;for(inti=1;i<=n;i++)S=S+i*i;returnS;}（2）intQ(intn){if(n==1)return1;elsereturnQ(n-1)+2*n-1;}2．考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本语句执行了多少次？算法的时间复杂性是多少？（1）完成的是1-n的平方和基本语句：s+=i*i，执行了n次时间复杂度O（n）（2）（2）完成的是n的平方基本语句：returnQ(n-1)+2*n–1，执行了n次时间复杂度O（n）3.分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。（1）for(i

7、=1;i<=n;i++)if(2*i<=n)for(j=2*i;j<=n;j++)y=y+i*j；（2）m=0;for(i=1;i<=n;i++)for(j=1;j<=2*i;j++)m=m+1;（1）基本语句2*i1)retur