2017-2018版高中數(shù)學(xué)第一章算法初步1.4算法案例學(xué)案版3

學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精PAGE20學(xué)必求其心得，業(yè)必貴于專精PAGE1.4算法案例學(xué)習(xí)目標(biāo)1。理解解決“韓信點(diǎn)兵—孫子問(wèn)題”的算法思想；2。理解輾轉(zhuǎn)相除法與更相減損術(shù)的數(shù)學(xué)原理；3。能用偽代碼實(shí)現(xiàn)二分法求方程的近似解．知識(shí)點(diǎn)一本節(jié)涉及的內(nèi)置函數(shù)就像木工不必自己造鋸一樣,VB也把一些常用基礎(chǔ)工具做成內(nèi)置函數(shù)，以備使用者直接調(diào)用，下面是本節(jié)涉及的內(nèi)置函數(shù)：函數(shù)功能例子Mod（a,b)得到a除以b的余數(shù)Mod(9，2）＝1Val(）將字符串轉(zhuǎn)換為數(shù)值Int（x）表示不超過(guò)x的最大整數(shù)Int(3.9)＝3知識(shí)點(diǎn)二“韓信點(diǎn)兵一孫子問(wèn)題”的數(shù)學(xué)本質(zhì)思考“三三數(shù)之剩二”是什么意思?如何用代數(shù)式表示？梳理“韓信點(diǎn)兵-孫子問(wèn)題”是求關(guān)于x,y，z的一次不定方程組________________的正整數(shù)解．知識(shí)點(diǎn)三輾轉(zhuǎn)相除法與更相減損術(shù)的算法原理思考我們知道204＝85×2＋34。為什么204與85的最大公約數(shù)就是85與34的最大公約數(shù)？梳理一般地,有2種算法求兩個(gè)正整數(shù)的最大公約數(shù)：(1)輾轉(zhuǎn)相除法的運(yùn)算步驟：第一步，給定__________________．第二步，計(jì)算__________________．第三步，____________.第四步，若r＝0，則m，n的最大公約數(shù)等于______；否則，返回__________．(2）更相減損術(shù)的運(yùn)算步驟：第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是______．若是,用____約簡(jiǎn)；若不是,執(zhí)行________．第二步，以________的數(shù)減去________的數(shù)，接著把所得的差與________的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個(gè)操作,直到所得的數(shù)________為止,則這個(gè)數(shù)（等數(shù)）或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)．知識(shí)點(diǎn)四二分法的實(shí)現(xiàn)思考你還能回憶起二分法的作用和原理嗎?梳理求方程f(x）＝0在區(qū)間[a，b］上的近似解的步驟為：S1?。踑,b］的中點(diǎn)x0＝eq\f（1,2)(a＋b),將區(qū)間一分為二．S2若________，則x0就是方程的根，否則判斷根x*在x0的左側(cè)還是右側(cè)：若____________，則x*∈(x0，b），以x0代替a;若____________，則x*∈(a,x0）,以x0代替b.S3若|a－b｜<c，計(jì)算終止，此時(shí)____________，否則轉(zhuǎn)______．類型一“韓信點(diǎn)兵—-孫子問(wèn)題”例1韓信是秦末漢初的著名軍事家．據(jù)說(shuō)有一次漢高祖劉邦在衛(wèi)士的簇?fù)硐聛?lái)到練兵場(chǎng)，劉邦問(wèn)韓信有什么辦法,不要逐個(gè)報(bào)數(shù)，就能知道場(chǎng)上士兵的人數(shù)．韓信先令士兵排成3列縱隊(duì)進(jìn)行操練，結(jié)果有2人多余;接著他立刻下令將隊(duì)形改為5列縱隊(duì)，這一改，又多出3人；隨后他又下令改為7列縱隊(duì)，這一次又剩下2人無(wú)法成整列．結(jié)果在場(chǎng)的人哈哈大笑，韓信看此情形，立刻報(bào)告共有士兵2333人．眾人都愣了，不知韓信用什么辦法這么快清點(diǎn)出準(zhǔn)確人數(shù)的．這個(gè)故事卻引出一個(gè)著名的數(shù)學(xué)問(wèn)題，即聞名世界的“孫子問(wèn)題”．最早出現(xiàn)在我國(guó)《算經(jīng)十書》之一的《孫子算經(jīng)》中．原文是:“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二．問(wèn)物幾何？答曰:二十三．”所以人們將這種問(wèn)題的通用解法稱為“孫子剩余定理”或“中國(guó)剩余定理"．設(shè)有物m個(gè)，則其本質(zhì)為由方程組eq\b\lc\{\rc\（\a\vs4\al\co1(m＝3x＋2，，m＝5y＋3，,m＝7z＋2)）求m的正整數(shù)解．試為此問(wèn)題編寫流程圖和偽代碼．反思與感悟此算法的本質(zhì)是從最小2開(kāi)始,逐個(gè)實(shí)驗(yàn)是否滿足方程組,對(duì)人而言是個(gè)笨法,但很適合計(jì)算機(jī)，以上程序求出的是m的最小值．跟蹤訓(xùn)練1有一堆圍棋子，五個(gè)五個(gè)地?cái)?shù)，最后余下2個(gè);七個(gè)七個(gè)地?cái)?shù)，最后余下3個(gè)；九個(gè)九個(gè)地?cái)?shù)，最后余下4個(gè)．請(qǐng)用偽代碼表示“求出這堆棋子至少有多少個(gè)"的一種算法．類型二輾轉(zhuǎn)相除法的現(xiàn)代實(shí)現(xiàn)例2你能根據(jù)“歐幾里得輾轉(zhuǎn)相除法"設(shè)計(jì)一種求兩個(gè)正整數(shù)a,b（a〉b)的最大公約數(shù)的一個(gè)算法嗎？并畫出流程圖，編寫偽代碼．反思與感悟利用輾轉(zhuǎn)相除法求給定的兩個(gè)數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對(duì)中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì)，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)．跟蹤訓(xùn)練2用輾轉(zhuǎn)相除法和更相減損術(shù)求261和319的最大公約數(shù)．類型三求方程f（x)＝0近似解的算法例3畫出用區(qū)間二分法求方程x3－x－1＝0在區(qū)間[1，1.5]上的一個(gè)近似解(誤差不超過(guò)0.001）的一個(gè)算法流程圖并編寫偽代碼．反思與感悟在此算法中用到了條件語(yǔ)句和循環(huán)語(yǔ)句，所以用“Do”是因?yàn)橐獔?zhí)行再判斷是否滿足條件，因?yàn)椴恢h(huán)次數(shù)，所以也不宜用“For”語(yǔ)句．跟蹤訓(xùn)練3改造例3中偽代碼，用來(lái)求f（x）＝lnx＋2x－1在區(qū)間[a,b］上的一個(gè)近似解（誤差不超過(guò)c）．1．m是一正整數(shù)，對(duì)兩個(gè)正整數(shù)a,b，若a－b是m的倍數(shù)，則稱模m同余，用符號(hào)a≡b（Modm）表示．則a≡5（Mod27）中，a的取值最小為_(kāi)_______．2．用更相減損術(shù)求36與134的最大公約數(shù)，第一步應(yīng)為_(kāi)_________________________．3．求方程x＝5y＋3（其中y為自然數(shù)）的所有小于100的x的正整數(shù)解，用偽代碼表示．4．求兩個(gè)正數(shù)8251和6105的最大公約數(shù)．1．求兩個(gè)正整數(shù)的最大公約數(shù)時(shí)，用輾轉(zhuǎn)相除法進(jìn)行設(shè)計(jì)的關(guān)鍵是：將“輾轉(zhuǎn)”的過(guò)程用循環(huán)語(yǔ)句表示．為了避免求循環(huán)次數(shù)(對(duì)兩個(gè)具體的正整數(shù)，循環(huán)次數(shù)可以求出，但會(huì)使程序更為復(fù)雜），最好使用“While"語(yǔ)句．2．用二分法求方程近似解，必須先判斷方程在給定區(qū)間上是否有解．3．二分法的過(guò)程是一個(gè)多次重復(fù)的過(guò)程，故可用循環(huán)結(jié)構(gòu)處理．4．二分法過(guò)程中需要對(duì)中點(diǎn)(端點(diǎn))處函數(shù)值的符號(hào)進(jìn)行判定，故實(shí)現(xiàn)算法需用選擇結(jié)構(gòu),即用條件語(yǔ)句進(jìn)行分支選擇．

答案精析問(wèn)題導(dǎo)學(xué)知識(shí)點(diǎn)二思考“三三數(shù)之剩二”意思是一堆東西,三個(gè)三個(gè)地分組，余二個(gè)．設(shè)這堆東西數(shù)目為m，則m＝3x＋2,其中x指組數(shù)．梳理eq\b\lc\｛\rc\（\a\vs4\al\co1(m＝3x＋2，,m＝5y＋3，,m＝7z＋2）)知識(shí)點(diǎn)三思考設(shè)204與85的最大公約數(shù)為a，則a能整除204，故能整除85×2＋34.又因?yàn)閍也是85的約數(shù),故a能整除85×2，所以a必能整除34,即a是34的約數(shù)，從而是85與34的最大公約數(shù),顯然，204與85的公約數(shù)問(wèn)題轉(zhuǎn)化成了85與34的公約數(shù)問(wèn)題，問(wèn)題難度降低了．梳理(1）兩個(gè)正整數(shù)m，n（m>n）m除以n所得的余數(shù)rm←n,n←rm第二步(2）偶數(shù)2第二步較大較小較小相等知識(shí)點(diǎn)四思考二分法是用來(lái)求方程近似解的，其原理是先確定一個(gè)解所在的大致區(qū)間，然后借助零點(diǎn)存在定理，不斷縮小這個(gè)區(qū)間．梳理f（x0）＝0f（a)f(x0)〉0f（a)f（x0)<0x*≈x0S1題型探究例1解流程圖為偽代碼為m←2WhileMod(m，3）≠2orMod（m，5）≠3orMod(m,7)≠2m←m＋1EndWhilePrintm跟蹤訓(xùn)練1解算法的偽代碼如下：m←2WhileMod（m，5）≠2orMod（m，7)≠3orMod（m，9）≠4m←m＋1EndWhilePrintm例2解算法如下：S1輸入兩個(gè)正整數(shù)a,b；S2若Mod（a,b)≠0,那么轉(zhuǎn)S3，否則轉(zhuǎn)S6;S3r←Mod(a,b)；S4a←b；S5b←r，轉(zhuǎn)S2；S6輸出b。流程圖如圖:偽代碼如下：Reada，bWhileModa,b≠0r←Moda，ba←bb←rEndWhilePrintb跟蹤訓(xùn)練2解輾轉(zhuǎn)相除法：319÷261＝1（余58）,261÷58＝4（余29），58÷29＝2（余0）,所以319與261的最大公約數(shù)為29。更相減損術(shù):319－261＝58，261－58＝203，203－58＝145,145－58＝87,87－58＝29，58－29＝29，29－29＝0,所以319與261的最大公約數(shù)是29.例3解流程圖如圖：偽代碼如圖:a←1b←1。5c←0.001Dox0←fa←a3－a－1fx0←－x0－1Iffx0＝0ThenExitDoIffafx0<0Thenb←x0Elsea←x0EndIfUntil｜a－b｜〈cEndDoPrintx0跟蹤訓(xùn)練3解偽代碼如圖：Reada，b，cDox0←fa←lna＋2a－1fx0←lnx0＋2x0－1Iffx0＝0ThenExitDoIffafx0<0Thenb←x0Elsea←x0EndIfUntil|a－b|〈cEndDoPrintx0當(dāng)堂訓(xùn)練1．322．先除以2，得到18與67解析∵36與134都是偶數(shù)，∴第一步應(yīng)為：先除以2，得到18與67。3．解算法的偽代碼如圖：y←0x←0Whilex<100x←5y＋3Printxy←y＋1EndWhile4．解825