《算法设计与分析》王红梅课后习题答案清华大学出版社

liang183

习题1  
1.
图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现
在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，
图1.7是这条河以及河上的两个岛和七座桥的
草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。

   七桥问题属于一笔画问题。    输入：一个起点 输出：相同的点 1， 一次步行
2， 经过七座桥，且每次只经历过一次 3， 回到起点
该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。  
2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法  1.r=m-n
2.循环直到r=0 2.1  m=n 2.2   n=r 2.3  r=m-n 3 输出m

游客，如果您要查看本帖隐藏内容请回复

540477905

1234567890

Freddie

11111111111111

小鬼怖哭

1111111111

sgk

谢谢分享的算法分析!!!