第一篇：《算法案例：秦九韶算法》教學(xué)教案

秦九韶算法

學(xué)習(xí)目標(biāo)

1.了解秦九韶算法的計算過程，并理解利用秦九韶算法可以減少計算次數(shù)提高計算效率的實質(zhì)。

2.掌握數(shù)據(jù)排序的原理能使用直接排序法與冒泡排序法給一組數(shù)據(jù)排序，進(jìn)而能設(shè)計冒泡排序法的程序框圖及程序，理解數(shù)學(xué)算法與計算機(jī)算法的區(qū)別，理解計算機(jī)對數(shù)學(xué)的輔助作用。學(xué)習(xí)重難點(diǎn)

重點(diǎn)：1.秦九韶算法的特點(diǎn)

2.兩種排序法的排序步驟及計算機(jī)程序設(shè)計 難點(diǎn)：1.秦九韶算法的先進(jìn)性理解

2.排序法的計算機(jī)程序設(shè)計

學(xué)法與學(xué)習(xí)用具

學(xué)法：1.探究秦九韶算法對比一般計算方法中計算次數(shù)的改變，體會科學(xué)的計算。

2.模仿排序法中數(shù)字排序的步驟，理解計算機(jī)計算的一般步驟，領(lǐng)會數(shù)學(xué)計算在計算機(jī)上實施的要求。

學(xué)習(xí)用具：電腦，計算器，圖形計算器 學(xué)習(xí)設(shè)想

（一）創(chuàng)設(shè)情景，揭示課題

我們已經(jīng)學(xué)過了多項式的計算，下面我們計算一下多項式

f(x)?x5?x4?x3?x2?x?1當(dāng)x?5時的值，并統(tǒng)計所做的計算的種類及計算次數(shù)。

根據(jù)我們的計算統(tǒng)計可以得出我們共需要10次乘法運(yùn)算，5次加法運(yùn)算。我們把多項式變形為：f(x)?x2(1?x(1?x(1?x)))?x?1再統(tǒng)計一下計算當(dāng)x?5時的值時需要的計算次數(shù)，可以得出僅需4次乘法和5次加法運(yùn)算即可得出結(jié)果。顯然少了6次乘法運(yùn)算。這種算法就叫秦九韶算法。

（二）研探新知

/ 4

1.秦九韶計算多項式的方法

f(x)?anxn?an?1xn?1?an?2xn?2???a1x?a0?(anxn?1?an?1xn?2?an?2xn?3???a1)x?a0?((anxn?2?an?1xn?3???a2)x?a1)x?a0????(?((anx?an?1)x?an?2)x???a1)?a0例1 已知一個5次多項式為f(x)?5x5?2x4?3.5x3?2.6x2?1.7x?0.8 用秦九韶算法求這個多項式當(dāng)x?5時的值。解：略

思考：（1）例1計算時需要多少次乘法計算？多少次加法計算？

（2）在利用秦九韶算法計算n次多項式當(dāng)x?x0時需要多少次乘法計算和多少次加法計算？

練習(xí)：利用秦九韶算法計算f(x)?0.83x5?0.41x4?0.16x3?0.33x2?0.5x?1 當(dāng)x?5時的值，并統(tǒng)計需要多少次乘法計算和多少次加法計算？ 例2 設(shè)計利用秦九韶算法計算5次多項式

f(x)?a5x5?a4x4?a3x3?a2x2?a1x?a0當(dāng)x?x0時的值的程序框圖。解：程序框圖如下：

/ 4

開始輸入f(x)的系數(shù)：a1,a2,a3,a4,a5輸入x0n=1v=a5 n=n+1v=v x0+a5-nn≤5是否輸出v結(jié)束

練習(xí)：利用程序框圖試編寫B(tài)ASIC程序并在計算機(jī)上測試自己的程序。

2.排序

在信息技術(shù)課中我們學(xué)習(xí)過電子表格,電子表格對分?jǐn)?shù)的排序非常簡單,那么電子計算機(jī)是怎么對數(shù)據(jù)進(jìn)行排序的呢? 閱讀課本P30—P31面的內(nèi)容,回答下面的問題:(1)排序法中的直接插入排序法與冒泡排序法的步驟有什么區(qū)別?(2)冒泡法排序中對5個數(shù)字進(jìn)行排序最多需要多少趟?(3)在冒泡法排序?qū)?個數(shù)字進(jìn)行排序的每一趟中需要比較大小幾次? 游戲:5位同學(xué)每人拿一個數(shù)字牌在講臺上演示冒泡排序法對5個數(shù)據(jù)4,11,7,9,6排序的過程,讓學(xué)生通過觀察敘述冒泡排序法的主要步驟.并結(jié)合步驟解決例3的問題.例3 用冒泡排序法對數(shù)據(jù)7,5,3,9,1從小到大進(jìn)行排序

