高三數(shù)學(xué)教案：算法案例――輾轉(zhuǎn)相除法

1、算法案例 輾轉(zhuǎn)相除法育才中學(xué)潘敏一、教材分析選自蘇教版普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書必修3 第一章第 4 節(jié)。1、地位作用：與傳統(tǒng)教學(xué)內(nèi)容相比， 算法初步為新增內(nèi)容，算法是計(jì)算機(jī)科學(xué)的重要基礎(chǔ)，從日常生活的電子郵件發(fā)送到繁忙的交通管理，從與人們生產(chǎn)、 生活息息相關(guān)的天氣預(yù)報(bào)到?jīng)]有硝煙的戰(zhàn)爭模擬等等都離不開計(jì)算機(jī)算法。算法思想已經(jīng)滲透到社會(huì)的方方面面，算法思想也逐漸成為每個(gè)現(xiàn)代人應(yīng)具有的數(shù)學(xué)素養(yǎng)。在以前的學(xué)習(xí)中， 雖然沒有出現(xiàn)算法這個(gè)名詞， 但實(shí)際上在數(shù)學(xué)教學(xué)中已經(jīng)滲透了大量的算法思想，如四則運(yùn)算的過程，求解方程的步驟，以及將要學(xué)習(xí)的數(shù)列求和等等，完成這些工作都需要一系列程序化的步驟，這就是算法思想

2、。本節(jié)內(nèi)容是探究古代算法案例輾轉(zhuǎn)相除法， 鞏固算法三種描述性語言 （自然語言、流程圖和偽代碼） ，提高學(xué)生分析和解決問題的能力。2、教學(xué)目標(biāo)：（ 1）知識(shí)目標(biāo)：理解輾轉(zhuǎn)相除法原理；能用自然語言、流程圖和偽代碼表達(dá)輾轉(zhuǎn)相除法；能應(yīng)用迭代算法思想。（ 2）能力目標(biāo)：培養(yǎng)學(xué)生把具體問題抽象轉(zhuǎn)化為算法語言的能力；培養(yǎng)學(xué)生自主探索和合作學(xué)習(xí)的能力。（3）情感目標(biāo)：使學(xué)生進(jìn)一步了解從具體到抽象， 抽象到具體的辨證思想方法， 對(duì)學(xué)生進(jìn)行辨證唯物主義教育；創(chuàng)設(shè)和諧融洽的教學(xué)氛圍和階梯形問題， 使學(xué)生在活動(dòng)中獲得成功感， 從而培養(yǎng)學(xué)生熱愛數(shù)學(xué)、積極學(xué)習(xí)數(shù)學(xué)、應(yīng)用數(shù)學(xué)的熱情。3、教學(xué)重點(diǎn)與難點(diǎn)：（ 1）教學(xué)重點(diǎn)：

3、理解輾轉(zhuǎn)相除法原理；能用自然語言、流程圖和偽代碼表達(dá)輾轉(zhuǎn)相除法。（ 2）教學(xué)難點(diǎn)：理解和區(qū)分兩種循環(huán)結(jié)構(gòu)表達(dá)輾轉(zhuǎn)相除法；能應(yīng)用迭代算法思想。二、教法學(xué)法1、教法： 以問題為載體，有引導(dǎo)的對(duì)話，讓學(xué)生經(jīng)歷知識(shí)的形成過程和發(fā)展過程，從而突出教學(xué)重點(diǎn)，并采用多媒體教學(xué)，增加課堂容量，有利于學(xué)生活動(dòng)的充分展開。2、學(xué)法： 以觀察、討論、思考、分析、動(dòng)手操作、自主探索、合作學(xué)習(xí)多種形式相結(jié)合，引導(dǎo)學(xué)生多角度、多層面認(rèn)識(shí)事物，突破教學(xué)難點(diǎn)。第 1頁共 6頁三、教學(xué)過程設(shè)計(jì)：1、情景設(shè)置感知輾轉(zhuǎn)相除法（發(fā)給每位學(xué)生一張長為22cm，寬為 6cm的紙條）【問 1】這張長方形的紙，先拿短邊往長邊上折，得到一個(gè)正

