06、【習(xí)題課】第1-3章.ppt

《06、【習(xí)題課】第1-3章.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第1－3章習(xí)題作業(yè)1－5試用ADL語言編寫一個(gè)算法，判斷任一整數(shù)n是否為素?cái)?shù)?？疾熘R(shí)點(diǎn)判斷素?cái)?shù)素?cái)?shù)——大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。判斷：對(duì)于指定的n，如果[2,n-1]內(nèi)的整數(shù)都不能整除n，則n為素?cái)?shù)。ADL語言寫算法算法證明很難，可以使用邊界條件和特殊數(shù)據(jù)，人工模擬算法執(zhí)行過程。完成情況思想——基本正確，對(duì)素?cái)?shù)定義的理解：1？算法——特殊情況處理：n?1？算法輸出；ADL語言的使用：運(yùn)算符號(hào)：MOD(模)，DIV(除數(shù))，/(除)；??，??（取整）；％？sqrt?fabs()?輸入輸出參數(shù)：設(shè)置返

2、回值；中間用“.”分隔；條件語句：ifthenelse；fori＝1tonstep1(i=i+1?)賦值語句：?參考答案算法S(n.flag)/*判斷整數(shù)n是否為素?cái)?shù)，將結(jié)果保存到變量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.)▌?wù)_性驗(yàn)證：假定n＝7，模擬執(zhí)行過程，對(duì)i＝2，3，4，5，6時(shí)，分別判斷(7modi)的取值是否

3、為0。改進(jìn)：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)/*判斷整數(shù)n是否為素?cái)?shù)，將結(jié)果保存到變量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.)▌作業(yè)1-8若A(n)=amnm+…+a1n+

4、a0是關(guān)于n的m次多項(xiàng)式，證明A(n)=O(nm)。設(shè)f(n)和g(n)是正整數(shù)集到正實(shí)數(shù)集的函數(shù)，稱f(n)是O(g(n))當(dāng)且僅當(dāng)存在正常數(shù)C和n0，使得對(duì)任意的n?n0，有f(n)?Cg(n)。完成情況：令n0＝1，C＝am+…+a1+a0，amnm+…+a1n+a0?Cnm注意：當(dāng)ai?0時(shí)，aini?ainm不一定成立。證明：對(duì)于所有的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)。參考答案作業(yè)1－11證明對(duì)正整數(shù)n≥3，算法BS的元素比較次數(shù)T(n)≤5n/3-2。已知：0n=1T(n)=1n=2T(?n/2?)+T(?n/2?)+2n>2考察知識(shí)點(diǎn)：數(shù)學(xué)歸納法基礎(chǔ)歸納：n=c(初值)時(shí)，命題是正確的；歸納步驟：如果n＝k－1時(shí)，命題成立，則n＝k時(shí)，命題也成立。完成情況：利用結(jié)論T(n)＝3n/2－2，需要注意前提條件——當(dāng)n是2的冪時(shí)；由n=k反推n＝k-1時(shí)的情況。0n=1T(n)=1n=2T(?n/2?)+T(?n/2?)+2n>2n=3時(shí)，T(3)=T(1)+T(2)+2=3，5

14、?3/3-2=3，命題成立。假設(shè)n<=k時(shí)命題成立，需證明n=k+1時(shí)成立。當(dāng)k≥3時(shí)，有(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綜上，命題得證。作業(yè)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]