/ 4

練習(xí):寫出用冒泡排序法對5個數(shù)據(jù)4,11,7,9,6排序的過程中每一趟排序的結(jié)果.例4 設(shè)計冒泡排序法對5個數(shù)據(jù)進(jìn)行排序的程序框圖.解: 程序框圖如下:

開始輸入a1,a2,a3,a4,a5r=1i=1ai>ai+1是否x=aiai=ai+1ai+1=xi=i+1r=r+1i=5否是r=5否是輸出a1,a2,a3,a4,a5結(jié)束 思考:直接排序法的程序框圖如何設(shè)計?可否把上述程序框圖轉(zhuǎn)化為程序? 練習(xí):用直接排序法對例3中的數(shù)據(jù)從小到大排序 3.小結(jié):(1)秦九韶算法計算多項式的值及程序設(shè)計

(2)數(shù)字排序法中的常見的兩種排序法直接插入排序法與冒泡排序法(3)冒泡法排序的計算機(jī)程序框圖設(shè)計

/ 4

第二篇：P037算法案例---秦九韶算法教案（共）

清華同方教育技術(shù)研究院數(shù)學(xué)所

2013/04/16 Tuesday 09:41 算法案例---秦九韶算法

教學(xué)要求：了解秦九韶算法的計算過程，并理解利用秦九韶算法可以減少計算次數(shù)、提高計算效率的實質(zhì)；理解數(shù)學(xué)算法與計算機(jī)算法的區(qū)別，理解計算機(jī)對數(shù)學(xué)的輔助作用.教學(xué)重點(diǎn)：秦九韶算法的特點(diǎn)及其程序設(shè)計.教學(xué)難點(diǎn)：秦九韶算法的先進(jìn)性理解及其程序設(shè)計.教學(xué)過程：

一、復(fù)習(xí)準(zhǔn)備：

1.分別用輾轉(zhuǎn)相除法和更相減損術(shù)求出兩個正數(shù)623和1513的最大公約數(shù).2.設(shè)計一個求多項式

f(x)?2x?5x?4x?3x?6x?75432當(dāng)x?5時的值的算法.（學(xué)生自己提出一般的解決方案：將x?5代入多項式進(jìn)行計算即可）

提問：上述算法在計算時共用了多少次乘法運(yùn)算？多少次加法運(yùn)算？此方案有何優(yōu)缺點(diǎn)？(上述算法一共做了5＋4＋3＋2＋1＝15次乘法運(yùn)算，5次加法運(yùn)算.優(yōu)點(diǎn)是簡單、易懂；缺點(diǎn)是不通用，不能解決任意多項式的求值問題，而且計算效率不高.)

二、講授新課： 1.教學(xué)秦九韶算法：

① 提問：在計算x的冪值時，可以利用前面的計算結(jié)果，以減少計算量，即先計算x，2然后依次計算x?x，(x?x)?x，((x?x)?x)?x的值，這樣計算上述多項式的值，一共需

222要多少次乘法，多少次加法?（上述算法一共做了4次乘法運(yùn)算，5次加法運(yùn)算）

② 結(jié)論：第二種做法與第一種做法相比，乘法的運(yùn)算次數(shù)減少了，因而能提高運(yùn)算效率，而且對于計算機(jī)來說，做一次乘法所需的運(yùn)算時間比做一次加法要長得多，因此第二種做法能更快地得到結(jié)果.③ 更有效的一種算法是： 將f(?5多x)?4項

2x?式

3變

5x?2形

4x?為

3x：

?6x?7，依次計算2?5?5?5，5?5?4?21，21?5?3?108，108?5?6?534，534?5?7?2677

故f(5)?2677.――這種算法就是“秦九韶算法”.（注意變形，強(qiáng)調(diào)格式）

版權(quán)所有，盜版必究

第1頁，共2頁 清華同方教育技術(shù)研究院數(shù)學(xué)所

2013/04/16 Tuesday 09:41 ④ 練習(xí)：用秦九韶算法求多項式f(x)?2x?x?3x?5x?1當(dāng)x?4時的值.（學(xué)生板書?師生共評?教師提問：上述算法共需多少次乘法運(yùn)算？多少次加法運(yùn)算？）

⑤ 如何用秦九韶算法完成一般多項式題？

改f(x?anx?an?1xnn?1432f(x)?anx?an?1xnn?1???a1x?a0的求值問

寫???ax?a??)anx?an?x?an?x???ax?a1：

.首先計算最內(nèi)層括號內(nèi)一次多項式的值，即次多項式的值，即v2?v1x?an?2v1?anx?an?1，然后由內(nèi)向外逐層計算一

