資源描述：
《06、【習(xí)題課】第1-3章.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第1－3章習(xí)題作業(yè)1－5試用ADL語言編寫一個算法，判斷任一整數(shù)n是否為素數(shù)?？疾熘R點判斷素數(shù)素數(shù)——大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。判斷：對于指定的n，如果[2,n-1]內(nèi)的整數(shù)都不能整除n，則n為素數(shù)。ADL語言寫算法算法證明很難，可以使用邊界條件和特殊數(shù)據(jù)，人工模擬算法執(zhí)行過程。完成情況思想——基本正確，對素數(shù)定義的理解：1？算法——特殊情況處理：n?1？算法輸出；ADL語言的使用：運算符號：MOD(模)，DIV(除數(shù))，/(除)；??，??（取整）；％？sqrt?fabs()?輸入輸出參數(shù)：設(shè)置返
2、回值；中間用“.”分隔；條件語句：ifthenelse；fori＝1tonstep1(i=i+1?)賦值語句：?參考答案算法S(n.flag)/*判斷整數(shù)n是否為素數(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ù)_性驗證：假定n＝7，模擬執(zhí)行過程，對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)/*判斷整數(shù)n是否為素數(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次多項式，證明A(n)=O(nm)。設(shè)f(n)和g(n)是正整數(shù)集到正實數(shù)集的函數(shù)，稱f(n)是O(g(n))當(dāng)且僅當(dāng)存在正常數(shù)C和n0，使得對任意的n?n0，有f(n)?Cg(n)。完成情況：令n0＝1，C＝am+…+a1+a0，amnm+…+a1n+a0?Cnm注意：當(dāng)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)。參考答案作業(yè)1－11證明對正整數(shù)n≥3，算法BS的元素比較次數(shù)T(n)≤5n/3-2。已知：0n=1T(n)=1n=2T(?n/2?)+T(?n/2?)+2n>2考察知識點：數(shù)學(xué)歸納法基礎(chǔ)歸納：n=c(初值)時，命題是正確的；歸納步驟：如果n＝k－1時，命題成立，則n＝k時，命題也成立。完成情況：利用結(jié)論T(n)＝3n/2－2，需要注意前提條件——當(dāng)n是2的冪時；由n=k反推n＝k-1時的情況。0n=1 T(n)=1n=2 T(?n/2?)+T(?n/2?)+2n>2n=3時，T(3)=T(1)+T(2)+2=3，5
14、?3/3-2=3，命題成立。假設(shè)n<=k時命題成立，需證明n=k+1時成立。當(dāng)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綜上，命題得證。作業(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]
