13算法案例(教學(xué)案)

1、1.3算法案例【教學(xué)目標(biāo)】：1.理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊(yùn)含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析。2.根本能根據(jù)算法語句與程序框圖的知識(shí)設(shè)計(jì)完整的程序框圖并寫出算法程序?！窘虒W(xué)重難點(diǎn)】：重點(diǎn)：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法。難點(diǎn)：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語言。 【教學(xué)過程】：情境導(dǎo)入：1.教師首先提出問題：在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識(shí)，你能求出18與30的公約數(shù)嗎2.接著教師進(jìn)一步提出問題，我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)比方求8251與6

2、105的最大公約數(shù)這就是我們這一堂課所要探討的內(nèi)容。新知探究：1.輾轉(zhuǎn)相除法例1 求兩個(gè)正數(shù)8251和6105的最大公約數(shù)。分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識(shí)即可求出最大公約數(shù)解：82516105×12146顯然8251的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與2146的最大公約數(shù)。61052146×2181321461813×#215;5148333148×23714837&#

3、215;40那么37為8251與6105的最大公約數(shù)。以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：第一步：用較大的數(shù)m除以較小的數(shù)n得到一個(gè)商q0和一個(gè)余數(shù)r0；第二步：假設(shè)r00，那么n為m，n的最大公約數(shù)；假設(shè)r00，那么用除數(shù)n除以余數(shù)r0得到一個(gè)商q1和一個(gè)余數(shù)r1；第三步：假設(shè)r10，那么r1為m，n的最大公約數(shù)；假設(shè)r10，那么用除數(shù)r0除以余數(shù)r1得到一個(gè)商q2和一個(gè)余數(shù)r2；依次計(jì)算直至rn0，此時(shí)所得到的rn-1即為所求的最大公約數(shù)。練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與2072

4、3的最大公約數(shù)答案：532.更相減損術(shù)我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母·子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯出來為：第一步：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。假設(shè)是，用2約簡；假設(shè)不是，執(zhí)行第二步。第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，那么這個(gè)數(shù)等數(shù)就是所求的最大公約數(shù)。例2 用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：98633563352

5、83528728721217141477所以，98與63的最大公約數(shù)是7。練習(xí)：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)。答案：12比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：1都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。2從結(jié)果表達(dá)形式來看，輾轉(zhuǎn)相除法表達(dá)結(jié)果是以相除余數(shù)為0那么得到，而更相減損術(shù)那么以減數(shù)與差相等而得到3.秦九韶算法秦九韶計(jì)算多項(xiàng)式的方法令，那么有，其中.這樣，我們便可由依次求出；顯然，用秦九韶算法求n次多項(xiàng)式的值時(shí)只需要做n次乘法和n次加法運(yùn)算 4.進(jìn)位制進(jìn)位制

6、是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值.可使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進(jìn)位制，簡稱n進(jìn)制.現(xiàn)在最常用的是十進(jìn)制，通常使用10個(gè)阿拉伯?dāng)?shù)字0-9進(jìn)行記數(shù).對于任何一個(gè)數(shù)，我們可以用不同的進(jìn)位制來表示.比方：十進(jìn)數(shù)57，可以用二進(jìn)制表示為111001，也可以用八進(jìn)制表示為71、用十六進(jìn)制表示為39，它們所代表的數(shù)值都是一樣的.表示各種進(jìn)位制數(shù)一般在數(shù)字右下腳加注來表示,如111001(2)表示二進(jìn)制數(shù),34(5)表示5進(jìn)制數(shù).1.k進(jìn)制轉(zhuǎn)換為十進(jìn)制的方法：， 2.十進(jìn)制轉(zhuǎn)化為k進(jìn)制數(shù)b的步驟為：第一步，將給定的十進(jìn)制整數(shù)除以基數(shù)k，余數(shù)便是等值的k進(jìn)制的最低位；第

7、二步，將上一步的商再除以基數(shù)k，余數(shù)便是等值的k進(jìn)制數(shù)的次低位；第三步，重復(fù)第二步，直到最后所得的商等于0為止，各次所得的余數(shù)，便是k進(jìn)制各位的數(shù)，最后一次余數(shù)是最高位，即除k取余法.要點(diǎn)詮釋：1、在k進(jìn)制中，具有k個(gè)數(shù)字符號(hào).如二進(jìn)制有0，1兩個(gè)數(shù)字.2、在k進(jìn)制中，由低位向高位是按“逢k進(jìn)一的規(guī)那么進(jìn)行計(jì)數(shù).3、非k進(jìn)制數(shù)之間的轉(zhuǎn)化一般應(yīng)先轉(zhuǎn)化成十進(jìn)制，再將這個(gè)十進(jìn)制數(shù)轉(zhuǎn)化為另一種進(jìn)制的數(shù)，有的也可以相互轉(zhuǎn)化.【反響測評】：求三個(gè)數(shù)的最大公約數(shù)可以先求出兩個(gè)數(shù)的最大公約數(shù)，第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。2用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)，把98

8、和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 9863356335283528728721217211477所以，98和63的最大公約數(shù)等于7 3一個(gè)五次多項(xiàng)式為用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x = 5的值。解：將多項(xiàng)式變形：按由里到外的順序，依此計(jì)算一次多項(xiàng)式當(dāng)x = 5時(shí)的值：，所以，當(dāng)x = 5時(shí)，多項(xiàng)式的值等于17255.24將二進(jìn)制數(shù)110011(2)化成十進(jìn)制數(shù)解：根據(jù)進(jìn)位制的定義可知所以，1100112=51。 【板書設(shè)計(jì)】：1.3算法案例一、輾轉(zhuǎn)相除法例1二、更相減損術(shù)例2三、秦九韶算法四、進(jìn)位制五、反響測評：小結(jié)作業(yè)1.3算法案例課前預(yù)習(xí)學(xué)案一、預(yù)習(xí)目標(biāo)1、理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊(yùn)含的數(shù)

