2017-2018版高中數學第一章算法初步1.4算法案例學案版3

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

答案精析問題導學知識點二思考“三三數之剩二”意思是一堆東西,三個三個地分組，余二個．設這堆東西數目為m，則m＝3x＋2,其中x指組數．梳理eq\b\lc\｛\rc\（\a\vs4\al\co1(m＝3x＋2，,m＝5y＋3，,m＝7z＋2）)知識點三思考設204與85的最大公約數為a，則a能整除204，故能整除85×2＋34.又因為a也是85的約數,故a能整除85×2，所以a必能整除34,即a是34的約數，從而是85與34的最大公約數,顯然，204與85的公約數問題轉化成了85與34的公約數問題，問題難度降低了．梳理(1）兩個正整數m，n（m>n）m除以n所得的余數rm←n,n←rm第二步(2）偶數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跟蹤訓練1解算法的偽代碼如下：m←2WhileMod（m，5）≠2orMod（m，7)≠3orMod（m，9）≠4m←m＋1EndWhilePrintm例2解算法如下：S1輸入兩個正整數a,b；S2若Mod（a,b)≠0,那么轉S3，否則轉S6;S3r←Mod(a,b)；S4a←b；S5b←r，轉S2；S6輸出b。流程圖如圖:偽代碼如下：Reada，bWhileModa,b≠0r←Moda，ba←bb←rEndWhilePrintb跟蹤訓練2解輾轉相除法：319÷261＝1（余58）,261÷58＝4（余29），58÷29＝2（余0）,所以319與261的最大公約數為29。更相減損術:319－261＝58，261－58＝203，203－58＝145,145－58＝87,87－58＝29，58－29＝29，29－29＝0,所以319與261的最大公約數是29.例3解流程圖如圖：偽代碼如圖:a←1b←1。5c←0.001Dox0←fa←a3－a－1fx0←－x0－1Iffx0＝0ThenExitDoIffafx0<0Thenb←x0Elsea←x0EndIfUntil｜a－b｜〈cEndDoPrintx0跟蹤訓練3解偽代碼如圖：Reada，b，cDox0←fa←lna＋2a－1fx0←lnx0＋2x0－1Iffx0＝0ThenExitDoIffafx0<0Thenb←x0Elsea←x0EndIfUntil|a－b|〈cEndDoPrintx0當堂訓練1．322．先除以2，得到18與67解析∵36與134都是偶數，∴第一步應為：先除以2，得到18與67。3．解算法的偽代碼如圖：y←0x←0Whilex<100x←5y＋3Printxy←y＋1EndWhile4．解825