4、方形，從長方形上裁掉這個(gè)正方形后繼續(xù)將短邊往長邊上折， 一直到最后剩下來的是正方形為止， 最后得到的邊長是幾的正方形？【師生互動(dòng)解答】226 3 4；6 4 1 2；4 2 2 0 最后正方形的邊長為2cm?！驹O(shè)計(jì)意圖】通過動(dòng)手操作，直觀感受輾轉(zhuǎn)相除法的具體做法。2、理解輾轉(zhuǎn)相除法原理【問 2】 22 與 6 的最大公約數(shù)？【設(shè)計(jì)意圖】把輾轉(zhuǎn)相除法和情景設(shè)置聯(lián)系起來，承上啟下，順利過渡?！締?3】 204 與 85 的最大公約數(shù)？【師板書】204 85 2 3485 34 21734 17 2 0 204與 85 最大公約數(shù)為 17。【師引導(dǎo)】總結(jié)輾轉(zhuǎn)相除法具體步驟。【師講解】輾轉(zhuǎn)相除法原理：

5、（ 204， 85）（ 85， 34）（ 34， 17）?！揪?1】求 678 與 35 的最大公約數(shù)？【設(shè)計(jì)意圖】具體動(dòng)手操作，鞏固新知。3、設(shè)計(jì)輾轉(zhuǎn)相除法算法【問 4】寫出兩個(gè)正整數(shù)a,b(ab) 的最大公約數(shù)的一個(gè)算法?！編煶醪椒治觥?運(yùn)用輾轉(zhuǎn)相除法，產(chǎn)生一列數(shù)： a,b, r1 , r2 , rn 1 , rn ,0 。這列數(shù)從第三項(xiàng)開始，每項(xiàng)都是前兩項(xiàng)相除所得的余數(shù)，余數(shù)為0 的前一項(xiàng) r n ，既是 a 和 b 的最大公約數(shù)。遞推關(guān)系： rnmod( rn 1 , rn 2 ) （其中 r1mod( a,b) ， r2mod( b, r1 ) ）【問 5】可選用什么結(jié)構(gòu)書寫此算法？

6、【生答】循環(huán)結(jié)構(gòu)?！旧纸M討論】 共分為兩個(gè)小組，分別用直到型和當(dāng)型循環(huán)結(jié)構(gòu)寫算法、畫流程圖和寫偽代碼，并派代表演板流程圖和偽代碼?！净脽羝@示】當(dāng)型循環(huán)結(jié)構(gòu)算法：直到型循環(huán)結(jié)構(gòu)算法：s1輸入兩個(gè)正整數(shù)a,b(a b) ；s1輸入兩個(gè)正整數(shù)a, b(a b) ；s2ra b 的余數(shù)；s2若 mod( a,b)0 ，則輸出最大s3ab,b r；公約數(shù) b；若 r0，則轉(zhuǎn) s3。s3ra b 的余數(shù)；若 r0s4，則輸出最大公約數(shù)a ；ab, br；若 r0，則轉(zhuǎn) s2。s4第 2頁共 6頁10 read x,y20 m x30 ny40 cm-int(m/n)50 mn60 nc直到型循環(huán)結(jié)構(gòu)流

7、程圖：當(dāng)型循環(huán)結(jié)構(gòu)流程圖：輸入 a,b輸入 a,brmod( a, b)brababbrrmod(a, b)nnr 0mod( a,b)0yy輸出 a輸出 b直到型循環(huán)結(jié)構(gòu)偽代碼：當(dāng)型循環(huán)結(jié)構(gòu)偽代碼：10 reada, bread a, b20 rmod( a, b)30ab40br50ifr 0 then goto 2060printawhile mod(a, b)0rmod( a,b)a b b rend whileprint b【師點(diǎn)評(píng)結(jié)果】通過演板的流程圖和偽代碼的對(duì)比，梳理算法，強(qiáng)調(diào)選擇不同的循環(huán)結(jié)構(gòu)導(dǎo)致輸出結(jié)果不同?！驹O(shè)計(jì)意圖】多角度分析問題，加強(qiáng)綜合運(yùn)用知識(shí)能力；通過小組合作探索

