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

第一章1-3. 最大公约数为 1。快 1414 倍。主要考虑循环次数，程序1-2 的 while 循环体做了 10 次，程序 1-3 的 while 循环体做了 14141 次（14142-2循环）若考虑其他语句，则没有这么多，可能就601 倍。第二章2-8.（1）画线语句的执行次数为log n 。(log)n 。划线语句的执行次数应该理解为一格整体。（2）画线语句的执行次数为111(1)(2)16jniijkn nn。3()n。（3）画线语句的执行次数为n 。()n 。（4）当 n 为奇数时画线语句的执行次数为(1)(3)4nn，当 n 为偶数时画线语句的执行次数为2(2)4n。2()n。2-10. （1） 当1n时，225825nnn ，所以，可选5c，01n。对于0nn ，22( )5825f nnnn ，所以，22582()nnn。（2）当8n时，2222582524nnnnn ，所以，可选4c， 08n。对于0nn ，22( )5824f nnnn ，所以，22582()nnn。（3）由（1）、（2）可知，取14c， 25c， 08n，当0nn 时，有22212582c nnnc n ，所以22582()nnn。2-11. (1) 当3n时，3loglognnn，所以( )20log21f nnnn ，3( )log2g nnnn。可选212c， 03n。对于0nn ， ( )( )f ncg n ，即()( ())fngn。注意：是 f(n)和 g (n)的关系。（2） 当4n时，2loglognnn，所以22( )/ logf nnnn ，22( )logg nnnn 。可选1c，04n。对于0nn ，2( )( )f nncg n ，即( )(( ))f ng n。（3）因为loglog(log)( )(log)nnf nnn，( )/ loglog 2ng nnnn。当4n时，log(log)( )nf nnn， ( )log 2ng nnn 。所以，可选1c， 04n，对于0nn ， ( )( )f ncg n ，即( )(( ))f ng n。第二章2-17. 证明：设2in，则login 。当2n时，22 logT nnn 。所以，2logT nnn 。第五章5-4. SolutionType DandC1(int left,int right) { while(!Small(left,right)&&leftP[m]) left=m+1; else return S(P) } } 5-7. template int SortableList::BSearch(const T&x,int left,int right) const { if (left<=right) { int m=(right+left)/3; if (xl[m]) return BSearch(x,m+1,right); else return m; } return -1; } 第五章9．证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为log n ，至多为 log1n。在不成功搜索的情况下，关键...