个人做的课后练习

书籍：算法设计与分析基础(第三版）

习题2.3

一. a. 250000 b. 2046 c. n-1 d. (n+4)(n-1)/2 e. (n-1)n/2*(1+(2n-1)/3) f. (pow(3,n+1)-3)/2 g. pow((n+1)n/2,2) h. 1-1/(n+1)

二. a. n的四次方 b. log（n） c. 2的n次方乘n d. n*n

三. 用第一种方法 加减运算：n*n+1次；乘法运算：0次；除法运算：n+1次 第二种方法 加减运算：2*n+2次；乘法运算：n+1次；除法运算：2次

四. a.该算法求的是 1~n的平方和 b.基本操作是：乘法和加法运算 c. 执行了n次 d. O（n） e. 可以直接使用公式得出答案：S=n*（n+1）*（2n+1）/6

五. a.该算法求的是数列中最大元素和最小元素的差 b.基本操作是：比较运算 c.执行了n次 d.O（n） e.可以不必连续两次判断。因为两种情况是互斥的，所以，下面的if可以改写成 else if。减少比较的次数增加效率。

六. a.判断这个矩阵是不是对称矩阵 b.基本操作是：比较运算 c.执行了 n（n-1）/2 次 d. O（n*n） e. 从定义出发，这个算法已经是比较次数最少的算法。所以不可能做到更好了。

八. 开关的总次数是： n+n/2+n/3+…+1 = n*log2（n+1） 证明如下： S(n)=1+1/2+1/3+1/4+…+1/n T(n)=log2(n+1) 显然当 n=1 时， S(n)=T(n)； S(n)-S(n-1)=1/n T(n)-T(n-1)=log2( (n+1)/n ) 所以只需要证明： 1/n < log2( (n+1)/n ) 既证明： 1 < n*log2( (n+1)/n ) 显然成立。

九. 1+2+3+…+n n+(n-1)+(n-2)+…+1 显然有 1+2+3…+n = ( (n+1)+(n+1)+…+(n+1) )/2 = (n+1)*n/2

十. 做一张逆序表，两表相加，每一个格子的元素都是 20。 20*100/2 = 1000 就是所求。

十一. a. O(n*n*n) b. 重要的缺陷：使用了多重循环，并且每层循环都有乘法和除法的运算。我暂时还搞不明白运行的机理是什么。

十二. 第n次的时候，共生成了 2*（n+1）*n+1个格子

十三. 9*1+90*2+900*3+1*4=2893