1、习题 11. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler，17071783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图 1.7 是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。七桥问题属于一笔画问题。输入：一个起点输出：相同的点1， 一次步行2， 经过七座桥，且每次只经历过一次3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。2在欧几里德提出的欧
2、几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法1.r=m-n2.循环直到 r=02.1 m=n2.2 n=r2.3 r=m-n3 输出 m 3设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和 C+描述。/采用分治法/对数组先进行快速排序/在依次比较相邻的差#include using namespace std;int partions(int b,int low,int high)图 1.7 七桥问题北区东区岛区南区int prvotkey=blow;b0=blow;while (low=prvotkey)-high
3、;blow=bhigh;while (lowusing namespace std;int main()int a=1,2,3,6,4,9,0;int mid_value=0;/将“既不是最大也不是最小的元素”的值赋值给它for(int i=0;i!=4;+i)if(ai+1aicoutusing namespace std;int main()double value=0;for(int n=1;nusing namespace std;int main ()double a,b;double arctan(double x);/声明a = 16.0*arctan(1/5.0);b = 4.
4、0*arctan(1/239);cout 1e-15)/定义精度范围 f = e/i;/f 是每次 r 需要叠加的方程r = (i%4=1)?r+f:r-f; e = e*sqr;/e 每次乘于 x 的平方 i+=2;/i 每次加 2 /whilereturn r;7. 圣经上说：神 6 天创造天地万有，第 7 日安歇。为什么是 6 天呢？任何一个自然数的因数中都有 1 和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此 6 是完美数。神 6 天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是
5、完美数#includeusing namespace std;int main()int value, k=1;cinvalue;for (int i = 2;i!=value;+i)while (value % i = 0 ) k+=i;/k 为该自然数所有因子之和value = value/ i;/forif(k=value)coutusing namespace std;extern const int n=6;/声明int main()int an=0,6,1,2,3,5;/初始化int mid=n/2;int num_max1=0,num_max2=0;for(int i=0;inu
6、m_max1)num_max1=ai;for(int j=n/2+1;jnum_max2)num_max2=aj;if(num_max1=num_max2)coutusing namespace std;void LeftReverse(char *a, int begin, int end)for(int i=0;iusing namespace std;int data100;/在 m 个数中输出 n 个排列数（nusing namespace std;void Findnum(int *a,int n)int low=0;int high=n-1;while(lowmid)high=mid-1;elselow=mid+1;int main()int a7=1,0,2,5,6,7,9;Findnum(a,7);return 0;时间复杂度为 O(log2n)。10. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。/先对序列进行快速排序/再进行一次遍历/输出众数的重复次数#include using namespace std;int partions(int b,int low,int high)int prvotkey=blow;