.，v3?v2x?an?3，?，vn?vn?1x?a0⑥ 結(jié)論：秦九韶算法將求n次多項式的值轉(zhuǎn)化為求n個一次多項式的值，整個過程只需n次乘法運(yùn)算和n次加法運(yùn)算；觀察上述n個一次式，可發(fā)出

vk的計算要用到

vk?1的值，?v0?an,?v?vk?1x?an?k(k?1,2,?,n)v0?an若令，可得到下列遞推公式：?k.這是一個反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實現(xiàn).⑦ 練習(xí)：用秦九韶算法求多項式x?5時的值并畫出程序框圖.f(x)?5x?2x?3.5x?2.6x?1.7x?0.85432當(dāng)2.小結(jié)：秦九韶算法的特點(diǎn)及其程序設(shè)計

三、鞏固練習(xí)：

1、練習(xí)：教材P35第2題

2、作業(yè)：教材P36第2題

版權(quán)所有，盜版必究

第2頁，共2頁

第三篇：算法案例教案

課題：§1．3算法案例

第1課時 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法

一、教學(xué)目標(biāo)：

根據(jù)課標(biāo)要求：在學(xué)生學(xué)習(xí)了算法的初步知識，理解了表示算法的算法步驟、程序框圖和程序三種不同方式以后，再結(jié)合典型算法案例，讓學(xué)生經(jīng)歷設(shè)計算法解決問題的全過程，體驗算法在解決問題中的重要作用，體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達(dá)能力。制定以下三維目標(biāo)：

1、知識與技能

理解算法案例的算法步驟和程序框圖.2、過程與方法：

引導(dǎo)學(xué)生得出自己設(shè)計的算法程序.3、情感態(tài)度與價值觀：

體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達(dá)能力.二、重點(diǎn)與難點(diǎn)：

重點(diǎn)：引導(dǎo)學(xué)生得出自己設(shè)計的算法步驟、程序框圖和算法程序.解決策略：通過分析解決具體問題的算法步驟來引導(dǎo)學(xué)生寫出算法，根據(jù)算法畫出程序框圖，再根據(jù)框圖用規(guī)范的語言寫出程序。

難點(diǎn)：體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達(dá)能力.解決策略：讓學(xué)生能嚴(yán)謹(jǐn)?shù)匕凑兆约菏浅绦蚩驁D寫出程序。

三、學(xué)法與教學(xué)用具：

1、學(xué)法：直觀感知、操作確認(rèn)。

2、教學(xué)用具：多媒體。

四、教學(xué)過程

（一）引入課題

大家喜歡打乒乓球吧，由于東、西方文化及身體條件的不同，西方人喜歡橫握拍打球，東方人喜歡直握拍打球，對于同一個問題，東、西方人處理問題方式是有所不同的.在小學(xué)，我們學(xué)過求兩個正整數(shù)的最大公約數(shù)的方法：先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.當(dāng)兩個數(shù)公有的質(zhì)因數(shù)較大

時（如與6 105），使用上述方法求最大公約數(shù)就比較困難.下面我們介紹兩種不同的算法——輾轉(zhuǎn)相除法與更相減損術(shù),由此可以體會東、西方文化的差異.（二）研探新知

（1）怎樣用短除法求最大公約數(shù)？

（2）怎樣用窮舉法（也叫枚舉法）求最大公約數(shù)？（3）怎樣用輾轉(zhuǎn)相除法求最大公約數(shù)？（4）怎樣用更相減損術(shù)求最大公約數(shù)？ 討論結(jié)果：（1）短除法

求兩個正整數(shù)的最大公約數(shù)的步驟：先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是兩個互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.（2）窮舉法（也叫枚舉法）

窮舉法求兩個正整數(shù)的最大公約數(shù)的解題步驟：從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù).（3）輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法步驟可以描述如下： 第一步，給定兩個正整數(shù)m，n.第二步，求余數(shù)r：計算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é)專著，其中的“更相減損術(shù)”也可以用來求兩個數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”翻譯為現(xiàn)代語言如下：

第一步，任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù)，若是，用2約簡；若不是，執(zhí)行第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).（三）范例分析

例1 用輾轉(zhuǎn)相除法求8 251與6 105的最大公約數(shù),寫出算法分析，畫出程序框圖，寫出算法程序.解：用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)：8 251=6 105×1+2 146.由此可得，6 105與2 146的公約數(shù)也是8 251與6 105的公約數(shù)，反過來，8 251與6 105的公約數(shù)也是6 105與2 146的公約數(shù)，所以它們的最大公約數(shù)相等.對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的最大公約數(shù).這就是輾轉(zhuǎn)相除法.由除法的性質(zhì)可以知道，對于任意兩個正整數(shù)，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉(zhuǎn)相除法求出兩個正整數(shù)的最大公約數(shù).算法分析：從上面的例子可以看出，輾轉(zhuǎn)相除法中包含重復(fù)操作的步驟，因此可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法.算法步驟如下：

