06、【习题课】第1-3章.ppt

《06、【习题课】第1-3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1－3章习题作业1－5试用ADL语言编写一个算法，判断任一整数n是否为素数。考察知识点判断素数素数——大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。判断：对于指定的n，如果[2,n-1]内的整数都不能整除n，则n为素数。ADL语言写算法算法证明很难，可以使用边界条件和特殊数据，人工模拟算法执行过程。完成情况思想——基本正确，对素数定义的理解：1？算法——特殊情况处理：n1？算法输出；ADL语言的使用：运算符号：MOD(模)，DIV(除数)，/(除)；，（取整）；％？sqrt?fabs()?输入输出参数：设置返

2、回值；中间用“.”分隔；条件语句：ifthenelse；fori＝1tonstep1(i=i+1?)赋值语句：参考答案算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判断]WHILE(i≤n-1)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌正确性验证：假定n＝7，模拟执行过程，对i＝2，3，4，5，6时，分别判断(7modi)的取值是否

3、为0。改进：n-1？——n/2、n1/2n=ab,a≥2,b≤n/2,…a,…b,…n/2a≤n1/2,b≥n1/2,…a,…n1/2,…b…参考答案2算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1[n≤1？]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判断]WHILE(i≤n/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌作业1-8若A(n)=amnm+…+a1n+

4、a0是关于n的m次多项式，证明A(n)=O(nm)。设f(n)和g(n)是正整数集到正实数集的函数，称f(n)是O(g(n))当且仅当存在正常数C和n0，使得对任意的nn0，有f(n)Cg(n)。完成情况：令n0＝1，C＝am+…+a1+a0，amnm+…+a1n+a0Cnm注意：当ai0时，ainiainm不一定成立。证明：对于所有的n≥1，有：A(n)=i=0,…,maini≤i=0,…,m

5、ai

6、ni≤nmi=0,…,m

7、ai

8、ni-m≤nmi=0,…,m

9、ai

10、令C＝i=0,…,m

11、ai

12、，有A(n)≤Cnm所以

13、，A(n)=O(nm)。参考答案作业1－11证明对正整数n≥3，算法BS的元素比较次数T(n)≤5n/3-2。已知：0n=1T(n)=1n=2T(n/2)+T(n/2)+2n>2考察知识点：数学归纳法基础归纳：n=c(初值)时，命题是正确的；归纳步骤：如果n＝k－1时，命题成立，则n＝k时，命题也成立。完成情况：利用结论T(n)＝3n/2－2，需要注意前提条件——当n是2的幂时；由n=k反推n＝k-1时的情况。0n=1T(n)=1n=2T(n/2)+T(n/2)+2n>2n=3时，T(3)=T(1)+T(2)+2=3，5

14、3/3-2=3，命题成立。假设n<=k时命题成立，需证明n=k+1时成立。当k≥3时，有(k+1)>(k+1)/2≥(k+1)/2，即k≥(k+1)/2≥(k+1)/2所以：T((k+1)/2)≤5((k+1)/2)/3-2,(1)T((k+1)/2)≤5((k+1)/2)/3-2(2)T(k+1)=T((k+1)/2)+T((k+1)/2)+2≤[5((k+1)/2)/3-2]＋[5((k+1)/2)/3-2]+2=5((k+1)/2+(k+1)/2)/3-2//k＋1=

15、(k+1)/2+(k+1)/2=5(k+1)/3-2综上，命题得证。作业1－12给出算法BS的非递归算法，并说明算法最多需要多大的辅助空间。算法SM(A,n.max,min)SM1[初始化]max←min←A[1].SM2[比较]FORI=2TOnDO//求最大和最小元素(IFA[I]>maxTHENmax←A[I].IFA[I]

16、max←fmin←A[i].RETURN.）IFi=j1THEN（IFA[i]