算法初步全章 算法案例1孫子問(wèn)題.ppt

《算法初步全章 算法案例1孫子問(wèn)題.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、流程圖算法的描述算法自然語(yǔ)言順序結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)輸語(yǔ)句偽代碼循環(huán)語(yǔ)句賦值語(yǔ)句條件語(yǔ)句入出中國(guó)剩余定理(孫子問(wèn)題)“孫子問(wèn)題”記載在《孫子算經(jīng)》中，原文是：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？”孫子問(wèn)題的現(xiàn)代數(shù)學(xué)描述“孫子問(wèn)題”相當(dāng)于求關(guān)于x,y,z的方程組的正整數(shù)解。解題分析（1）如何依次檢索正整數(shù)？（采用循環(huán)結(jié)構(gòu)）（2）該循環(huán)何時(shí)結(jié)束？（找到滿足條件的整數(shù)為止）（3）一個(gè)正整數(shù)m什么時(shí)候滿足方程？（m同時(shí)滿足被3除余2，被5除余3，被7除余2）引入記號(hào)：m被3除余2用符號(hào)表示為Mod(m，3)＝2；m被5除

2、余3用符號(hào)表示為Mod(m，5)＝3；m被7除余3用符號(hào)表示為Mod(m，7)＝2流程圖偽代碼m?2WhileMod(m,3)≠2orMod(m,5)≠3orMod(m,7)≠2m?m＋1EndWhilePrintm例1有3個(gè)連續(xù)的自然數(shù)，其中最小的能被15整除，中間的能被17整除，最大的能被19整除，求滿足要求的一組三個(gè)連續(xù)的自然數(shù)。分析：本題的其實(shí)就是求下面不定方程組的正整數(shù)解.算法S1取m＝1；S2當(dāng)m不能被15整除，或m＋1不能被17整除，或m＋2不能被19整除，則m?m＋1，轉(zhuǎn)S2；否則輸出m，m＋1，m＋2，算法結(jié)束.流程圖m?1WhileMod(m,15)

3、≠2_orMod(m＋1,17)≠0_orMod(m＋2,19)≠0m?m＋1EndWhilePrintm，m+1，m+2偽代碼思考：以下偽代碼是否可行？k?1a?15kWhileMod(a＋1,17)≠0or_Mod(a＋2,19)≠0k?k＋1a?15kEndWhilePrinta,a＋1,a＋2本課小結(jié)1．韓信點(diǎn)兵－孫子問(wèn)題的求解算法；2．利用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)整數(shù)的搜索；3．利用邏輯運(yùn)算符Or實(shí)現(xiàn)多條件的判斷。