算法设计与分析C 语言描述(陈慧南版)课后答案.doc

.第一章1-3. 最大公约数为1。快1414倍。主要考虑循环次数，程序1-2的while循环体做了10次，程序1-3的while循环体做了14141次（14142-2循环）若考虑其他语句，则没有这么多，可能就601倍。第二章2-8.（1）画线语句的执行次数为。划线语句的执行次数应该理解为一格整体。（2）画线语句的执行次数为 。（3）画线语句的执行次数为 。（4）当n为奇数时画线语句的执行次数为 ，当n为偶数时画线语句的执行次数为 。 2-10.（1） 当 时，所以，可选 ，。对于，所以，。（2） 当 时，所以，可选 ，。对于，所以，。（3） 由（1）、（2）可知，取，当时，有，所以。2-11. (1) 当时，所以，。可选 ，。对于，即。注意：是f(n)和g(n)的关系。（2） 当 时，所以 ，。可选 ，。对于 ，即 。（3）因为 ，。当 时，。所以，可选 ，对于，即 。第二章2-17. 证明：设，则 。