高考數(shù)學(xué)一輪復(fù)習(xí) 1.3.1《算法案例——輾轉(zhuǎn)相除法與更相減損術(shù)》課件 新人教A版必修3.ppt

1 3算法案例 第一課時(shí) 問題提出 1 研究一個(gè)實(shí)際問題的算法 主要從算法步驟 程序框圖和編寫程序三方面展開 在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種 在程序設(shè)計(jì)中基本的算法語句有哪幾種 2 求兩個(gè)正整數(shù)的最大公約數(shù) 是數(shù)學(xué)中的一個(gè)基礎(chǔ)性問題 它有各種解決辦法 我們以此為案例 對(duì)該問題的算法作一些探究 輾轉(zhuǎn)相除法與更相減損術(shù) 知識(shí)探究 一 輾轉(zhuǎn)相除法 思考1 18與30的最大公約數(shù)是多少 你是怎樣得到的 先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除 一直除到所得的商是互質(zhì)數(shù)為止 然后把所有的除數(shù)連乘起來即為最大公約數(shù) 思考2 對(duì)于8251與6105這兩個(gè)數(shù) 由于其公有的質(zhì)因數(shù)較大 利用上述方法求最大公約數(shù)就比較困難 注意到8251 6105 1 2146 那么8251與6105這兩個(gè)數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系 思考3 又6105 2146 2 1813 同理 6105與2146的公約數(shù)和2146與1813的公約數(shù)相等 重復(fù)上述操作 你能得到8251與6105這兩個(gè)數(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 輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟 這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu) m n q r 用程序框圖表示出右邊的過程 r mmodn m n n r r 0 是 否 思考4 輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu) 思考5 上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法 一般地 用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m n的最大公約數(shù) 可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法 其算法步驟如何設(shè)計(jì) 第一步 給定兩個(gè)正整數(shù)m n m n 第二步 計(jì)算m除以n所得的余數(shù)r 第三步 m n n r 第四步 若r 0 則m n的最大公約數(shù)等于m 否則 返回第二步 思考5 該算法的程序框圖如何表示 思考6 該程序框圖對(duì)應(yīng)的程序如何表述 inputm n do r mmodn m n n r loopuntilr 0 printm end 思考7 如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法 則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m n的最大公約數(shù)的程序框圖和程序分別如何表示 inputm n whilen 0 r mmodn m n n r wend printm end 練習(xí)1 利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù) 53 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0 知識(shí)探究 二 更相減損術(shù) 思考1 設(shè)兩個(gè)正整數(shù)m n 若m n k 則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等 反復(fù)利用這個(gè)原理 可求得98與63的最大公約數(shù)為多少 98 63 35 14 7 7 21 7 14 28 7 21 35 28 7 63 35 28 思考2 上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為更相減損術(shù) 一般地 用更相減損術(shù)求兩個(gè)正整數(shù)m n的最大公約數(shù) 可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法 其算法步驟如何設(shè)計(jì) 第一步 給定兩個(gè)正整數(shù)m n m n 第二步 計(jì)算m n所得的差k 第三步 比較n與k的大小 其中大者用m表示 小者用n表示 第四步 若m n 則m n的最大公約數(shù)等于m 否則 返回第二步 思考3 該算法的程序框圖如何表示 思考4 該程序框圖對(duì)應(yīng)的程序如何表述 inputm n whilemn k m n ifn kthen m n n k else m k endif wend printm end 更相減損術(shù) 在中國(guó)古代數(shù)學(xué)專著 九章算術(shù) 中記述為 可半者半之 不可半者 副置分母 子之?dāng)?shù) 以少減多 更相減損 求其等也 以等數(shù)約之 input m n m nifm nthena mm nn aendifk 0whilemmod2 0andnmod2 0m m 2n n 2k k 1wendd m n whilednifd nthenm delsem nn dendifd m nwendd 2 k dprintdend 理論遷移 例1分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù) 輾轉(zhuǎn)相除法 168 93 1 75 93 75 1 18 75 18 4 3 18 3 6 更相減損術(shù) 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三個(gè)數(shù)的最大公約數(shù) 因?yàn)?25 130 2 65 130 65 2 所以325與130的最大公約數(shù)是65 因?yàn)?70 65 4 10 65 10 6 5 10 5 2 所以65與270最大公約數(shù)是5 故325 130 270三個(gè)數(shù)的最大公約數(shù)是5 1 輾轉(zhuǎn)相除法 就是對(duì)于給定的兩個(gè)正整數(shù) 用較大的數(shù)除以較小的數(shù) 若余數(shù)不為零 則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù) 繼續(xù)上面的除法 直到大數(shù)被小數(shù)除盡為止 這時(shí)的較小的數(shù)即為原來兩個(gè)數(shù)的最大公約數(shù) 小結(jié)作業(yè) 2 更相減損術(shù) 就是對(duì)于給定的兩個(gè)正整數(shù) 用較大的數(shù)減去較小的數(shù) 然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù) 繼續(xù)上面的減法 直到差和較小的數(shù)相等 此時(shí)相等的兩數(shù)即為原來兩個(gè)數(shù)的最大公約數(shù) 比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 1 都是求最大公約數(shù)的方法 計(jì)算上輾轉(zhuǎn)相除法以除法為主 更相減損術(shù)以減法為主 計(jì)