算法设计与分析基础课后习题答案VIP免费

1 Program 算法设计与分析基础中文版答案 习题1.1 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n 都成立. Hint: 根据除法的定义不难证明:  如果d 整除u 和v , 那么d 一定能整除u±v;  如果d 整除u ,那么d 也能够整除u 的任何整数倍 ku . 对于任意一对正整数m,n,若 d 能整除m 和n,那么d 一定能整除n 和r=m mod n=m-qn；显然，若 d 能整除n 和r，也一定能整除m=r+qn 和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故 gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m0 temp←2*a x1←(-b+sqrt(D))/temp x2←(-b-sqrt(D))/temp return x1,x2 else if D=0 return –b/(2*a) else return “no real roots” else //a=0 if b≠0 return –c/b else //a=b=0 if c=0 return “no real numbers” else return “no real roots” 5. 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数 n 输出：正整数 n 相应的二进制数 第一步：用 n 除以 2，余数赋给 Ki(i=0,1,2...)，商赋给 n 第二步：如果 n=0，则到第三步，否则重复第一步 第三步：将 Ki 按照 i 从高到低的顺序输出 b.伪代码 算法 DectoBin(n) //将十进制整数 n 转换为二进制整数的算法 //输入：正整数 n //输出：该正整数相应的二进...