欢迎来到天天文库
浏览记录
ID:27185847
大小:123.00 KB
页数:26页
时间:2018-12-01
《算法设计和分析习题答案及解析1_6章》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、.WORD完美.格式编辑.习题1图1.7七桥问题北区东区岛区南区1.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(LeonhardEuler,1707—1783)提出并解决了该问题。七桥问题是这样描述的:一个人是否能在一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次,图1.7是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来,并判断此问题是否有解。七桥问题属于一笔画问题。输入:一个起点输出:相同的点1,一次步行2,经过七座桥,且每次只经历过一次3,回到起点该问题无解:能一笔画的图
2、形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法1.r=m-n2.循环直到r=02.1 m=n2.2 n=r2.3 r=m-n3 输出m3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C++描述。//采用分治法//对数组先进行快速排序//在依次比较相邻的差#includeusingnamespacestd;intpartions(intb[],intlow,inth
3、igh){.技术资料.专业整理..WORD完美.格式编辑.intprvotkey=b[low];b[0]=b[low];while(low=prvotkey)--high;b[low]=b[high];while(low4、tions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high}}voidquicksort(intl[],intn){qsort(l,1,n);//第一个作为枢轴,从第一个排到第n个}intmain(){inta[11]={0,2,32,43,23,45,36,57,14,27,39};intvalue=0;//将最小差的值赋值给valuefor(intb=15、;b<11;b++)cout<6、ludeusingnamespacestd;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]a[i+2]){mid_value=a[i+1];cout<7、k;}}//forreturn0;}.技术资料.专业整理..WORD完美.格式编辑.5.编写程序,求n至少为多大时,n个“1”组成的整数能被2013整除。#includeusingnamespacestd;intmain(){doublevalue=0;for(intn=1;n<=10000;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<8、ludeusingnamespacestd;intmain(
4、tions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high}}voidquicksort(intl[],intn){qsort(l,1,n);//第一个作为枢轴,从第一个排到第n个}intmain(){inta[11]={0,2,32,43,23,45,36,57,14,27,39};intvalue=0;//将最小差的值赋值给valuefor(intb=1
5、;b<11;b++)cout<6、ludeusingnamespacestd;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]a[i+2]){mid_value=a[i+1];cout<7、k;}}//forreturn0;}.技术资料.专业整理..WORD完美.格式编辑.5.编写程序,求n至少为多大时,n个“1”组成的整数能被2013整除。#includeusingnamespacestd;intmain(){doublevalue=0;for(intn=1;n<=10000;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<8、ludeusingnamespacestd;intmain(
6、ludeusingnamespacestd;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]a[i+2]){mid_value=a[i+1];cout<7、k;}}//forreturn0;}.技术资料.专业整理..WORD完美.格式编辑.5.编写程序,求n至少为多大时,n个“1”组成的整数能被2013整除。#includeusingnamespacestd;intmain(){doublevalue=0;for(intn=1;n<=10000;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<8、ludeusingnamespacestd;intmain(
7、k;}}//forreturn0;}.技术资料.专业整理..WORD完美.格式编辑.5.编写程序,求n至少为多大时,n个“1”组成的整数能被2013整除。#includeusingnamespacestd;intmain(){doublevalue=0;for(intn=1;n<=10000;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<8、ludeusingnamespacestd;intmain(
8、ludeusingnamespacestd;intmain(
此文档下载收益归作者所有