《2017-2018版高中數學 第一章 算法初步 1.4 算法案例課件 蘇教版必修3》由會員分享，可在線閱讀，更多相關《2017-2018版高中數學 第一章 算法初步 1.4 算法案例課件 蘇教版必修3（37頁珍藏版）》請在裝配圖網上搜索。
1、第1章算法初步1.4算法案例 學習目標1.理解解決“韓信點兵孫子問題”的算法思想；2.理解輾轉相除法與更相減損術的數學原理；3.能用偽代碼實現(xiàn)二分法求方程的近似解. 題型探究問題導學內容索引 當堂訓練 問題導學 知識點一本節(jié)涉及的內置函數就像木工不必自己造鋸一樣，VB也把一些常用基礎工具做成內置函數，以備使用者直接調用，下面是本節(jié)涉及的內置函數：函數功能例子Mod(a，b)得到a除以b的余數Mod(9，2)1Val()將字符串轉換為數值Int(x)表示不超過x的最大整數Int(3.9)3 思考知識點二“ 韓信點兵一孫子問題” 的數學本質“三三數之剩二”是什么意思？如何用代數式表示？“三三數之剩
2、二”意思是一堆東西，三個三個地分組，余二個.設這堆東西數目為m，則m3x2，其中x指組數. 答案 梳理“韓信點兵孫子問題”是求關于x，y，z的一次不定方程組_的正整數解. 思考知識點三輾轉相除法與更相減損術的算法原理我們知道20485234.為什么204與85的最大公約數就是85與34的最大公約數？設204與85的最大公約數為a，則a能整除204，故能整除85234.又因為a也是85的約數，故a能整除852，所以a必能整除34，即a是34的約數，從而是85與34的最大公約數，顯然，204與85的公約數問題轉化成了85與34的公約數問題，問題難度降低了.答案 梳理一般地，有2種算法求兩個正整數的
3、最大公約數：(1)輾轉相除法的運算步驟：第一步，給定.第二步，計算 .第三步， .第四步，若r0，則m，n的最大公約數等于 ；否則，返回.第二步兩個正整數m，n(mn)m除以n所得的余數rm n，n r m (2)更相減損術的運算步驟：第一步，任意給定兩個正整數，判斷它們是否都是.若是，用約簡；若不是，執(zhí)行.第二步，以的數減去的數，接著把所得的差與的數比較，并以大數減小數，繼續(xù)這個操作，直到所得的數為止，則這個數(等數)或這個數與約簡的數的乘積就是所求的最大公約數.相等偶數2第二步較大較小較小 思考知識點四二分法的實現(xiàn)你還能回憶起二分法的作用和原理嗎？二分法是用來求方程近似解的，其原理是先確定
4、一個解所在的大致區(qū)間，然后借助零點存在定理，不斷縮小這個區(qū)間.答案 梳理求方程f(x)0在區(qū)間a，b上的近似解的步驟為：S1取a，b的中點x0(ab)，將區(qū)間一分為二.S2若 ，則x0就是方程的根，否則判斷根x*在x0的左側還是右側：若 ，則x* (x0，b)，以x0代替a；若 ，則x* (a，x0)，以x0代替b.S3若|ab|0f(a)f(x0)b)的最大公約數的一個算法嗎？并畫出流程圖，編寫偽代碼.類型二輾轉相除法的現(xiàn)代實現(xiàn) 解答 算法如下：S1輸入兩個正整數a，b；S2若Mod(a，b) 0，那么轉S3，否則轉S6；S3r Mod(a，b)；S4a b；S5b r，轉S2；S6輸出b.
5、流程圖如圖： 偽代碼如下：Reada，bWhileMod(a，b) 0r Mod(a，b)a bb rEndWhilePrintb 利用輾轉相除法求給定的兩個數的最大公約數，即利用帶余除法，用數對中較大的數除以較小的數，若余數不為零，則將余數和較小的數構成新的數對，再利用帶余除法，直到大數被小數除盡，則這時的較小數就是原來兩個數的最大公約數. 反 思 與 感悟 跟蹤訓練2用輾轉相除法和更相減損術求261和319的最大公約數. 解答 輾轉相除法：3192611(余58)，261584(余29)，58292(余0)，所以319與261的最大公約數為29.更相減損術：31926158，2615820
6、3，20358145， 1455887，875829，582929，29290，所以319與261的最大公約數是29. 類型三求方程 f(x)0近似解的算法例3畫出用區(qū)間二分法求方程x3x10在區(qū)間1，1.5上的一個近似解(誤差不超過0.001)的一個算法流程圖并編寫偽代碼. 解答 流程圖如圖：a 1b 1.5c 0.001Do f(a) a3 a 1Iff(x0) 0ThenExitDoIff(a)f(x0)0Then b x 0Else a x0EndIfUntil|a b|cEndDoPrintx0 偽代碼如圖： 在此算法中用到了條件語句和循環(huán)語句，所以用“ Do”是因為要執(zhí)行再判斷是否
7、滿足條件，因為不知循環(huán)次數，所以也不宜用“ For”語句.反 思 與 感悟 跟蹤訓練3改造例3中偽代碼，用來求f(x)lnx2x1在區(qū)間a，b上的一個近似解(誤差不超過c). 解析 偽代碼如圖：Read a， b， cDo f(a) lna 2a 1 f(x0) lnx0 2x0 1If f(x0) 0 Then Exit DoIf f(a)f(x0)0 Then b x0Else a x 0End IfUntil |a b|cEnd DoPrint x0 當堂訓練 2 3 41 1.m是一正整數，對兩個正整數a，b，若ab是m的倍數，則稱模m同余，用符號a b(Modm)表示.則a 5(Mo
8、d27)中，a的取值最小為_. 答案32 2.用更相減損術求36與134的最大公約數，第一步應為_. 36與134都是偶數，第一步應為：先除以2，得到18與67.先除以2，得到18與67 2 3 41答案 解析 3.求方程x5y3(其中y為自然數)的所有小于100的x的正整數解，用偽代碼表示.算法的偽代碼如圖：解答y 0 x 0Whilex100 x 5y3Printxy y1EndWhile 2 3 41 4.求兩個正數8251和6105的最大公約數.8251610512146；6105214621813；214618131333；18133335148；333148237；1483740；則37為8251與6105的最大公約數. 解答 2 3 41 規(guī) 律 與 方法1.求兩個正整數的最大公約數時，用輾轉相除法進行設計的關鍵是：將“輾轉”的過程用循環(huán)語句表示.為了避免求循環(huán)次數(對兩個具體的正整數，循環(huán)次數可以求出，但會使程序更為復雜)，最好使用“ While”語句.2.用二分法求方程近似解，必須先判斷方程在給定區(qū)間上是否有解.3.二分法的過程是一個多次重復的過程，故可用循環(huán)結構處理.4.二分法過程中需要對中點(端點)處函數值的符號進行判定，故實現(xiàn)算法需用選擇結構，即用條件語句進行分支選擇. 本課結束
2017-2018版高中數學 第一章 算法初步 1.4 算法案例課件 蘇教版必修3
