算法设计与分析习题与实验题.docx

《算法设计与分析》习题

第一章 引 论

习题1-1 写一个通用方法用于判定给定数组是否已排好序。解答：

Algorithmcompare(a,n)Begin

J=1;

While(jnanda[j]=a[j+1])doj=j+1;Ifj=nthenreturntrue

Else

While(jnanda[j]=a[j+1])doj=j+1;

Ifj=nthenreturntrueelsereturnfalseendif

Endif

end

习题1-2 写一个算法交换两个变量的值不使用第三个变量。解答：x=x+y;y=x-y;x=x-y;

习题1-3已知m,n为自然数，其上限为k（由键盘输入，1=k=109）,找出满足条件(n2-mn-m2)2=1且使n2+m2达到最大的m、n。

解答：

m:=k;flag:=0;repeat

n:=m;

repeat

l:=n*n-m*n-m*n;

if(l*l=1)thenflag:=1elsen:=n-1;until(flag=1)or(n=0)

ifn=0thenm:=m-1until(flag=1)or(m=0);

第二章 基础知识

习题2-1 求下列函数的渐进表达式：

3n2+10n; n2/10+2n; 21+1/n; logn3; 10log3n。

解答： 3n2+10n=O（n2），n2/10+2n=O（2n），21+1/n=O（1），logn3=O（logn），10log3n=O（n）。

习题2-2 说明O(1)和O(2)的区别。

习题 2-3 照渐进阶从低到高的顺序排列以下表达式：n!，

4n2,logn,3n,20n,2,n2/3。

2解答：照渐进阶从低到高的顺序为：n!、3n、4n2、n3、20n、logn、2

2

习题2-4

假设某算法在输入规模为n时的计算时间为T(n)?3?2n。在某台计算机

上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？

若上述算法的计算时间改进为T(n)?n2，其余条件不变，则在新机器上用

t秒时间能解输入规模多大的问题？

若上述算法的计算时间进一步改进为T(n)?8,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？

解答：

（1）设新机器用同一算法在t 秒内能解输入规模为n 的问题。因此有

1

1t?3?2n?3?2n/64，解得n

1

1

?n?6。

（2）n2?64n2??n ?8n。

1 1

（3）由于T(n)?常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手

ABC公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n!的各算法，

若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？

解答：

n??100n。

n?2?100n2??n??10n。

100nn?3?100n3??3 ?4.64n

100n

n?!?100n!??n??n?log100?n?6.64。

习题2-6 对于下列各组函数f(n)和g(n)，确定f(n)?O(g(n))或

f(n)??(g(n))或f(n)??(g(n))，并简述理由。

f(n)?logn2;g(n)?logn?5。

nf(n)?logn2;g(n)? 。

n

f(n)?n;g(n)?log2n。

f(n)?nlogn?n;g(n)?logn。

（5）f(n)?10;g(n)?log10。

（6）f(n)?log2n;g(n)?logn。

（7）f(n)?2n;g(n)?100n2。

（8）f(n)?2n;g(n)?3n。

解答：

logn2??(logn?5)。

logn2?O( n)。

n??(log2n)。

nlogn?n??(logn)。

（5）10??(log10)。

（6