算法案例教案

1、課題：§13算法案例第1課時(shí) 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法一、教學(xué)目標(biāo)：根據(jù)課標(biāo)要求：在學(xué)生學(xué)習(xí)了算法的初步知識(shí)，理解了表示算法的算法步驟、程序框圖和程序三種不同方式以后，再結(jié)合典型算法案例，讓學(xué)生經(jīng)歷設(shè)計(jì)算法解決問題的全過程，體驗(yàn)算法在解決問題中的重要作用，體會(huì)算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達(dá)能力。制定以下三維目標(biāo)：1、知識(shí)與技能理解算法案例的算法步驟和程序框圖.2、過程與方法：引導(dǎo)學(xué)生得出自己設(shè)計(jì)的算法程序.3、情感態(tài)度與價(jià)值觀：體會(huì)算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達(dá)能力.二、重點(diǎn)與難點(diǎn)：重點(diǎn)：引導(dǎo)學(xué)生得出自己設(shè)計(jì)的算法

2、步驟、程序框圖和算法程序.解決策略：通過分析解決具體問題的算法步驟來引導(dǎo)學(xué)生寫出算法，根據(jù)算法畫出程序框圖，再根據(jù)框圖用規(guī)范的語言寫出程序。難點(diǎn)：體會(huì)算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達(dá)能力.解決策略：讓學(xué)生能嚴(yán)謹(jǐn)?shù)匕凑兆约菏浅绦蚩驁D寫出程序。三、學(xué)法與教學(xué)用具：1、學(xué)法：直觀感知、操作確認(rèn)。2、教學(xué)用具：多媒體。四、教學(xué)過程（一）引入課題 大家喜歡打乒乓球吧，由于東、西方文化及身體條件的不同，西方人喜歡橫握拍打球，東方人喜歡直握拍打球，對(duì)于同一個(gè)問題，東、西方人處理問題方式是有所不同的.在小學(xué)，我們學(xué)過求兩個(gè)正整數(shù)的最大公約數(shù)的方法：先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一

3、直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來. 當(dāng)兩個(gè)數(shù)公有的質(zhì)因數(shù)較大時(shí)（如8 251與6 105），使用上述方法求最大公約數(shù)就比較困難.下面我們介紹兩種不同的算法輾轉(zhuǎn)相除法與更相減損術(shù),由此可以體會(huì)東、西方文化的差異. （二）研探新知（1）怎樣用短除法求最大公約數(shù)？（2）怎樣用窮舉法（也叫枚舉法）求最大公約數(shù)？（3）怎樣用輾轉(zhuǎn)相除法求最大公約數(shù)？（4）怎樣用更相減損術(shù)求最大公約數(shù)？討論結(jié)果：（1）短除法求兩個(gè)正整數(shù)的最大公約數(shù)的步驟：先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是兩個(gè)互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.（2）窮舉法（也叫枚舉法）窮舉法求兩個(gè)正整數(shù)的最大公約數(shù)的

4、解題步驟：從兩個(gè)數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù).（3）輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)，其算法步驟可以描述如下：第一步，給定兩個(gè)正整數(shù)m，n.第二步，求余數(shù)r：計(jì)算m除以n，將所得余數(shù)存放到變量r中.第三步，更新被除數(shù)和余數(shù)：m=n，n=r.第四步，判斷余數(shù)r是否為0.若余數(shù)為0，則輸出結(jié)果；否則轉(zhuǎn)向第二步繼續(xù)循環(huán)執(zhí)行.如此循環(huán)，直到得到結(jié)果為止. 這種算法是由歐幾里得在公元前300年左右首先提出的，因而又叫歐幾里得算法.（4）更相減損術(shù)我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù). 九章算術(shù)是中國古代的數(shù)學(xué)專著，其中的“更

5、相減損術(shù)”也可以用來求兩個(gè)數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”翻譯為現(xiàn)代語言如下：第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)，若是，用2約簡；若不是，執(zhí)行第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）或這個(gè)數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).（三）范例分析例1 用輾轉(zhuǎn)相除法求8 251與6 105的最大公約數(shù),寫出算法分析，畫出程序框圖，寫出算法程序.解：用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)：8 251=6 105×1

6、+2 146.由此可得，6 105與2 146的公約數(shù)也是8 251與6 105的公約數(shù)，反過來，8 251與6 105的公約數(shù)也是6 105與2 146的公約數(shù)，所以它們的最大公約數(shù)相等.對(duì)6 105與2 146重復(fù)上述步驟：6 105=2 146×2+1 813.同理，2 146與1 813的最大公約數(shù)也是6 105與2 146的最大公約數(shù).繼續(xù)重復(fù)上述步驟：2 146=1 813×1+333，1 813=333×5+148，333=148×2+37，148=37×4.最后的除數(shù)37是148和37的最大公約數(shù)，也就是8 251與6 105的