第一步，給定兩個正整數(shù)m，n.第二步，計算m除以n所得的余數(shù)為r.第三步，m=n，n=r.第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.程序框圖如右圖： 程序： INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m

END 例2 用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，如下圖所示.98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，98和63的最大公約數(shù)等于7.前面我們學(xué)習(xí)了輾轉(zhuǎn)相除法與更相減損術(shù)，現(xiàn)在我們來學(xué)習(xí)一種新的算法：秦九韶算法.（1）怎樣求多項式f(x)=x+x+x+x+x+1當(dāng)x=5時的值呢？

一個自然的做法就是把5代入多項式f(x)，計算各項的值，然后把它們加起來，這時，我們一共做了1+2+3+4=10次乘法運(yùn)算，5次加法運(yùn)算.另一種做法是先計算x的值，然后依次計算x·x，（x·x）·x，（（x·x）·x）·x的值，這樣每次都可以利用上一次計算的結(jié)果，這時，我們一共做了4次乘法運(yùn)算，5次加法運(yùn)算.第二種做法與第一種做法相比，乘法的運(yùn)算次數(shù)減少了，因而能夠提高運(yùn)算效率，對于計算機(jī)來說，做一次乘法運(yùn)算所用的時間比做一次加法運(yùn)算要長得多，所以采用第二種做法，計算機(jī)能更快地得到結(jié)果.（2）上面問題有沒有更有效的算法呢？我國南宋時期的數(shù)學(xué)家秦九韶（約1202~1261）在他的著作《數(shù)書九章》中提出了下面的算法：

把一個n次多項式f(x)=anx+an-1x+?+a1x+a0改寫成如下形式： f(x)=anx+an-1x+?+a1x+a0 =（anx+an-1x+?+a1）x+ a0 =（（anx+an-1x+?+a2）x+a1)x+a0 =?

=（?（（anx+an-1）x+an-2）x+?+a1）x+a0.求多項式的值時，首先計算最內(nèi)層括號內(nèi)一次多項式的值，即v1=anx+an-1，然后由內(nèi)向外逐層計算一次多項式的值，即 v2=v1x+an-2，n-2n-3n-1n-2nn-1n

n-1

222

5432

v3=v2x+an-3，?

vn=vn-1x+a0，這樣，求n次多項式f（x）的值就轉(zhuǎn)化為求n個一次多項式的值.上述方法稱為秦九韶算法.直到今天，這種算法仍是多項式求值比較先進(jìn)的算法.（3）計算機(jī)的一個很重要的特點(diǎn)就是運(yùn)算速度快，但即便如此，算法好壞的一個重要標(biāo)志仍然是運(yùn)算的次數(shù).如果一個算法從理論上需要超出計算機(jī)允許范圍內(nèi)的運(yùn)算次數(shù)，那么這樣的算法就只能是一個理論的算法.例3 已知一個5次多項式為f（x）=5x+2x+3.5x-2.6x+1.7x-0.8，用秦九韶算法求這個多項式當(dāng)x=5時的值.解：根據(jù)秦九韶算法，把多項式改寫成如下形式： f(x)=（(((5x+2)x+3.5)x-2.6)x+1.7)x-0.8，按照從內(nèi)到外的順序，依次計算一次多項式當(dāng)x=5時的值： 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;所以，當(dāng)x=5時，多項式的值等于17 255.2.算法分析：觀察上述秦九韶算法中的n個一次式，可見vk的計算要用到vk-1的值，若令v0=an，我們可以得到下面的公式：

32?v0?an, ?v?vx?a(k?1,2,?,n).k?1n?k?k這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實現(xiàn).算法步驟如下：

第一步，輸入多項式次數(shù)n、最高次的系數(shù)an和x的值.第二步，將v的值初始化為an，將i的值初始化為n-1.第三步，輸入i次項的系數(shù)ai.第四步，v=vx+ai,i=i-1.第五步，判斷i是否大于或等于0.若是，則返回第三步；

否則，輸出多項式的值v.程序框圖如右圖： 程序：

INPUT “n=”；n INPUT “an=”；a INPUT “x=”；x v=a i=n-1 WHILE i＞=0 PRINT “i=”；i INPUT “ai=”；a v=v*x+a i=i-1 WEND PRINT v END

（四）隨堂練習(xí)P45 練習(xí)1、2

（五）歸納總結(jié)

（1）用輾轉(zhuǎn)相除法求最大公約數(shù).（2）用更相減損術(shù)求最大公約數(shù).（3）.秦九韶算法的方法和步驟.以及計算機(jī)程序框圖.（六）作業(yè)布置

