《算法设计与分析(第2版)-王红梅-胡明-习题答案..docx》由会员分享，可在线阅读，更多相关《算法设计与分析(第2版)-王红梅-胡明-习题答案..docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与分析(第2版)-王红梅-胡明-习题答案. 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，17071783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫 加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的
2、点都是偶点。另一类是只有二个奇点的图形。 2在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 图 七桥问题 南区 3设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C+描述。 编写程序，求n至少为多大时，n个“1”组成的整数能被2022整除。 #include using namespace std; int main() double value=0; for(int n=1;nvalue; for (int i = 2;i!=value;+i
3、) while (value % i = 0 ) k+=i;有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟：甲，乙过桥且甲回来 第二趟：甲，丙过桥且甲回来 第一趟：甲，丁过桥 一共用时19
4、小时 9欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就输了。请问，你是选择先行动还是后行动为什么 设最初两个数较大的为a, 较小的为b，两个数的最大公约数为factor。 则最终能出现的数包括: factor, factor*2, factor*3, ., factor*(a/factor)=a. 一共a/factor个。如果a/factor 是奇数，就选择先行动；否则就后行动。 习题2 1如果T
5、1(n)=O(f (n)，T2(n)=O(g(n)，解答下列问题： （1）证明加法定理：T1(n)T2(n)=maxO(f (n), O(g(n)； （2）证明乘法定理：T1(n)T2(n)=O(f (n)O(g(n)； （3）举例说明在什么情况下应用加法定理和乘法定理。 ,（1） （2） （3）比如在 for（f(n)） for(g(n) 中应该用乘法定理 如果在“讲两个数组合并成一个数组时”，应当用加法定理 2考虑下面的算法，回答下列问题：算法完成什么功能算法的基本语句是什么基本语句执行了多少次算法的时间复杂性是多少 （1） 完成的是1-n 的平方和 基本语句：s+=i*i ，执行了n 次
6、 时间复杂度O （n ） （2） （2）完成的是n 的平方 基本语句：return Q(n-1) + 2 * n 1，执行了n 次 时间复杂度O （n ） 3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。 （1） 基本语句2*i-=1 )1(314 )(n n T n n T （2）? ?+=1)3(211)(n n n T n n T （1）int Stery(int n) int S = 0; for (int i = 1; i 1) return 3*T(n-1); (2) int T(int n) if(n=1) return 1; else if(n1) retur
7、n 2*T(n/3)+n; 5. 求下列问题的平凡下界，并指出其下界是否紧密。（1）求数组中的最大元素； （2）判断邻接矩阵表示的无向图是不是完全图； （3）确定数组中的元素是否都是惟一的； （4）生成一个具有n个元素集合的所有子集 (1)(n) 紧密 (2)(n*n) (3)(logn+n)（先进行快排，然后进行比较查找） (4)(2n) 7画出在三个数a , b , c 中求中值问题的判定树。 8国际象棋是很久以前由一个印度人Shashi 发明的，当他把该发明献给国王时，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi 要求以这种方式给他一些粮食：棋盘的第1个方格内只放1粒
8、麦粒，第2格2粒，第3格4粒，第4格8粒，以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢 #include using namespace std; int main() long double result=1; double j=1; for(int i=1;i=64;+i) j=j*2; result+=j; j+; bc C coutresultendl; return 0; 习题3 1假设在文本ababcabccabccacbab中查找模式abccac，写出分别采用BF算法和KMP 算法的串匹配过 式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/
9、8化简为3/4。 #include using namespace std; int main() int n;数字游戏。把数字1,2,9这9个数字填入以下含有加、减、乘、除的四则运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字1不能出现在乘和除的一位数中（即排除运算式中一位数为1的平凡情形）。 = 0 5. 设计算法求解a n mod m，其中a、n和m均为大于1的整数。（提示：为了避免a n 超出int型的表示范围，应该每做一次乘法之后对n取模） #include using namespace std; int square(int x) return x*x; 设计
10、算法，在数组rn中删除所有元素值为x的元素，要求时间复杂性为O(n)，空间复杂性为O(1)。 7.设计算法，在数组rn中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。 #include using namespace std; void deletere(int a,int N) int b100=0; int i,k; k=0; static int j=0; for(i=0;iN;i+) bai+; for(i=0;i100;i+) if(bi!=0) if(bi=2) k+; aj=i; j+; for(i=0;iN-k;i+) cout int main()
11、int a=1,2,1,3,2,4; deletere(a,6); return 0; 设表A =a 1, a 2, , a n ，将A 拆成B 和C 两个表，使A 中值大于等于0的元素存入表B ，值小于0的元素存入表C ，要求表B 和C 不另外设置存储空间而利用表A 的空间。 荷兰国旗问题。要求重新排列一个由字符R , W , B （R 代表红色，W 代表白色，B 代表兰色，这都是荷兰国旗的颜色）构成的数组，使得所有的R 都排在最前面，W 排在其次，B 排在最后。为荷兰国旗问题设计一个算法，其时间性能是O (n )。 设最近对问题以k 维空间的形式出现，k 维空间的两个点p 1=(x 1,
12、x 2, , x k )和p 2=(y 1, y 2, , y k )的欧几里德距离定义为：=k i i i -x y p p d 1 2 21) (),(。对k 维空间的最近对问题设计 蛮力算法，并分析其时间性能。 11设计蛮力算法求解小规模的线性规划问题。假设约束条件为：（1）x +y 4；（2）x +3y 6；（3）x 0且y 0；使目标函数3x +5y 取得极大值。 #include using namespace std; int main() int x,y,x0,y0; int summax=0,temp=0; for(x0=0;x0=4;+x0) for(y0=0;(x0+y0=4)&(x0+3*y0=6);+y0) temp=3*x0+5*y0;