7、最大公約數(shù).這就是輾轉(zhuǎn)相除法.由除法的性質(zhì)可以知道，對(duì)于任意兩個(gè)正整數(shù)，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉(zhuǎn)相除法求出兩個(gè)正整數(shù)的最大公約數(shù).算法分析：從上面的例子可以看出，輾轉(zhuǎn)相除法中包含重復(fù)操作的步驟，因此可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法.算法步驟如下：第一步，給定兩個(gè)正整數(shù)m，n.第二步，計(jì)算m除以n所得的余數(shù)為r.第三步，m=n，n=r.第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.程序框圖如右圖：程序：INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND例2 用更相減損術(shù)求98與63的最大公約數(shù).解：由于

8、63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，如下圖所示.98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98和63的最大公約數(shù)等于7.前面我們學(xué)習(xí)了輾轉(zhuǎn)相除法與更相減損術(shù)，現(xiàn)在我們來學(xué)習(xí)一種新的算法：秦九韶算法.（1）怎樣求多項(xiàng)式f(x)=x5+x4+x3+x2+x+1當(dāng)x=5時(shí)的值呢？一個(gè)自然的做法就是把5代入多項(xiàng)式f(x)，計(jì)算各項(xiàng)的值，然后把它們加起來，這時(shí)，我們一共做了1+2+3+4=10次乘法運(yùn)算，5次加法運(yùn)算.另一種做法是先計(jì)算x2的值，然后依次計(jì)算x2·x，（x2·x）·x，（x2·x）&

9、#183;x）·x的值，這樣每次都可以利用上一次計(jì)算的結(jié)果，這時(shí)，我們一共做了4次乘法運(yùn)算，5次加法運(yùn)算.第二種做法與第一種做法相比，乘法的運(yùn)算次數(shù)減少了，因而能夠提高運(yùn)算效率，對(duì)于計(jì)算機(jī)來說，做一次乘法運(yùn)算所用的時(shí)間比做一次加法運(yùn)算要長得多，所以采用第二種做法，計(jì)算機(jī)能更快地得到結(jié)果.（2）上面問題有沒有更有效的算法呢？我國南宋時(shí)期的數(shù)學(xué)家秦九韶（約12021261）在他的著作數(shù)書九章中提出了下面的算法：把一個(gè)n次多項(xiàng)式f(x)=anxn+an-1xn-1+a1x+a0改寫成如下形式：f(x)=anxn+an-1xn-1+a1x+a0=（anxn-1+an-1xn-2+a1）x+

10、a0=（anxn-2+an-1xn-3+a2）x+a1)x+a0=（anx+an-1）x+an-2）x+a1）x+a0.求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，即v1=anx+an-1，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即v2=v1x+an-2，v3=v2x+an-3，vn=vn-1x+a0，這樣，求n次多項(xiàng)式f（x）的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值.上述方法稱為秦九韶算法.直到今天，這種算法仍是多項(xiàng)式求值比較先進(jìn)的算法.（3）計(jì)算機(jī)的一個(gè)很重要的特點(diǎn)就是運(yùn)算速度快，但即便如此，算法好壞的一個(gè)重要標(biāo)志仍然是運(yùn)算的次數(shù).如果一個(gè)算法從理論上需要超出計(jì)算機(jī)允許范圍內(nèi)的運(yùn)算次數(shù)，那么這

11、樣的算法就只能是一個(gè)理論的算法.例3 已知一個(gè)5次多項(xiàng)式為f（x）=5x5+2x4+3.5x3-2.6x2+1.7x-0.8，用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x=5時(shí)的值.解：根據(jù)秦九韶算法，把多項(xiàng)式改寫成如下形式：f(x)=（(5x+2)x+3.5)x-2.6)x+1.7)x-0.8，按照從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)x=5時(shí)的值：v0=5；v1=5×5+2=27;v2=27×5+3.5=138.5;v3=138.5×5-2.6=689.9;v4=689.9×5+1.7=3 451.2;v5=3 415.2×5-0.8=17 255.2;所以

12、，當(dāng)x=5時(shí)，多項(xiàng)式的值等于17 255.2.算法分析：觀察上述秦九韶算法中的n個(gè)一次式，可見vk的計(jì)算要用到vk-1的值，若令v0=an，我們可以得到下面的公式：這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn).算法步驟如下：第一步，輸入多項(xiàng)式次數(shù)n、最高次的系數(shù)an和x的值.第二步，將v的值初始化為an，將i的值初始化為n-1.第三步，輸入i次項(xiàng)的系數(shù)ai.第四步，v=vx+ai,i=i-1.第五步，判斷i是否大于或等于0.若是，則返回第三步；否則，輸出多項(xiàng)式的值v.程序框圖如右圖：程序：INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1

