《1.4算法案例(2)》教案

rnrqmrrnrqmrrrrrqrrr《算法案（2教案教目：．理解歐幾里得輾轉(zhuǎn)相除法的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析．．理解用歐幾里得輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)的方法與步驟．．能根據(jù)算法語(yǔ)句與流程圖的知識(shí)設(shè)計(jì)完整的流程圖并寫出其偽代碼．教重點(diǎn)重點(diǎn)：1．理解歐幾里得輾轉(zhuǎn)相除法求兩個(gè)數(shù)最大公約數(shù)的方法與步驟．．能寫出歐幾里得輾轉(zhuǎn)相除法的流程圖和偽代碼．難點(diǎn)：1．利用計(jì)算機(jī)編程來(lái)實(shí)現(xiàn)求兩個(gè)數(shù)的大公約數(shù)．．歐幾里得輾轉(zhuǎn)相除法的流程圖和偽代碼程序．教過(guò)：一、問題情境在初中，我們已經(jīng)學(xué)過(guò)求最大公約數(shù)的知識(shí)，你能求與0公約數(shù)嗎？我們都是利用找公約數(shù)的方法來(lái)求最大公約數(shù)公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)又該怎樣求它們的最大公約數(shù)？比如251與105最大公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容．二、建構(gòu)教學(xué)以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法叫幾里德算法是歐幾里德在公元前3年左右首先提出的．利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：第一步：用較大的數(shù)m除較小的數(shù)n得一個(gè)商和一個(gè)數(shù)；0第二步：若r，為的大約數(shù)；若r，用除數(shù)除余數(shù)r得00一個(gè)商和個(gè)余數(shù)；1第三步：若，則為的大公約數(shù)；若，用除數(shù)除余數(shù)得到0一個(gè)商和一個(gè)余數(shù)；……依次計(jì)算直至，時(shí)所得的即為所求的最大公約數(shù)．nn三、數(shù)學(xué)運(yùn)用利用輾轉(zhuǎn)相除法與更相減損術(shù)的計(jì)算算法可設(shè)計(jì)出程序框圖以B程序來(lái)在計(jì)算機(jī)上實(shí)現(xiàn)輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)由同學(xué)們?cè)O(shè)計(jì)相應(yīng)框圖并相互之間檢查框圖與程序的正確性，并在計(jì)算機(jī)上驗(yàn)證自己的結(jié)果．rr(1)輾轉(zhuǎn)相除法的程序框圖及程序程序框圖：偽代碼

開始輸入用較大的數(shù)除以較小的數(shù)，得到除式

rr(,r

(0r)

，直到．五、要點(diǎn)歸納與方法小結(jié)本節(jié)課學(xué)習(xí)了以下內(nèi)容：．輾轉(zhuǎn)相除法中蘊(yùn)