算法设计与分析练习题_1

《算法设计与分析练习题_1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析练习题1.仅使用Ο、Ω、Θ的定义，证明下列各式成立。221)5n–6n=Θ(n)n2)n!=Ο(n)2n2n3)2n2+nlogn=Θ(n2)n234)∑i=Θ(n)i=0n345)∑i=Θ(n)i=0nn2n26)+6*2n=Θ（n）36237)n+10n=Θ(n)2.下面哪些规则是正确的？为什么？1){f(n)=Ο(F(n))，g(n)=Ο(G(n))}→f(n)/g(n)=Ο(F(n)/G(n))2){f(n)=Ο(F(n))，g(n)=Ο(G(n))}→f(n)/g(n)=Ω(F(n)/G(n))3){f(n)=Ο(F(n))，g(n)=Ο(G(n))}→

2、f(n)/g(n)=Θ(F(n)/G(n))4){f(n)=Ω(F(n))，g(n)=Ω(G(n))}→f(n)/g(n)=Ω(F(n)/G(n))5){f(n)=Ω(F(n))，g(n)=Ω(G(n))}→f(n)/g(n)=Ο(F(n)/G(n))6){f(n)=Ω(F(n))，g(n)=Ω(G(n))}→f(n)/g(n)=Θ(F(n)/G(n))7){f(n)=Θ(F(n))，g(n)=Θ(G(n))}→f(n)/g(n)=Θ(F(n)/G(n))8){f(n)=Θ(F(n))，g(n)=Θ(G(n))}→f(n)/g(n)=Ω(F(n)/G(n))9){f(n)=Θ(

3、F(n))，g(n)=Θ(G(n))}→f(n)/g(n)=Ο(F(n)/G(n))3.某算法的计算时间可用下面的递推关系式描述。试采用迭代的方式求解该关系式，并用大写О表示解(要求给出详细的推导过程)。an=1，a为常数T(n)=2T(n/2)+c*nn>1，c为常数4.下面的算法是依据分治策略设计出来的，仔细阅读该算法回答下列问题(行号是为了说明问题而设置，它不属于算法本身)。行号VoidABC(intw[]，intn，int&p，int&q){1//w[0:n-1]中存放了n个整数。p,q是用于返回结果的两个变量2if(n<1)returnfalse；3if(n==1){

4、p=q=0；returntrue；}4ints；5if(n％2)｛p=q=0；s=1；｝6else{7if(w[0]>=w[1]){p=1；q=0；}8else{p=0；q=1；}9s=2；10｝；11for(i=s；iw[i+1]){if(w[i]>w[q])q=i；if(w[i+1]w[q])q=i+1；if(w[i]

5、同的n，讨论算法的比较次数。5.依据贪婪法求解问题的思想，编写一个求解下列问题的算法。设某币种有面额为25分、10分、5分、1分的四种硬币，1元钱等于100分。当希望找给顾客小于1元钱的零钱时，如何选择硬币种类才能够使得找给顾客的硬币数量最少。假设各种面额硬币的数量足够多。利用已经给出的部分代码，写出该问题的完整C语言算法。同时，假设需要找给顾客67分钱，请依据你的算法，给出找零钱的方案。main(){inta[3]={25,10,5,1}；//a[0:3]存放硬币的不同面额intb[4]；//b[0:3]存放对应硬币的数量(按面额由大到小)ints；//存放零钱总数inti；

6、//循环控制变量printf(“请输入零钱总数：”)；scanf(“%d”,&s)；//输入零钱总数，然后在下面补充必要代码，完成整个算法for(i=0；i<4；i++)printf(“面额为%d的硬币需要%d枚”，a[i]，b[i])；}//main6.试证明，对于函数f(n)和g(n)，若limg(n)/f(n)存在，则f(n)＝Ω(g(n))当且n→∞n→∞仅当存在确定的常数c，有limg(n)/f(n)≤c。7.证明：如果一个算法在平均情况下的计算时间复杂度为θ(g(n))，则该算法在最坏情况下所需的时间是Ω(g(n))。8.用贪婪法解装箱问题。装箱问题可简述如下：

7、设有编号为1，…，n的n种物品，体积分别为v1，v2，…，vn。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于1≤i≤n，有0