习题1.15..证明等式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<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if 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//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the ith element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty.(“lazy deletion”)习题2.11欧几里得算法的时间复杂度欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式gcd(a, b) = gcd(b, a mod b)其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b的余数. 算法如下:输入: 两个整数a, b输出: a和b的最大公约数function gcd(a, b:integer):integer;if b=0 return a;else return gcd(b, a mod b);end function欧几里得算法是最古老而经典的算法, 理解和掌握这一算法并不难, 但要分析它的时间复杂度却并不容易. 我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论), 我们只考虑这样的问题: 欧几里得算法在最坏情况下所需的模运算次数和输入的a 和b 的大小有怎样的关系?我们不妨设a>b>=1(若a<b 我们只需多做一次模运算, 若b=0或a=b 模运算的次数分别为0和1), 构造数列{un}: u0=a, u1=b, uk=uk-2 mod uk-1(k>=2), 显然, 若算法需要n 次模运算, 则有un=gcd(a, b), un+1=0. 我们比较数列{un}和菲波那契数列{Fn}, F0=1<=un, F1=1<=un-1, 又因为由uk mod uk+1=uk+2, 可得uk>=uk+1+uk+2, 由数学归纳法容易得到uk>=Fn-k, 于是得到a=u0>=Fn, b=u0>=Fn-1. 也就是说如果欧几里得算法需要做n 次模运算, 则b 必定不小于Fn-1. 换句话说, 若 b<Fn-1, 则算法所需模运算的次数必定小于n. 根据菲波那契数列的性质, 有Fn-1>(1.618)n/sqrt(5), 即b>(1.618)n/sqrt(5), 所以模运算的次数为O(lgb)---以b 为底数 = O(lg(2)b)---以2为底数，输入规模也可以看作是b 的bit 位数。
习题2.27.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。
它指出如果t(n)的增长率小于或等于g(n)的增长率，那么 g(n)的增长率大于或等于t(n)的增长率由 t(n)≤c ·g(n) for all n ≥n0, where c>0则：)()()1(n g n t c ≤ for all n ≥n0b. 这个断言是正确的。
只需证明))(())(()),(())((n g n g n g n g ααΘ⊆ΘΘ⊆Θ。
设f(n)∈Θ(αg(n)),则有：)()(n g c n f α≤ for all n>=n0, c>0 )()(1n g c n f ≤ for all n>=n0, c1=c α>0即：f(n)∈Θ(g(n))又设f(n)∈Θ(g(n)),则有：)()(n cg n f ≤ for all n>=n0,c>0)()()(1n g c n g cn f ααα=≤for all n>=n0,c1=c/α>0即：f(n)∈Θ(αg(n))8．证明本节定理对于下列符号也成立： a.Ω符号 b.Θ符号 证明：a 。
we need to proof that if t1(n)∈Ω(g1(n)) and t2(n)∈Ω(g2(n)), then t1(n)+ t2(n)∈Ω(max{g1(n), g2(n)})。
由 t1(n)∈Ω(g1(n))，t1(n)≥c1g1(n) for all n>=n1, where c1>0 由 t2(n)∈Ω(g2(n))，T2(n)≥c2g2(n) for all n>=n2, where c2>0 那么，取c>=min{c1,c2},当n>=max{n1,n2}时：t1(n)+ t2(n)≥c1g1(n)+ c2g2(n)≥c g1(n)+c g2(n)≥c[g1(n)+ g2(n)]≥cmax{ g1(n), g2(n)}所以以命题成立。
b. t1(n)+t2(n) ∈Θ()))(2),(1max(ngng证明：由大Ⓗ的定义知，必须确定常数c1、c2和n0，使得对于所有n>=n0，有：))(2),(1max()(2)(1))(2),(1max((1ngngntntngngc≤+≤由t1(n)∈Θ(g1(n))知，存在非负整数a1,a2和n1使：a1*g1(n)<=t1(n)<=a2*g1(n)-----(1)由t2(n)∈Θ(g2(n))知，存在非负整数b1,b2和n2使：b1*g2(n)<=t2(n)<=b2*g2(n)-----(2)(1)+(2):a1*g1(n)+ b1*g2(n)<=t1(n)+t2(n) <= a2*g1(n)+ b2*g2(n)令c1=min(a1,b1),c2=max(a2,b2)，则C1*(g1+g2)<= t1(n)+t2(n) <=c2(g1+g2)-----(3)不失一般性假设max(g1(n),g2(n))=g1(n).显然，g1(n)+g2(n)<2g1(n)，即g1+g2<2max(g1,g2)又g2(n)>0，g1(n)+g2(n)>g1(n),即g1+g2>max(g1,g2)。
则（3）式转换为：C1*max(g1,g2) <= t1(n)+t2(n) <=c2*2max(g1,g2)所以当c1＝min(a1,b1),c2＝2c2=2max(c1,c2)，n0＝max(n1,n2)时，当n>=n0时上述不等式成立。