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

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

答案精析問題導(dǎo)學(xué)知識點二思考“三三數(shù)之剩二”意思是一堆東西,三個三個地分組，余二個．設(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è)204與85的最大公約數(shù)為a，則a能整除204，故能整除85×2＋34.又因為a也是85的約數(shù),故a能整除85×2，所以a必能整除34,即a是34的約數(shù)，從而是85與34的最大公約數(shù),顯然，204與85的公約數(shù)問題轉(zhuǎn)化成了85與34的公約數(shù)問題，問題難度降低了．梳理(1）兩個正整數(shù)m，n（m>n）m除以n所得的余數(shù)rm←n,n←rm第二步(2）偶數(shù)2第二步較大較小較小相等知識點四思考二分法是用來求方程近似解的，其原理是先確定一個解所在的大致區(qū)間，然后借助零點存在定理，不斷縮小這個區(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輸入兩個正整數(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