1、P48習(xí)題1.3 A組1、2

2、完成課后鞏固作業(yè)

（八）五、教學(xué)反思：

_________________________________________________________ ___________________________________________________________________________________________________________________________________________________________________________

_________________________________________________________

1.3 算法案例 第2課時 進(jìn)位制

一、教學(xué)目標(biāo)：

根據(jù)課標(biāo)要求：掌握不同進(jìn)制之間的相互轉(zhuǎn)化，會用程序描述不同進(jìn)制之間的轉(zhuǎn)化，體會數(shù)學(xué)的轉(zhuǎn)化思想，制定以下三維目標(biāo)：

1、知識與技能

學(xué)生理解各種進(jìn)位制與十進(jìn)制之間轉(zhuǎn)換的規(guī)律，會利用十進(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)度與價值觀

學(xué)生通過合作完成任務(wù)后，領(lǐng)悟十進(jìn)制，二進(jìn)制的特點(diǎn)，了解計算機(jī)的電路與二進(jìn)制的聯(lián)系，進(jìn)一步認(rèn)識到計算機(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é)過程

（一）引入課題

在日常生活中，我們最熟悉、最常用的是十進(jìn)制，據(jù)說這與古人曾以手指計數(shù)有關(guān)，愛好天文學(xué)的古人也曾經(jīng)采用七進(jìn)制、十二進(jìn)制、六十進(jìn)制，至今我們?nèi)匀皇褂靡恢芷咛?、?/p>

年十二個月、一小時六十分的歷法.今天我們來學(xué)習(xí)一下進(jìn)位制.（二）研探新知

進(jìn)位制是人們?yōu)榱擞嫈?shù)和運(yùn)算方便而約定的計數(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ù)說這與古人曾以手指計數(shù)有關(guān)，愛好天文學(xué)的古人也曾經(jīng)采用七進(jìn)制、十二進(jìn)制、六十進(jìn)制，至今我們?nèi)匀皇褂靡恢芷咛?、一年十二個月、一小時六十分的歷法.十進(jìn)制使用0 ~9十個數(shù)字.計數(shù)時，幾個數(shù)字排成一行，從右起，第一位是個位，個位上的數(shù)字是幾，就表示幾個一；第二位是十位，十位上的數(shù)字是幾，就表示幾個十；接著依次是百位、千位、萬位??

例如：十進(jìn)制數(shù)3 721中的3表示3個千，7表示7個百，2表示2個十，1表示1個一.于是，我們得到下面的式子： 3 721=3×10+7×10+2×10+1×10.與十進(jìn)制類似，其他的進(jìn)位制也可以按照位置原則計數(shù).由于每一種進(jìn)位制的基數(shù)不同，所用的數(shù)字個數(shù)也不同.如二進(jìn)制用0和1兩個數(shù)字，七進(jìn)制用0~6七個數(shù)字.一般地，若k是一個大于1的整數(shù)，那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式 anan-1?a1a0（k）（0＜an＜k，0≤an-1，?，a1，a0＜k).其他進(jìn)位制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)的冪的乘積之和的形式，如 110 011（2）=1×2+1×2+0×2+0×2+1×2+1×2，7 342（8）=7×8+3×8+4×8+2×8.非十進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)比較簡單，只要計算下面的式子值即可： anan-1?a1a0(k)=an×k+an-1×k+?+a1×k+a0.第一步：從左到右依次取出k進(jìn)制數(shù)anan-1?a1a0(k)各位上的數(shù)字，乘以相應(yīng)的k的冪，k的冪從n開始取值，每次遞減1，遞減到0，即an×k,an-1×k,?,a1×k,a0×k； 第二步：把所得到的乘積加起來，所得的結(jié)果就是相應(yīng)的十進(jìn)制數(shù).關(guān)于進(jìn)位制的轉(zhuǎn)換，教科書上以十進(jìn)制和二進(jìn)制之間的轉(zhuǎn)換為例講解，并推廣到十進(jìn)制和

n

n-

10nn-1321

0

543210321

0

其他進(jìn)制之間的轉(zhuǎn)換.這樣做的原因是，計算機(jī)是以二進(jìn)制的形式進(jìn)行存儲和計算數(shù)據(jù)的，而一般我們傳輸給計算機(jī)的數(shù)據(jù)是十進(jìn)制數(shù)據(jù)，因此計算機(jī)必須先將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)，再處理，顯然運(yùn)算后首次得到的結(jié)果為二進(jìn)制數(shù)，同時計算機(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)換

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

i-1i-1

i-154

0

程序：

