算法设计与分析（第2版） 王红梅 胡明 习题答案

精心整理

动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就输了。请问，你是选择先行动还是后行动？为什么？

设最初两个数较大的为a,较小的为b，两个数的最大公约数为factor。

则最终能出现的数包括:factor,factor*2,factor*3,...,factor*(a/factor)=a.一共a/factor个。

如果a/factor是奇数，就选择先行动；否则就后行动。

习题2

1．如果T1(n)=O(f(n))，T2(n)=O(g(n))，解答下列问题： （1）证明加法定理：T1(n)＋T2(n)=max{O(f(n)),O(g(n))}； （2）证明乘法定理：T1(n)×T2(n)=O(f(n))×O(g(n))； （3）举例说明在什么情况下应用加法定理和乘法定理。 ,（1） （2） （3）比如在 for（f(n)） { for(g(n)) } 中应该用乘法定理 如果在“讲两个数组合并成一个数组时”，应当用加法定理 2．考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本语句执行了多少次？算法的时间复杂性是多少？ （2）intQ(intn) （1（）1 ）intStery(intn) 完成的是1-n的平方和 { { 基本语句：s+=i*i，执行了n次 intS=0; if(n==1) 时间复杂度O（n） return1; （2） for(inti=1;i<=n;i++) （2）完成的是n的平方 S=S+i*i; else 基本语句：returnQ(n-1)+2*n–1，执行了n次 returnS; returnQ(n-1)+2*n-1; 时间复杂度O（n） } } 3.分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。 （1）for(i=1;i<=n;i++) （2）m=0; （1） 基本语句2*i

（1）T(n)???4n?1（2）

?3T(n?1)n?11n?1? T(n)???2T(n3)?nn?1(1)intT(intn) {

if(n==1) return4;

elseif(n>1) return3*T(n-1);

精心整理

} (2)

intT(intn) {

if(n==1) return1;

elseif(n>1) return2*T(n/3)+n; }

5.求下列问题的平凡下界，并指出其下界是否紧密。 （1）求数组中的最大元素；

（2）判断邻接矩阵表示的无向图是不是完全图； （3）确定数组中的元素是否都是惟一的； （4）生成一个具有n个元素集合的所有子集 (1) Ω(n)紧密？ (2) Ω(n*n) (3) Ω(logn+n)（先进行快排，然后进行比较查找） (4) Ω(2^n) a

b usingnamespacestd; intmain() {

longdoubleresult=1; doublej=1; for(inti=1;i<=64;++i) {

j=j*2; result+=j; j++; }

cout<

习题3

1． 假设在文本\中查找模式\，写出分别采用BF算法和KMP算法的串匹配过 //BF算法

#include usingnamespacestd; intBF(charS[],charT[])

精心整理 {

intindex=0; inti=0,j=0;

while((S[i]!='\\0')&&(T[j]!='\\0')) {

if(S[i]==T[j]) {

i++; j++; } else{

++index; i=index; j=0; } }

if(T[j]=='\\0') returnindex+1; else

return0; }

intmain() {

chars1[19]=\ chars2[7]=\cout<

//KMP算法

#include usingnamespacestd; voidGetNext(charT[],intnext[])//求模式T的next值 {

inti,j,len; next[0]=-1;

for(j=1;T[j]!='\\0';j++)//依次求next[j] {

for(len=j-1;len>=1;len--)//相等子串的最大长度为j-1 {

for(i=0;i

next[j]=len;break; }

}//for if(len<1)

精心整理

next[j]=0;//其他情况，无相等子串 }//for }

intKMP(charS[],charT[])//求T在S中的序号 {

inti=0,j=0;

intnext[80];//假定模式最长为80个字符 GetNext(T,next);

while(S[i]!='\\0'&&T[j]!='\\0') {

if(S[i]==T[j]) {

i++;j++; }

else{

j=next[j]; if(j==-1){i++;j++;} } }

if(T[j]=='\\0')return(i-strlen(T)+1);//返回本趟匹配的开始位置 else return0; }

intmain() {

chars1[]=\ chars2[]=\cout<

2.分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4。 #include usingnamespacestd; intmain() {

intn;//分子 intm;//分母

intfactor;//最大公因子 intfactor1;

cout<<\输入一个真分数的分子与分母：\cin>>n>>m;

intr=m%n;//因为是真分数所以分母一定大于分子 factor1=m; factor=n; while(r!=0) {

factor1=factor;