8、，激發(fā)學(xué)生興趣，鞏固新知；滲透從具體到抽象的數(shù)學(xué)思想方法，體會(huì)迭代 n的算法思想。4、應(yīng)用輾轉(zhuǎn)相除法算法【練 2】右面一段偽代碼的目的是：()a. 求 x,y 的最小公倍數(shù)b.求 x,y 的最大公約數(shù)c.求 x 被 y 整除的商d.求 y 被 x 整除的商70 if m/n=int(m/n) then goto 4080 print m（練 2）【生答】b【設(shè)計(jì)意圖】會(huì)“識(shí)”直到型循環(huán)語句描述的應(yīng)用輾轉(zhuǎn)相除法求最大公約數(shù)。第 3頁共 6頁【練 3】右面一段偽代碼的輸出結(jié)果是：（）a.1b.429a 1048b 429c.190d.6while mod(a, b) 0【生答】 a【設(shè)計(jì)意圖】會(huì)“

9、識(shí)”當(dāng)型循環(huán)語句描述輾轉(zhuǎn)相除法mod( a,b)并且會(huì)“算”最大公約數(shù)。rab【練 4】設(shè)計(jì)計(jì)算兩個(gè)正整數(shù)bra, b(a b) 的end while最小公倍數(shù)的算法。print b【設(shè)計(jì)意圖】會(huì)“用”輾轉(zhuǎn)相除法的算法語句。(練 3)【師提示】最小公倍數(shù)ab最大公約數(shù)【生演板】【師點(diǎn)評(píng)】易錯(cuò)點(diǎn)為：reada, b(a b)s abreada,b(a b)whilemod ( a, b) 0whilemod (a,b) 0rmod(a, b)rmod( a,b)a babbrbrend whileend whileprintsprintabbb【問 6】：還有其他算法嗎？reada,b( a b

10、)【生答】運(yùn)用案例1 窮舉算法方法x1whilemod ( x, a)0and mod (x,b)0xx1end whileprintx【設(shè)計(jì)意圖】鞏固練習(xí)輾轉(zhuǎn)相除法算法；重溫上節(jié)課孫子問題的窮舉算法思想。第 4頁共 6頁5、課堂小結(jié)：【問 7】今天這節(jié)課主要學(xué)習(xí)了什么內(nèi)容？在問題的解決過程中，我們運(yùn)用了那些數(shù)學(xué)思想？【答】回顧從具體到抽象的研究方法；掌握運(yùn)用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)的最大公約數(shù)；體會(huì)迭代算法思想。【設(shè)計(jì)意圖】 使學(xué)生對(duì)本節(jié)課所學(xué)知識(shí)的結(jié)構(gòu)有一個(gè)清晰的認(rèn)識(shí)， 對(duì)本節(jié)課所用的迭代算法數(shù)學(xué)思想方法有一個(gè)明確的了解。6、布置作業(yè)：必做題：寫出 3428 與 736 的最大公約數(shù)和最小公倍數(shù)的算法；選做題：課本 p23： 4（斐波那契數(shù)列） ；拓展延伸：閱讀課本 p28輾轉(zhuǎn)相除與更相減損【設(shè)計(jì)意圖】必做題讓所有學(xué)生再次鞏固本節(jié)課所學(xué)內(nèi)容；選作題體現(xiàn)迭代算法思想，可供學(xué)生提高之用；閱讀中國古代類似算法更相減損法， 體會(huì)中國古代數(shù)學(xué)對(duì)世界數(shù)學(xué)發(fā)展的貢獻(xiàn)， 增強(qiáng)民族自豪感。7、板書設(shè)計(jì)：輾轉(zhuǎn)相除法1、分析3、流程圖5、演板練習(xí)2、算法4、 偽代碼四、評(píng)價(jià)分析：1、指導(dǎo)思想：新知識(shí)與舊知識(shí)相結(jié)合的原則；掌握知識(shí)與發(fā)展智力、能力相統(tǒng)一的原則；教師的主導(dǎo)作用與學(xué)生的主體作用相結(jié)合的原則。2、本節(jié)課特點(diǎn)：教學(xué)模式打破了傳統(tǒng)的教學(xué)模式，采用了以問題為載