INPUT “a,k，n=”；a，k，n b=0 i=1 t=a MOD 10 DO b=b+t*k^（i-1）a=a10 t=a MOD 10 i=i+1 LOOP UNTIL i＞n PRINT b END 例3 把89化為二進(jìn)制數(shù).解：根據(jù)二進(jìn)制數(shù)“滿二進(jìn)一”的原則，可以用2連續(xù)去除89或所得商，然后取余數(shù).具體計算方法如下：

因為89=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×（2+1）+1）+0）+0）+1 =?=1×2+0×2+1×2+1×2+0×2+0×2+1×2 =1 011 001(2).這種算法叫做除2取余法，還可以用右邊的除法算式表示：

把上式中各步所得的余數(shù)從下到上排列，得到89=1 011 001(2).上述方法也可以推廣為把十進(jìn)制數(shù)化為k進(jìn)制數(shù)的算法，稱為除k取余法.6543

02

例4 設(shè)計一個程序，實現(xiàn)“除k取余法”.算法分析：從例2的計算過程可以看出如下的規(guī)律：

若十制數(shù)a除以k所得商是q0，余數(shù)是r0，即a=k·q0+r0，則r0是a的k進(jìn)制數(shù)的右數(shù)第1位數(shù).若q0除以k所得的商是q1，余數(shù)是r1，即q0=k·q1+r1，則r1是a的k進(jìn)制數(shù)的左數(shù)第2位數(shù).??

若qn-1除以k所得的商是0，余數(shù)是rn，即qn-1=rn，則rn是a的k進(jìn)制數(shù)的左數(shù)第1位數(shù).這樣，我們可以得到算法步驟如下：

第一步，給定十進(jìn)制正整數(shù)a和轉(zhuǎn)化后的數(shù)的基數(shù)k.第二步，求出a除以k所得的商q，余數(shù)r.第三步，把得到的余數(shù)依次從右到左排列.第四步，若q≠0，則a=q，返回第二步；否則，輸出全部余數(shù)r排列得到的k進(jìn)制數(shù).程序框圖如右圖： 程序：

INPUT “a，k=”；a，k b=0 i=0 DO q=ak r=a MOD k b=b+r*10^i i=i+1 a=q LOOP UNTIL q=0 PRINT b END

（四）隨堂練習(xí)

1、將十進(jìn)制數(shù)34轉(zhuǎn)化為二進(jìn)制數(shù)． 解：

即34(10)=100 010(2)

2、把1 234(5)分別轉(zhuǎn)化為十進(jìn)制數(shù)和八進(jìn)制數(shù)． 解：1 234(5)=1×5+2×5+3×5+4＝194． 則1 234(5)=302(8)

所以，1 234(5)=194＝302(8)

點(diǎn)評：本題主要考查進(jìn)位制以及不同進(jìn)位制數(shù)的互化．五進(jìn)制數(shù)直接利用公式就可以轉(zhuǎn)化為十進(jìn)制數(shù)；五進(jìn)制數(shù)和八進(jìn)制數(shù)之間需要借助于十進(jìn)制數(shù)來轉(zhuǎn)化．

32（五）歸納總結(jié)

（1）理解算法與進(jìn)位制的關(guān)系.（2）熟練掌握各種進(jìn)位制之間轉(zhuǎn)化.（六）作業(yè)布置

1、習(xí)題1.3A組3、4.2、完成課后鞏固作業(yè)

（九）五、教學(xué)反思：

_________________________________________________________ ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________

第四篇：高中數(shù)學(xué)《秦九韶算法與排序》教案1 北師大版必修3

第三、四課時 秦九韶算法與排序

（1）教學(xué)目標(biāo)（a）知識與技能

1.了解秦九韶算法的計算過程，并理解利用秦九韶算法可以減少計算次數(shù)提高計算效率的實質(zhì)。

2.掌握數(shù)據(jù)排序的原理能使用直接排序法與冒泡排序法給一組數(shù)據(jù)排序，進(jìn)而能設(shè)計冒泡排序法的程序框圖及程序，理解數(shù)學(xué)算法與計算機(jī)算法的區(qū)別，理解計算機(jī)對數(shù)學(xué)的輔助作用。

（b）過程與方法

模仿秦九韶計算方法，體會古人計算構(gòu)思的巧妙。能根據(jù)排序法中的直接插入排序法與冒泡排序法的步驟，了解數(shù)學(xué)計算轉(zhuǎn)換為計算機(jī)計算的途徑，從而探究計算機(jī)算法與數(shù)學(xué)算法的區(qū)別，體會計算機(jī)對數(shù)學(xué)學(xué)習(xí)的輔助作用。（c）情態(tài)與價值