9、學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析。2、理解秦九韶算法的思想。二、預(yù)習(xí)內(nèi)容什么是進(jìn)位制最常見的進(jìn)位制是什么除此之外還有哪些常見的進(jìn)位制請舉例說明三、提出疑惑思考：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)課內(nèi)探究學(xué)案一、 學(xué)習(xí)目標(biāo)1. 會(huì)用輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法。2. 會(huì)利用秦九韶算法求多項(xiàng)式的值。3各進(jìn)位制之間能靈活轉(zhuǎn)化。二、學(xué)習(xí)重難點(diǎn)：重點(diǎn)：輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法和秦九韶算法求多項(xiàng)式的值。難點(diǎn)：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語言。三、 學(xué)習(xí)過程輾轉(zhuǎn)相除法思路：可以利用除法將大數(shù)化小,找兩數(shù)的最大公約數(shù).(適于兩數(shù)較大時(shí))(1)用較大的數(shù)m

10、除以較小的數(shù)n得到一個(gè)商和一個(gè)余數(shù)；(2)假設(shè)0,那么n為m,n的最大公約數(shù)；假設(shè)0,那么用除數(shù)n除以余數(shù)得到一個(gè)和一個(gè)余數(shù)；(3)假設(shè)0,那么為m,n的最大公約數(shù);假設(shè)0,那么用除數(shù)除以余數(shù)得到一個(gè)商和一個(gè)余數(shù)；依次計(jì)算直至0，此時(shí)所得到的即為所求的最大公約數(shù).例題1：求兩個(gè)正數(shù)1424和801的最大公約數(shù).以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法，也叫歐幾里德算法. 由上述步驟可以看出，輾轉(zhuǎn)相除法中的除法是一個(gè)反復(fù)執(zhí)行的步驟，且執(zhí)行次數(shù)由余數(shù) 是否等于0來決定,所以可把它看成一循環(huán)體,寫出輾轉(zhuǎn)相除法完整的程序框圖和程序語言.教學(xué)更相減損術(shù)：我國早期也有求最大公約數(shù)問題的算法，就是更相減損術(shù)

11、. 在 九章算 術(shù) 中有更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置 分母子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之. 翻譯為：(1) 任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù). 假設(shè)是，用2約簡；假設(shè)不是，執(zhí) 行第二步.(2) 以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小 數(shù). 繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，那么這個(gè)數(shù)等數(shù)就是所求的最 大公約數(shù).例題2. 用更相減損術(shù)求91和49的最大公約數(shù).秦九韶算法：1設(shè)計(jì)求多項(xiàng)式當(dāng)x=5時(shí)的值的算法，并寫出程序。2有沒有更高效的算法能否探求更好的算法，來解決任意多項(xiàng)式的求解問題引導(dǎo)學(xué)生把多項(xiàng)式變形為：并提問：

12、從內(nèi)到外，如果把每一個(gè)括號(hào)都看成一個(gè)常數(shù)，那么變形后的式子中有哪些“一次式x的系數(shù)依次是什么用秦九韶算法求多項(xiàng)式的值，與多項(xiàng)式組成有直接關(guān)系嗎用秦九韶算法計(jì)算上述多項(xiàng)式的值，需要多少次乘法運(yùn)算和多少次加法運(yùn)算秦九韶算法適用于一般的多項(xiàng)式的求值問題嗎怎樣用程序框圖表示秦九韶算法觀察秦九韶算法的數(shù)學(xué)模型，計(jì)算時(shí)要用到的值，假設(shè)令，我們可以得到下面的遞推公式：這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟，可以用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。請畫出程序框圖。例題3一個(gè)五次多項(xiàng)式為用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x = 5的值。進(jìn)位制：我們了解十進(jìn)制嗎所謂的十進(jìn)制，它是如何構(gòu)成的其它進(jìn)位制的數(shù)又是如何的呢進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算

13、方便而約定的記數(shù)系統(tǒng)。進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進(jìn)位制，簡稱n進(jìn)制。例題4將二進(jìn)制數(shù)110011(2)化成十進(jìn)制數(shù)精講點(diǎn)撥：1求兩個(gè)正數(shù)8251和2146;228和1995;5280和12155的最大公約數(shù). 2 求兩個(gè)正數(shù)8251和2146的最大公約數(shù).3.用秦九韶算法計(jì)算多項(xiàng)式在x=-4時(shí)的值時(shí),V3的值為 ： 反思總結(jié)：比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別(1)都是求的方法，計(jì)算上輾轉(zhuǎn)相除法以法為主，更相減損術(shù)以法為主，計(jì)算次數(shù)上法計(jì)算次數(shù)相對較少，特別當(dāng)兩個(gè)數(shù)字時(shí)計(jì)算次數(shù)的區(qū)別較明顯(2)從結(jié)果表達(dá)形式來看，輾轉(zhuǎn)相除法表達(dá)結(jié)果是以那么得到，而更相減損術(shù)那么以而得到(3)通過對秦九韶算法的學(xué)習(xí)，你對算法本身有哪些進(jìn)一步認(rèn)