gcd（m,n）=gcd（n,m）
并且这种交换处理只发生一次.
8.a.对于所有1≤m,n≤10的输入,Euclid算法最少要做几次除法?
（1次）
b.对于所有1≤m,n≤10的输入,Euclid算法最多要做几次除法?
（5次）
gcd（5,8）
习题1.2
1.（农夫过河）
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
//输出:
实根或者无解信息
Ifa≠0
D←b*b-4*a*c
IfD>0
temp←2*a
x1←（-b+sqrt（D））/temp
x2←（-b-sqrt（D））/temp
returnx1,x2
elseifD=0return–b/（2*a）
elsereturn“norealroots”
else //a=0
ifb≠0return–c/b
else //a=b=0
ifc=0return“norealnumbers”
elsereturn“norealroots”
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=1
whilen!
=0do{
Bin[i]=n%2;
n=（int）n/2;
i++;
}
whilei!
=0do{
printBin[i];
i--;
}
9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.（算法略）
对这个算法做尽可能多的改进.
算法MinDistance（A[0..n-1]）
//输入:
数组A[0..n-1]
//输出:
thesmallestdistancedbetweentwoofitselements
习题1.3
1.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.
a.应用该算法对列表”60,35,81,98,14,47”排序
b.该算法稳定吗?
c.该算法在位吗?
解:
a.该算法对列表”60,35,81,98,14,47”排序的过程如下所示:
b.该算法不稳定.比如对列表”2,2*”排序
c.该算法不在位.额外空间forSandCount[]
4.（古老的七桥问题）
第2章
习题2.1
7.对下列断言进行证明:
（如果是错误的,请举例）
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）foralln≥n0,wherec>0
则：
foralln≥n0
b.这个断言是正确的。
只需证明
。
设f（n）∈Θ（αg（n））,则有：
foralln>=n0,c>0
foralln>=n0,c1=cα>0
即：
f（n）∈Θ（g（n））
又设f（n）∈Θ（g（n））,则有：
foralln>=n0,c>0
foralln>=n0,c1=c/α>0
即：
f（n）∈Θ（αg（n））
8．证明本节定理对于下列符号也成立：
a.Ω符号
b.Θ符号
证明：
a。
weneedtoproofthatift1（n）∈Ω（g1（n））andt2（n）∈Ω（g2（n））,thent1（n）+t2（n）∈Ω（max{g1（n）,g2（n）}）。
由t1（n）∈Ω（g1（n）），
t1（n）≥c1g1（n） foralln>=n1,wherec1>0
由t2（n）∈Ω（g2（n）），
T2（n）≥c2g2（n） foralln>=n2,wherec2>0
那么，取c>=min{c1,c2},当n>=max{n1,n2}时：
t1（n）+t2（n）≥c1g1（n）+c2g2（n）
≥cg1（n）+cg2（n）≥c[g1（n）+g2（n）]
≥cmax{g1（n）,g2（n）}
所以以命题成立。
b.t1（n）+t2（n）∈Θ（
证明：
由大?
的定义知，必须确定常数c1、c2和n0，使得对于所有n>=n0，有：
由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时上述不等式成立。
证毕。
习题2.2
2.请用
的非正式定义来判断下列断言是真还是假。
a.n（n+1）/2∈O（n3）b.n（n+1）/2∈O（n2）
c.n（n+1）/2∈Θ（n3）d.n（n+1）/2∈Ω（n）
答：
c假，其它真。
5.按照下列函数的增长次数对它们进行排列（按照从低到高的顺序）
（n?
2）!
5lg（n+100）10,22n,0.001n4+3n3+1,ln2n,
，3n.
答：
习题2.3
1.计算下列求和表达式的值。
答：
3.考虑下面的算法。
a．该算法求的是什么？
b．它的基本操作是什么？
c．该基本操作执行了多少次？
d．该算法的效率类型是什么？
e．对该算法进行改进，或者设计一个更好的算法，然后指出它们的效率类型。
如果做不到这一点，请试着证明这是不可能做到的。
9.证明下面的公式：
可以使用数学归纳法，也可以像10岁的高斯一样，用洞察力来解决该问题。
这个小学生长大以后成为有史以来最伟大的数学家之一。
数学归纳法：
高斯的方法：
习题2.4
1.解下列递推关系（做a,b）
当n>1时
a.
解：
当n>1时
b.
解：
2.对于计算n!
的递归算法F（n），建立其递归调用次数的递推关系并求解。
解：
3.考虑下列递归算法，该算法用来计算前n个立方的和：
S（n）=13+23+…+n3。
算法S（n）
//输入：
正整数n
//输出：
前n个立方的和
ifn=1return1
elsereturnS（n-1）+n*n*n
a.建立该算法的基本操作次数的递推关系并求解
b.如果将这个算法和直截了当的非递归算法比，你做何评价？
解：
7.a.请基于公式2n=2n-1+2n-1，设计一个递归算法。
当n是任意非负整数的时候，该算法能够计算2n的值。
b.建立该算法所做的加法运算次数的递推关系并求解
c.为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。
d. 对于该问题的求解来说，这是一个好的算法吗？
解:
a.算法power（n）
//基于公式2n=2n-1+2n-1,计算2n
//输入:
非负整数n
//输出:
2n的值
Ifn=0return1
Elsereturnpower（n-1）+power（n-1）
c.
8.考虑下面的算法
算法Min1（A[0..n-1]）
//输入:
包含n个实数的数组A[0..n-1]
Ifn=1returnA[0]
Elsetemp←Min1（A[0..n-2]）
Iftemp≤A[n-1]returntemp
ElsereturnA[n-1]
a.该算法计算的是什么?
b.建立该算法所做的基本操作次数的递推关系并求解
解:
a.计算的给定数组的最小值
foralln>1
n=1
b.
9.考虑用于解决第8题问题的另一个算法,该算法递归地将数组分成两半.我们将它称为Min2（A[0..n-1]）
算法 Min（A[r..l]）
Ifl=rreturnA[l]
Elsetemp1←Min2（A[l..（l+r）/2]）
Temp2←Min2（A[l..（l+r）/2]+1..r）
Iftemp1≤temp2returntemp1
Elsereturntemp2
a.建立该算法所做的的操作次数的递推关系并求解
b.算法Min1和Min2哪个更快?
有其他更好的算法吗?
解:
a.
习题2.5
3.java的基本数据类型int和long的最大值分别是
当n最小为多少的时候，第n个斐波那契数能够使下面的类型溢出。
a.int类型 b.long类型
4.爬梯子假设每一步可以爬一个或两格梯子，爬一部n格梯子一共可以用几种的不同方法？
（例如，一部3格的梯子可以用三种不同的方法爬：
1-1-1，1-2和2-1）。
6.改进算法Fib，使它只需要?
（1）的额外空间。
7.证明等式：
答：
数学归纳法证明
习题2.6
1.考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数.
算法SortAnalysis（A[0..n-1]）
//input:
包含n个可排序元素的一个数组A[0..n-1]
//output:
所做的关键比较的总次数
count←0
fori←1ton-1do
v←A[i]
j←i-1
whilej>0andA[j]>vdo
count←count+1
A[j+1]←A[j]
j←j+1
A[j+1]←v
returncount
比较计数器是否插在了正确的位置?
如果不对,请改正.
解:
应改为:
算法SortAnalysis（A[0..n-1]）
//input:
包含n个可排序元素的一个数组A[0..n-1]
//output:
所做的关键比较的总次数
count←0
fori←1ton-1do
v←A[i]
j←i-1
whilej>0andA[j]>vdo
count←count+1
A[j+1]←A[j]
j←j+1
ifj>=0 count=count+1
A[j+1]←v
returncount
习题3.1
4.a.设计一个蛮力算法,对于给定的x0,计算下面多项式的值:
P（x）=anxn+an-1xn-1+…+a1x+a0
并确定该算法的最差效率类型.
b.如果你设计的算法属于Θ（n2）,请你为该算法设计一个线性的算法.
C.对于该问题来说,能不能设计一个比线性效率还要好的算法呢?
解:
a.AlgorithmsBruteForcePolynomialEvaluation（P[0..n],x）
//由高幂到低幂用蛮力法计算多项式p在给定点x的值
//输入:
P[0..n]是多项式按低幂到高幂的常系数,以及定值x
//输出:
多项式p在给定点x的值
p=0.0
fori=nto0do
power=1
forj=1toido
power=power*x
p=p+P[i]*power
returnp
算法效率分析:
基本操作:
两个数相乘,且M（n）仅依赖于多项式的阶n
b.thaabovealgorithmsisveryinefficient,becausewerecompute powersofxagainandagainasiftherewerenorelationshipamongthem.Infact,wecanmovefromthelowesttermtothehighestandcomputexibyusingxi-1.
AlgorithmsBetterBruteForcePolynomialEvaluation（P[0..n],x）
//由高幂到低幂用蛮力法计算多项式p在给定点x的值
//输入:
P[0..n]是多项式按低幂到高幂的常系数,以及定值x
//输出:
多项式p在给定点x的值
P=P[0]
power=1
fori←1tondo
power←power*x
p←p+P[i]*power
returnp
基本操作乘法运算总次数M（n）:
c.不行.因为计算任意一个多项式在任意点x的值,都必须处理它的n+1个系数.例如:
（x=1,p（x）=an+an-1+..+a1+a0,至少要做n次加法运算）
5.应用选择排序对序列E,X,A,M,P,L,E按照字母顺序排序.
6.选择排序是稳定的吗?
（不稳定）
7.用链表实现选择排序的话,能不能获得和数组版相同的Θ（n2）效率?
Yes.Bothoperation—findingthesmallestelementandswappingit–canbedoneasefficientlywiththelinkedlistaswithanarray.
8.应用冒泡排序对序列E,X,A,M,P,L,E按照字母顺序排序.
9.a.请证明,如果对列表比较一遍之后没有交换元素的位置,那么这个表已经排好序了,算法可以停止了.
b.结合所做的改进,为冒泡排序写一段伪代码.
c.请证明改进的算法最差效率也是平方级的.
Hints:
a.第i趟冒泡可以表示为:
如果没有发生交换位置,那么:
b.AlgorithmsBetterBubblesort（A[0..n-1]）
//用改进的冒泡算法对数组A[0..n-1]排序
//输入:
数组A[0..n-1]
//输出:
升序排列的数组A[0..n-1]
count←n-1 //进行比较的相邻元素对的数目
flag←true //交换标志
whileflagdo
flag←false
fori=0tocount-1do
ifA[i+1]swap（A[i],A[i+1]）
flag←true
count←count-1
c最差情况是数组是严格递减的,那么此时改进的冒泡排序会蜕化为原来的冒泡排序.
10.冒泡排序是稳定的吗?
（稳定）
习题3.2
1.对限位器版的顺序查找算法的比较次数:
a.在最差情况下
b.在平均情况下.假设成功查找的概率是p（0<=p<=1）
Hints:
a.Cworst（n）=n+1
b.在成功查找下,对于任意的I,第一次匹配发生在第i个位置的可能性是p/n,比较次数是i.在查找不成功时,比较次数是n+1,可能性是1-p.
6.给出一个长度为n的文本和长度为m的模式构成的实例,它是蛮力字符串匹配算法的一个最差输入.并指出,对于这样的输入需要做多少次字符比较运算.
Hints:
文本:
由n个0组成的文本
模式:
前m-1个是0,最后一个字符是1
比较次数:
m（n-m+1）
7.为蛮力字符匹配算法写一个伪代码,对于给定的模式,它能够返回给定的文本中所有匹配子串的数量.
AlgorithmsBFStringmatch（T[0..n-1],P[0..m-1]）
//蛮力字符匹配
//输入:
数组T[0..n-1]—长度为n的文本,数组P[0..m-1]—长度为m的模式
//输出:
在文本中匹配成功的子串数量
count←0
fori←0ton-mdo
j←0
whilejj←j+1
ifj=m
count←count+1
returncount
8.如果所要搜索的模式包含一些英语中较少见的字符,我们应该如何修改该蛮力算法来利用这个信息.
Hint:
每次都从这些少见字符开始比较,如果匹配,则向左边和右边进行其它字符的比较.
习题3.4
8.解释一下如何对排序问题应用穷举查找，并确定这种算法的效率类型。
答：
生成给定元素的一个排列，通过连续比较它们之间的元素，检查他们是否符合排序的要求。
如果符合就停止，否则重新生成新的排列。
最差情况生成排列的个数是n！
，每趟连续元素比较次数为n-1次。
所以效率类型为O（n！
（n-1））。
9.幻方一个n阶幻方是把从1到n2的整数填入一个n阶方阵，每个整数只出现一次，使得每一行，每一列，每一条主对角线的和都相等。
a.证明：
如果一个n阶幻方存在的话，所讨论的和一定等于n（n2+1）/2。
答：
令s为n阶幻方的每一行的和。
则把从1到n2的整数求和可得如下式子
由上式可得：
习题4.1
1.a.为一个分治算法编写伪代码,该算法求一个n个元素数组中最大元素的位置.
b.如果数组中的若干个元素都具有最大值,该算法的输出是怎样的呢?
c.建立该算法的键值比较次数的递推关系式并求解.
d.请拿该算法与解同样问题的蛮力算法做一个比较
解:
a.
AlgorithmsMaxIndex（A[l..r]）{
Input:
AportionofarrayA[0..n-1]betweenindiceslandr（l≤r）
Output:
TheindexofthelargestelementinA[l..r]
ifl=rreturnl
elsetemp1←MaxIndex（A[l..（l+r）/2]）
temp2←MaxIndex（A[（l+r）/2..r]）
ifA[temp1]≥A[temp2] returntemp1
elsereturntemp2
}
b.返回数组中位于最左边的最大元素的序号.
c.键值比较次数的递推关系式:
C（n）=C（n/2）+C（n/2）+1 forn>1
C
（1）=0
设n=2k，C（2k）=2C（2k-1）+1
=2[2C（2k-2）+1]+1=22C（2k-2）+2+1
=2[22C（2k-3）+1]+2+1=23C（2k-3）+22+2+1
=...
=2iC（2k-i）+2i-1+2i-2+...+2+1
=...
=2kC（2k-k）+2k-1+2k-2+...+2+1=2k－1=n-1
可以证明C（n）=n-1对所有n>1的情况都成立（n是偶数或奇数）
d.比较的次数相同，但蛮力算法不用递归调用。
2、a.为一个分治算法编写伪代码，该算法同时求出一个n元数组的最大元素和最小元素的值。
b.请拿该算法与解同样问题的蛮力算法做一个比较。
c.请拿该算法与解同样问题的蛮力算法做一个比较。
解答：
a.同时求出最大值和最小值，只需要将原数组一分为二，再使用相同的方法找出这两个部分中的最大值和最小值，然后经过比较就可以得到整个问题的最大值和最小值。
算法MaxMin（A[l..r],Max,Min）
//该算法利用分治技术得到数组A中的最大值和最小值
//输入：
数值数组A[l..r]
//输出：
最大值Max和最小值Min
if（r=l）Max←A[l]；Min←A[l];//只有一个元素时
else
ifr－l=1 //有两个
升级会员 