通過對秦九韶算法的學(xué)習(xí)，了解中國古代數(shù)學(xué)家對數(shù)學(xué)的貢獻(xiàn)，充分認(rèn)識到我國文化歷史的悠久。通過對排序法的學(xué)習(xí)，領(lǐng)會數(shù)學(xué)計算與計算機(jī)計算的區(qū)別，充分認(rèn)識信息技術(shù)對數(shù)學(xué)的促進(jìn)。

（2）教學(xué)重難點(diǎn)

重點(diǎn)：1.秦九韶算法的特點(diǎn)

2.兩種排序法的排序步驟及計算機(jī)程序設(shè)計 難點(diǎn)：1.秦九韶算法的先進(jìn)性理解

2.排序法的計算機(jī)程序設(shè)計（3）學(xué)法與教學(xué)用具

學(xué)法：1.探究秦九韶算法對比一般計算方法中計算次數(shù)的改變，體會科學(xué)的計算。2.模仿排序法中數(shù)字排序的步驟，理解計算機(jī)計算的一般步驟，領(lǐng)會數(shù)學(xué)計算在計算機(jī)上實施的要求。

教學(xué)用具：電腦，計算器，圖形計算器

（4）教學(xué)設(shè)想

（一）創(chuàng)設(shè)情景，揭示課題

我們已經(jīng)學(xué)過了多項式的計算，下面我們計算一下多項式

5432f(x)?x?x?x?x?x?1當(dāng)x?5時的值，并統(tǒng)計所做的計算的種類及計算次數(shù)。

根據(jù)我們的計算統(tǒng)計可以得出我們共需要10次乘法運(yùn)算，5次加法運(yùn)算。

2我們把多項式變形為：f(x)?x(1?x(1?x(1?x)))?x?1再統(tǒng)計一下計算當(dāng)x?5時的值時需要的計算次數(shù)，可以得出僅需4次乘法和5次加法運(yùn)算即可得出結(jié)果。顯然少了6次乘法運(yùn)算。這種算法就叫秦九韶算法。

（二）研探新知

1.秦九韶計算多項式的方法

用心

愛心

專心 31

f(x)?anx?an?1x?(anxn?1n?2nn?1?an?2xn?3n?2???a1x?a0???a1)x?a0?an?1xn?2?an?2xn?3?((anx????an?1x???a2)x?a1)x?a0

?(?((anx?an?1)x?an?2)x???a1)?a0例1 已知一個5次多項式為f(x)?5x5?2x4?3.5x3?2.6x2?1.7x?0.8 用秦九韶算法求這個多項式當(dāng)x?5時的值。解：略

思考：（1）例1計算時需要多少次乘法計算？多少次加法計算？

（2）在利用秦九韶算法計算n次多項式當(dāng)x?x0時需要多少次乘法計算和多少次加法計算？

練習(xí)：利用秦九韶算法計算f(x)?0.83x5?0.41x4?0.16x3?0.33x2?0.5x?1 當(dāng)x?5時的值，并統(tǒng)計需要多少次乘法計算和多少次加法計算？ 例2 設(shè)計利用秦九韶算法計算5次多項式

f(x)?a5x?a4x?a3x?a2x?a1x?a0當(dāng)x?x0時的值的程序框圖。5432解：程序框圖如下：

開始輸入f(x)的系數(shù)：a1,a2,a3,a4,a5輸入x0n=1v=a5 n=n+1v=v x0+a5-nn≤5是否輸出v結(jié)束

用心

愛心

專心

練習(xí)：利用程序框圖試編寫B(tài)ASIC程序并在計算機(jī)上測試自己的程序。

2.排序

在信息技術(shù)課中我們學(xué)習(xí)過電子表格,電子表格對分?jǐn)?shù)的排序非常簡單,那么電子計算機(jī)是怎么對數(shù)據(jù)進(jìn)行排序的呢? 閱讀課本P30—P31面的內(nèi)容,回答下面的問題:(1)排序法中的直接插入排序法與冒泡排序法的步驟有什么區(qū)別?(2)冒泡法排序中對5個數(shù)字進(jìn)行排序最多需要多少趟?(3)在冒泡法排序?qū)?個數(shù)字進(jìn)行排序的每一趟中需要比較大小幾次? 游戲:5位同學(xué)每人拿一個數(shù)字牌在講臺上演示冒泡排序法對5個數(shù)據(jù)4,11,7,9,6排序的過程,讓學(xué)生通過觀察敘述冒泡排序法的主要步驟.并結(jié)合步驟解決例3的問題.例3 用冒泡排序法對數(shù)據(jù)7,5,3,9,1從小到大進(jìn)行排序

解:P32 練習(xí):寫出用冒泡排序法對5個數(shù)據(jù)4,11,7,9,6排序的過程中每一趟排序的結(jié)果.例4 設(shè)計冒泡排序法對5個數(shù)據(jù)進(jìn)行排序的程序框圖.解: 程序框圖如下:

