算法设计与分析第二版课后习题及解答
算法设计与分析基础课后练习答案
习题1.1
4.设计一个计算的算法,n是任意正整数。除了赋值和比较运算，该算法只能用到基本的四则运算操作。
数学二进制的算法
算法求 //输入：一个正整数n2//输出:。
step1:a1;  step2：若a*an 转step 3，否则输出a;  step3:aa+1转step 2;
5. a.用欧几里德算法求gcd(31415,14142)。
b. 用欧几里德算法求gcd(31415,14142)，比检查min{m,n}和gcd(m,n)间连续整数的算法快多少倍?请估算一下。
a. gcd31415, 14142  gcd14142, 3131  gcd3131, 1618 gcd1618, 1513  gcd1513, 105  gcd1513, 105  gcd105, 43 gcd43, 19  gcd19, 5  gcd5, 4  gcd4, 1  gcd1, 0  1.
b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。
连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1?14142 和 2?14142之间，所以欧几里德算法比此算法快1?14142/11 ≈1300 与2?14142/11 ≈ 2600 倍之间。
6.证明等式gcdm,ngcdn,m mod n对每一对正整数m,n都成立.
Hint:
根据除法的定义不难证明:
如果d整除u和v, 那么d一定能整除u±v;
如果d整除u，那么d也能够整除u的任何整数倍ku.
对于任意一对正整数m,n，若d能整除m和n，那么d一定能整除n和rm mod nm-qn；显然，若d能整除n和r，也一定能整除mr+qn和n。
数对m,n和n,r具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcdm,ngcdn,r
7.对于第一个数小于第二个数的一对数字，欧几里得算法将会如何处理?该算法在处理这种输入的过程中，上述情况最多会发生几次?
Hint:
对于任何形如0mn的一对数字,Euclid算法在第一次叠代时交换m和n, 即
gcdm,ngcdn,m
并且这种交换处理只发生一次.
8.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?1次b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次
除法?5次gcd5,8
习题1.2
1.农夫过河
P?农夫W?狼 G?山羊 C?白菜
2.过桥问题
1,2,5,10---分别代表4个人, f?手电筒
4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c0的实根，写出上述算法的伪代码可以假设sqrtx是求平方根的函数算法Quadratica,b,c
//求方程ax^2+bx+c0的实根的算法
//输入：实系数a,b,c
//输出：实根或者无解信息
If a≠0
D←b*b-4*a*c
If D0
temp←2*a
x1←-b+sqrtD/temp
x2←-b-sqrtD/temp
return x1,x2
else if D0 return ?b/2*a
el se return “no real roots”
else  //a0
if b≠0 return ?c/b
else  //ab0
if c0 return “no real numbers”
else return “no real roots”
5. 描述将十进制整数表达为二进制整数的标准算法
a.用文字描述
b.用伪代码描述
解答:
a.将十进制整数转换为二进制整数的算法
输入：一个正整数n
输出：正整数n相应的二进制数
第一步：用n除以2，余数赋给Kii0,1,2，商赋给n
第二步：如果n0，则到第三步，否则重复第一步
第三步：将Ki按照i从高到低的顺序输出
b.伪代码
算法 DectoBinn
//将十进制整数n转换为二进制整数的算法
//输入：正整数n
//输出：该正整数相应的二进制数，该数存放于数组Bin[1n]中i1
while n!0 do
Bin[i]n%2;
nintn/2;
i++;
while i!0 do
print Bin[i];

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。