算法设计与分析第2版王红梅胡明习题答案.pdf

精品文档 习题胡明 -版)-王红梅 -算法设计与分 析(第 2 答案 1 习题 ）— 1783Leonhard Euler ，1707 1. 图论诞生于七桥问题。 出生于瑞士的伟大数学家欧拉 （提 出并解决了该问题。七桥问题是这样描述的： 北区 一个人是否能在 一次步行中穿越哥尼斯堡 （现 东区在叫加里宁格勒， 在波罗的海南岸） 城中全部 岛区 的七座桥后 回到起点，且每座桥只经过一次， 南区 是这条河以及河上的两个岛和七座桥的图 1.7 1.7 七桥问题 图草图。请将该问题的数据模型抽象出来，并判 断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 一次步行 1 ， 经过七座桥，且每次只经历过一次 2 ， 回到起点 3，该问题 无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个 奇点的图形。 ）用的不是除法而是减 最初的欧几里德算法 2 ．在欧几里德提出的欧几里德算法中（即 法。请 用伪代码描述这个版本的欧几里德算法 1.r=m -n r=0 循环直到 2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出 3 ．设计算法求数组中相差最小的两个元素 （称为最接近数） 的差。 要求分别给出伪代 3 ++描述。 C 码和 采用分治法 // // 对数组先进行快速排序 在依次比较相邻的差 // 精品文档． 精品文档 #include iostream using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (lowhigh) { while (lowhighb[high]=prvotkey) --high; b[low]=b[high]; while (lowhighb[low]=prvotkey) ++low; b[high]=b[low]; } b[low]=b[0]; return low; } void qsort(int l[],int low,int high) { int prvotloc; if(lowhigh) { prvotloc=partions(l,low,high); // 将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); // 递归调用排序 由 low 到 prvotloc-1 qsort(l,prvotloc+1,high); // 递归调用排序 由 prvotloc+1 到 high } } void quicksort(int l[],int n) { qsort(l,1,n); // 第一个作为枢轴 ，从第一个排到第 n 个 } int main() { int a[11]={0,2,32,43,23,45,36,57,14,27,39}; int value=0;// 将最小差的值赋值给 value for (int b=1;b11;b++) couta[b] ; 精品文档． 精品文档 coutendl; quicksort(a,11); for(int i=0;i!=9;++i) { if( (a[i+1]-a[i])=(a[i+2]-a[i+1]) )