算法设计与分析基础课后练习答案
习题1.1
4。设计一个计算的算法，n是任意正整数。除了赋值和比较运算，该算法只能用到基本的四则运算操作。
算法求
    //输入:一个正整数n2
    //输出：。
step1：a=1；
      step2:若a*a<n 转step 3，否则输出a；
      step3：a=a+1转step 2;
5. a．用欧几里德算法求gcd（31415,14142）。
b。 用欧几里德算法求gcd(31415,14142），比检查min｛m，n｝和gcd（m，n）间连续整数的算法快多少倍?请估算一下.
a。 gcd（31415, 14142) = gcd（14142， 3131） = gcd(3131, 1618) =gcd(1618, 1513) = gcd(1513, 105) = gcd(1513， 105） = gcd(105, 43） =gcd(43， 19） = gcd（19, 5) = gcd（5， 4) = gcd(4， 1） = gcd(1， 0） = 1.
b。有a可知计算gcd（31415，14142)欧几里德算法做了11次除法.
连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142 和 2·14142之间，所以欧几里德算法比此算法快1·14142/11 ≈ 1300 与 2·14142/11 ≈ 2600 倍之间.
6。证明等式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。

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