13、WHILE i=0 PRINT “i=”；i INPUT “ai=”；a v=v*x+a i=i-1WENDPRINT vEND（四）隨堂練習(xí) P45 練習(xí) 1、2（五）歸納總結(jié)（1）用輾轉(zhuǎn)相除法求最大公約數(shù).（2）用更相減損術(shù)求最大公約數(shù).（3）.秦九韶算法的方法和步驟.以及計(jì)算機(jī)程序框圖.（六）作業(yè)布置1、P48 習(xí)題1.3 A組1、2 2、完成課后鞏固作業(yè)（八）五、教學(xué)反思：_1.3 算法案例第2課時(shí) 進(jìn)位制一、教學(xué)目標(biāo)：根據(jù)課標(biāo)要求：掌握不同進(jìn)制之間的相互轉(zhuǎn)化，會(huì)用程序描述不同進(jìn)制之間的轉(zhuǎn)化，體會(huì)數(shù)學(xué)的轉(zhuǎn)化思想，制定以下三維目標(biāo)：1、知識(shí)與技能學(xué)生理解各種進(jìn)位制與十進(jìn)制之間轉(zhuǎn)換的規(guī)律，

14、會(huì)利用十進(jìn)制與各種進(jìn)制之間的聯(lián)系進(jìn)行各種進(jìn)位制之間的轉(zhuǎn)換。2、過程與方法學(xué)生經(jīng)歷得出各種進(jìn)位制與十進(jìn)制之間轉(zhuǎn)換的規(guī)律的過程，進(jìn)一步掌握進(jìn)位制之間轉(zhuǎn)換的方法。3、情感、態(tài)度與價(jià)值觀學(xué)生通過合作完成任務(wù)后，領(lǐng)悟十進(jìn)制，二進(jìn)制的特點(diǎn)，了解計(jì)算機(jī)的電路與二進(jìn)制的聯(lián)系，進(jìn)一步認(rèn)識(shí)到計(jì)算機(jī)與數(shù)學(xué)的聯(lián)系，培養(yǎng)他們的合作精神和嚴(yán)謹(jǐn)?shù)膽B(tài)度。二、教學(xué)重點(diǎn)、難點(diǎn)重點(diǎn)：各進(jìn)位制之間的轉(zhuǎn)換。解決策略：讓學(xué)生弄懂各進(jìn)位制的特點(diǎn)和聯(lián)系，再搭配習(xí)題講解。難點(diǎn)：“除k取余法”的理解。解決策略：先給出具體的例子講解，再延伸到一般的情況。三、學(xué)法與教學(xué)用具1、學(xué)法：講授法、歸納法、討論法。2、教學(xué)用具：多媒體，投影儀四、教學(xué)過程（

15、一）引入課題 在日常生活中，我們最熟悉、最常用的是十進(jìn)制，據(jù)說這與古人曾以手指計(jì)數(shù)有關(guān)，愛好天文學(xué)的古人也曾經(jīng)采用七進(jìn)制、十二進(jìn)制、六十進(jìn)制，至今我們?nèi)匀皇褂靡恢芷咛?、一年十二個(gè)月、一小時(shí)六十分的歷法.今天我們來學(xué)習(xí)一下進(jìn)位制.（二）研探新知進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的計(jì)數(shù)系統(tǒng)，約定滿二進(jìn)一，就是二進(jìn)制；滿十進(jìn)一，就是十進(jìn)制；滿十二進(jìn)一，就是十二進(jìn)制；滿六十進(jìn)一，就是六十進(jìn)制等等.也就是說：“滿幾進(jìn)一”就是幾進(jìn)制，幾進(jìn)制的基數(shù)（都是大于1的整數(shù)）就是幾.在日常生活中，我們最熟悉、最常用的是十進(jìn)制，據(jù)說這與古人曾以手指計(jì)數(shù)有關(guān)，愛好天文學(xué)的古人也曾經(jīng)采用七進(jìn)制、十二進(jìn)制、六十進(jìn)制，至今

16、我們?nèi)匀皇褂靡恢芷咛?、一年十二個(gè)月、一小時(shí)六十分的歷法.十進(jìn)制使用0 9十個(gè)數(shù)字.計(jì)數(shù)時(shí)，幾個(gè)數(shù)字排成一行，從右起，第一位是個(gè)位，個(gè)位上的數(shù)字是幾，就表示幾個(gè)一；第二位是十位，十位上的數(shù)字是幾，就表示幾個(gè)十；接著依次是百位、千位、萬位例如：十進(jìn)制數(shù)3 721中的3表示3個(gè)千，7表示7個(gè)百，2表示2個(gè)十，1表示1個(gè)一.于是，我們得到下面的式子：3 721=3×103+7×102+2×101+1×100.與十進(jìn)制類似，其他的進(jìn)位制也可以按照位置原則計(jì)數(shù).由于每一種進(jìn)位制的基數(shù)不同，所用的數(shù)字個(gè)數(shù)也不同.如二進(jìn)制用0和1兩個(gè)數(shù)字，七進(jìn)制用06七個(gè)數(shù)字.一般地，