開始輸入a1,a2,a3,a4,a5r=1i=1ai>ai+1是否x=aiai=ai+1ai+1=xi=i+1r=r+1i=5否是r=5否是輸出a1,a2,a3,a4,a5結(jié)束 思考:直接排序法的程序框圖如何設(shè)計?可否把上述程序框圖轉(zhuǎn)化為程序? 練習(xí):用直接排序法對例3中的數(shù)據(jù)從小到大排序

用心

愛心

專心

3.小結(jié):(1)秦九韶算法計算多項式的值及程序設(shè)計

(2)數(shù)字排序法中的常見的兩種排序法直接插入排序法與冒泡排序法(3)冒泡法排序的計算機(jī)程序框圖設(shè)計（5）評價設(shè)計

作業(yè)：P38 A（2）（3）

補(bǔ)充：設(shè)計程序框圖對上述兩組數(shù)進(jìn)行排序

用心

愛心

專心 34

第五篇：算法案例教學(xué)設(shè)計

算法案例——輾轉(zhuǎn)相除法與更相減損術(shù)

唐勁松

一、教材解讀

本節(jié)內(nèi)容是在學(xué)習(xí)了算法的基礎(chǔ)知識上，探究古代典型的算法案例——輾轉(zhuǎn)相除法和更相減損術(shù)，鞏固算法三種描述性語言（算法步驟，程序框圖和程序語言），使學(xué)生對算法中的迭代思想有一個初步的認(rèn)識。一方面以輾轉(zhuǎn)相除法及更相減損術(shù)為載體，使學(xué)生通過模仿，操作，探索經(jīng)歷算法設(shè)計的全過程，幫助學(xué)生進(jìn)一步體會算法的基本思想，感受算法在解決實際問題中的重要作用，另一方面讓學(xué)生體會中國古代數(shù)學(xué)家對現(xiàn)代數(shù)學(xué)發(fā)展的貢獻(xiàn)。

二、教學(xué)重難點(diǎn)

重點(diǎn)：輾轉(zhuǎn)相除法與更相減損術(shù)的方法和步驟；

難點(diǎn)：輾轉(zhuǎn)相除法的原理及其程序。

三、教學(xué)過程

Ⅰ引入新課

簡單回顧短除法求兩個數(shù)的最大公約數(shù)，并提出問題：當(dāng)兩個數(shù)較大時（如：8251與6105），如何求它們的最大公約數(shù)？引出課題——輾轉(zhuǎn)相除法。

Ⅱ知識探究

1、以求8251與6105的最大公約數(shù)的過程為例，講解如何利用輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)。對于輾轉(zhuǎn)相除法的原理，書本介紹的不是很詳細(xì)，學(xué)生容易產(chǎn)生疑惑，需要教師講解清楚。

2、通過這個實例，讓學(xué)生能夠模仿求任意兩個數(shù)的最大公約數(shù)，體會這種迭代的思想，并能與前面學(xué)習(xí)的循環(huán)結(jié)構(gòu)聯(lián)系起來。

3、訓(xùn)練（學(xué)生演排），了解學(xué)生的掌握情況，及時指出問題。

4、簡單介紹歐幾里得其人，增強(qiáng)學(xué)生人文素養(yǎng)。

5、引導(dǎo)學(xué)生根據(jù)前面的過程畫出輾轉(zhuǎn)相除法的程序框圖，并編寫出程序。靈活運(yùn)用直到型循環(huán)結(jié)構(gòu)及當(dāng)型循環(huán)結(jié)構(gòu)，并能轉(zhuǎn)化成語句。完成課本P45練習(xí)1:用輾轉(zhuǎn)相除法求下列兩個數(shù)的最大公約數(shù)：（1）225,135；（2）98,196；（3）72,168；（4）153,119.并用程序進(jìn)行演示判斷是否正確。

6、鞏固提高：

（1）求三個數(shù)：324,243,135的最大公約數(shù)；（2）求228與1995的最小公倍數(shù)。

7、介紹另一種求最大公約數(shù)的方法——更相減損術(shù)，簡單介紹相關(guān)數(shù)學(xué)史的知識，對學(xué)生進(jìn)行數(shù)學(xué)文化熏陶，增強(qiáng)民族自豪感。

8、通過實例：求98與63的最大公約數(shù) 來理解更相減損術(shù)的原理和過程。

9、分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù)，來體會和總結(jié)輾轉(zhuǎn)相除法和更相減損術(shù)的區(qū)別。

Ⅲ課堂小結(jié)

學(xué)生回顧總結(jié)兩種方法的步驟，教師加以補(bǔ)充和點(diǎn)評。