0306高一數(shù)學（1.31輾轉相除法與更相減損術） (2).ppt

1 3算法案例 第一課時 問題提出 1 研究一個實際問題的算法 主要從算法步驟 程序框圖和編寫程序三方面展開 在程序框圖中算法的基本邏輯結構有哪幾種 在程序設計中基本的算法語句有哪幾種 2 求兩個正整數(shù)的最大公約數(shù) 是數(shù)學中的一個基礎性問題 它有各種解決辦法 我們以此為案例 對該問題的算法作一些探究 輾轉相除法與更相減損術 知識探究 一 輾轉相除法 思考1 18與30的最大公約數(shù)是多少 你是怎樣得到的 先用兩個數(shù)公有的質因數(shù)連續(xù)去除 一直除到所得的商是互質數(shù)為止 然后把所有的除數(shù)連乘起來即為最大公約數(shù) 思考2 對于8251與6105這兩個數(shù) 由于其公有的質因數(shù)較大 利用上述方法求最大公約數(shù)就比較困難 注意到8251 6105 1 2146 那么8251與6105這兩個數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關系 思考3 又6105 2146 2 1813 同理 6105與2146的公約數(shù)和2146與1813的公約數(shù)相等 重復上述操作 你能得到8251與6105這兩個數(shù)的最大公約數(shù)嗎 2146 1813 1 333 148 37 4 0 333 148 2 37 1813 333 5 148 8251 6105 1 2146 6105 2146 2 1813 思考4 上述求兩個正整數(shù)的最大公約數(shù)的方法稱為輾轉相除法或歐幾里得算法 一般地 用輾轉相除法求兩個正整數(shù)m n的最大公約數(shù) 可以用什么邏輯結構來構造算法 其算法步驟如何設計 第一步 給定兩個正整數(shù)m n m n 第二步 計算m除以n所得的余數(shù)r 第三步 m n n r 第四步 若r 0 則m n的最大公約數(shù)等于m 否則 返回第二步 思考5 該算法的程序框圖如何表示 思考6 該程序框圖對應的程序如何表述 inputm n do r mmodn m n n r loopuntilr 0 printm end 思考7 如果用當型循環(huán)結構構造算法 則用輾轉相除法求兩個正整數(shù)m n的最大公約數(shù)的程序框圖和程序分別如何表示 inputm n whilen 0 r mmodn m n n r wend printm end 知識探究 二 更相減損術 思考1 設兩個正整數(shù)m n 若m n k 則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等 反復利用這個原理 可求得98與63的最大公約數(shù)為多少 98 63 35 14 7 7 21 7 14 28 7 21 35 28 7 63 35 28 思考2 上述求兩個正整數(shù)的最大公約數(shù)的方法稱為更相減損術 一般地 用更相減損術求兩個正整數(shù)m n的最大公約數(shù) 可以用什么邏輯結構來構造算法 其算法步驟如何設計 第一步 給定兩個正整數(shù)m n m n 第二步 計算m n所得的差k 第三步 比較n與k的大小 其中大者用m表示 小者用n表示 第四步 若m n 則m n的最大公約數(shù)等于m 否則 返回第二步 思考3 該算法的程序框圖如何表示 思考4 該程序框圖對應的程序如何表述 inputm n whilemn k m n ifn kthen m n n k else m k endif wend printm end 更相減損術 在中國古代數(shù)學專著 九章算術 中記述為 可半者半之 不可半者 副置分母 子之數(shù) 以少減多 更相減損 求其等也 以等數(shù)約之 理論遷移 例1分別用輾轉相除法和更相減損術求168與93的最大公約數(shù) 輾轉相除法 168 93 1 75 93 75 1 18 75 18 4 3 18 3 6 更相減損術 168 93 75 93 75 18 75 18 57 57 18 39 39 18 21 21 18 3 18 3 15 15 3 12 12 3 9 9 3 6 6 3 3 例2求325 130 270三個數(shù)的最大公約數(shù) 因為325 130 2 65 130 65 2 所以325與130的最大公約數(shù)是65 因為270 65 4 10 65 10 6 5 10 5 2 所以65與270最大公約數(shù)是5 故325 130 270三個數(shù)的最大公約數(shù)是5 1 輾轉相除法 就是對于給定的兩個正整數(shù) 用較大的數(shù)除以較小的數(shù) 若余數(shù)不為零 則將余數(shù)和較小的數(shù)構成新的一對數(shù) 繼續(xù)上面的除法 直到大數(shù)被小數(shù)除盡為止 這時的較小的數(shù)即為原來兩個數(shù)的最大公約數(shù) 小結作業(yè) 2 更相減損術 就是對于給定的兩個正整