17、若k是一個(gè)大于1的整數(shù)，那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式 anan-1a1a0（k）（0ank，0an-1，a1，a0k).其他進(jìn)位制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)的冪的乘積之和的形式，如110 011（2）=1×25+1×24+0×23+0×22+1×21+1×20， 7 342（8）=7×83+3×82+4×81+2×80.非十進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)比較簡單，只要計(jì)算下面的式子值即可：anan-1a1a0(k)=an×kn+an-1×kn-1+

18、a1×k+a0.第一步：從左到右依次取出k進(jìn)制數(shù)anan-1a1a0(k)各位上的數(shù)字，乘以相應(yīng)的k的冪，k的冪從n開始取值，每次遞減1，遞減到0，即an×kn,an-1×kn-1,a1×k,a0×k0；第二步：把所得到的乘積加起來，所得的結(jié)果就是相應(yīng)的十進(jìn)制數(shù).關(guān)于進(jìn)位制的轉(zhuǎn)換，教科書上以十進(jìn)制和二進(jìn)制之間的轉(zhuǎn)換為例講解，并推廣到十進(jìn)制和其他進(jìn)制之間的轉(zhuǎn)換.這樣做的原因是，計(jì)算機(jī)是以二進(jìn)制的形式進(jìn)行存儲(chǔ)和計(jì)算數(shù)據(jù)的，而一般我們傳輸給計(jì)算機(jī)的數(shù)據(jù)是十進(jìn)制數(shù)據(jù)，因此計(jì)算機(jī)必須先將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)，再處理，顯然運(yùn)算后首次得到的結(jié)果為二進(jìn)制數(shù)，

19、同時(shí)計(jì)算機(jī)又把運(yùn)算結(jié)果由二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)輸出.1°十進(jìn)制數(shù)轉(zhuǎn)換成非十進(jìn)制數(shù)把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)，教科書上提供了“除2取余法”，我們可以類比得到十進(jìn)制數(shù)轉(zhuǎn)換成k進(jìn)制數(shù)的算法“除k取余法”.2°非十進(jìn)制之間的轉(zhuǎn)換一個(gè)自然的想法是利用十進(jìn)制作為橋梁.教科書上提供了一個(gè)二進(jìn)制數(shù)據(jù)與16進(jìn)制數(shù)據(jù)之間的互化的方法，也就是先由二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)，再由十進(jìn)制數(shù)轉(zhuǎn)化成為16進(jìn)制數(shù).（三）范例分析例1 把二進(jìn)制數(shù)110 011(2)化為十進(jìn)制數(shù).解：110 011(2)=1×25+1×24+0×23+0×22+1×21+1

20、5;20=1×32+1×16+1×2+1=51.點(diǎn)評(píng)：先把二進(jìn)制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式，再按照十進(jìn)制的運(yùn)算規(guī)則計(jì)算出結(jié)果.例2設(shè)計(jì)一個(gè)算法，把k進(jìn)制數(shù)a（共有n位）化為十進(jìn)制數(shù)b.算法分析：從例1的計(jì)算過程可以看出，計(jì)算k進(jìn)制數(shù)a的右數(shù)第i位數(shù)字ai與ki-1的乘積ai·ki-1，再將其累加，這是一個(gè)重復(fù)操作的步驟.所以，可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法. 算法步驟如下：第一步，輸入a，k和n的值.第二步，將b的值初始化為0，i的值初始化為1.第三步，b=b+ai·ki-1，i=i+1.第四步，判斷in是否成立.若是，則執(zhí)行第五步；

21、否則，返回第三步.第五步，輸出b的值.程序框圖如右圖：程序：INPUT “a,k，n=”；a，k，nb=0i=1t=a MOD 10DO b=b+t*k（i-1） a=a10 t=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND例3 把89化為二進(jìn)制數(shù).解：根據(jù)二進(jìn)制數(shù)“滿二進(jìn)一”的原則，可以用2連續(xù)去除89或所得商，然后取余數(shù).具體計(jì)算方法如下：因?yàn)?9=2×44+1，44=2×22+0，22=2×11+0，11=2×5+1，5=2×2+1，2=2×1+0，1=2×0+1，所以89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1=2×（2×（2×（2×（22+1）+1）+0）+0）+1=1×26+0×25+1×24+1×23+0×22+0×21+1×20=1 011 001(2).這種算法叫做除2取余法，還可以用右邊的除法算式表示：把上式中各步所得的余數(shù)從下到上排列，得到89=1 011 001(2).上述方法也可以推廣為把十進(jìn)制數(shù)化為