第一篇：算法案例教案

課題：§1．3算法案例

第1課時 輾轉相除法與更相減損術、秦九韶算法

一、教學目標：

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

1、知識與技能

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

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

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

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

難點：體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數學表達能力.解決策略：讓學生能嚴謹地按照自己是程序框圖寫出程序。

三、學法與教學用具：

1、學法：直觀感知、操作確認。

2、教學用具：多媒體。

四、教學過程

（一）引入課題

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

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

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

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

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

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

輾轉相除法求兩個數的最大公約數，其算法步驟可以描述如下： 第一步，給定兩個正整數m，n.第二步，求余數r：計算m除以n，將所得余數存放到變量r中.第三步，更新被除數和余數：m=n，n=r.第四步，判斷余數r是否為0.若余數為0，則輸出結果；否則轉向第二步繼續(xù)循環(huán)執(zhí)行.如此循環(huán)，直到得到結果為止.這種算法是由歐幾里得在公元前300年左右首先提出的，因而又叫歐幾里得算法.（4）更相減損術

我國早期也有解決求最大公約數問題的算法，就是更相減損術.《九章算術》是中國古代的數學專著，其中的“更相減損術”也可以用來求兩個數的最大公約數，即“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也.以等數約之.”翻譯為現代語言如下：

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

例1 用輾轉相除法求8 251與6 105的最大公約數,寫出算法分析，畫出程序框圖，寫出算法程序.解：用兩數中較大的數除以較小的數，求得商和余數：8 251=6 105×1+2 146.由此可得，6 105與2 146的公約數也是8 251與6 105的公約數，反過來，8 251與6 105的公約數也是6 105與2 146的公約數，所以它們的最大公約數相等.對6 105與2 146重復上述步驟：6 105=2 146×2+1 813.同理，2 146與1 813的最大公約數也是6 105與2 146的最大公約數.繼續(xù)重復上述步驟： 2 146=1 813×1+333，1 813=333×5+148，333=148×2+37，148=37×4.最后的除數37是148和37的最大公約數，也就是8 251與6 105的最大公約數.這就是輾轉相除法.由除法的性質可以知道，對于任意兩個正整數，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉相除法求出兩個正整數的最大公約數.算法分析：從上面的例子可以看出，輾轉相除法中包含重復操作的步驟，因此可以用循環(huán)結構來構造算法.算法步驟如下：

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

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

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

把一個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.求多項式的值時，首先計算最內層括號內一次多項式的值，即v1=anx+an-1，然后由內向外逐層計算一次多項式的值，即 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）的值就轉化為求n個一次多項式的值.上述方法稱為秦九韶算法.直到今天，這種算法仍是多項式求值比較先進的算法.（3）計算機的一個很重要的特點就是運算速度快，但即便如此，算法好壞的一個重要標志仍然是運算的次數.如果一個算法從理論上需要超出計算機允許范圍內的運算次數，那么這樣的算法就只能是一個理論的算法.例3 已知一個5次多項式為f（x）=5x+2x+3.5x-2.6x+1.7x-0.8，用秦九韶算法求這個多項式當x=5時的值.解：根據秦九韶算法，把多項式改寫成如下形式： f(x)=（(((5x+2)x+3.5)x-2.6)x+1.7)x-0.8，按照從內到外的順序，依次計算一次多項式當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;所以，當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這是一個在秦九韶算法中反復執(zhí)行的步驟，因此可用循環(huán)結構來實現.算法步驟如下：

第一步，輸入多項式次數n、最高次的系數an和x的值.第二步，將v的值初始化為an，將i的值初始化為n-1.第三步，輸入i次項的系數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

（四）隨堂練習P45 練習1、2

（五）歸納總結

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

1、P48習題1.3 A組1、2

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

（八）五、教學反思：

_________________________________________________________ ___________________________________________________________________________________________________________________________________________________________________________

_________________________________________________________

1.3 算法案例 第2課時 進位制

一、教學目標：

根據課標要求：掌握不同進制之間的相互轉化，會用程序描述不同進制之間的轉化，體會數學的轉化思想，制定以下三維目標：

1、知識與技能

學生理解各種進位制與十進制之間轉換的規(guī)律，會利用十進制與各種進制之間的聯系進行各種進位制之間的轉換。

2、過程與方法

學生經歷得出各種進位制與十進制之間轉換的規(guī)律的過程，進一步掌握進位制之間轉換的方法。

3、情感、態(tài)度與價值觀

學生通過合作完成任務后，領悟十進制，二進制的特點，了解計算機的電路與二進制的聯系，進一步認識到計算機與數學的聯系，培養(yǎng)他們的合作精神和嚴謹的態(tài)度。

二、教學重點、難點

重點：各進位制之間的轉換。

解決策略：讓學生弄懂各進位制的特點和聯系，再搭配習題講解。難點：“除k取余法”的理解。

解決策略：先給出具體的例子講解，再延伸到一般的情況。

三、學法與教學用具

1、學法：講授法、歸納法、討論法。

2、教學用具：多媒體，投影儀

四、教學過程

（一）引入課題

在日常生活中，我們最熟悉、最常用的是十進制，據說這與古人曾以手指計數有關，愛好天文學的古人也曾經采用七進制、十二進制、六十進制，至今我們仍然使用一周七天、一

年十二個月、一小時六十分的歷法.今天我們來學習一下進位制.（二）研探新知

進位制是人們?yōu)榱擞嫈岛瓦\算方便而約定的計數系統(tǒng)，約定滿二進一，就是二進制；滿十進一，就是十進制；滿十二進一，就是十二進制；滿六十進一，就是六十進制等等.也就是說：“滿幾進一”就是幾進制，幾進制的基數（都是大于1的整數）就是幾.在日常生活中，我們最熟悉、最常用的是十進制，據說這與古人曾以手指計數有關，愛好天文學的古人也曾經采用七進制、十二進制、六十進制，至今我們仍然使用一周七天、一年十二個月、一小時六十分的歷法.十進制使用0 ~9十個數字.計數時，幾個數字排成一行，從右起，第一位是個位，個位上的數字是幾，就表示幾個一；第二位是十位，十位上的數字是幾，就表示幾個十；接著依次是百位、千位、萬位??

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

n

n-

10nn-1321

0

543210321

0

其他進制之間的轉換.這樣做的原因是，計算機是以二進制的形式進行存儲和計算數據的，而一般我們傳輸給計算機的數據是十進制數據，因此計算機必須先將十進制數轉換為二進制數，再處理，顯然運算后首次得到的結果為二進制數，同時計算機又把運算結果由二進制數轉換成十進制數輸出.1°十進制數轉換成非十進制數

把十進制數轉換為二進制數，教科書上提供了“除2取余法”，我們可以類比得到十進制數轉換成k進制數的算法“除k取余法”.2°非十進制之間的轉換

一個自然的想法是利用十進制作為橋梁.教科書上提供了一個二進制數據與16進制數據之間的互化的方法，也就是先由二進制數轉化為十進制數，再由十進制數轉化成為16進制數.（三）范例分析

例1 把二進制數110 011(2)化為十進制數.解：110 011(2)=1×2+1×2+0×2+0×2+1×2+1×2=1×32+1×16+1×2+1=51.點評：先把二進制數寫成不同位上數字與2的冪的乘積之和的形式，再按照十進制的運算規(guī)則計算出結果.例2設計一個算法，把k進制數a（共有n位）化為十進制數b.算法分析：從例1的計算過程可以看出，計算k進制數a的右數第i位數字ai與k的乘積ai·k，再將其累加，這是一個重復操作的步驟.所以，可以用循環(huán)結構來構造算法.算法步驟如下： 第一步，輸入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化為二進制數.解：根據二進制數“滿二進一”的原則，可以用2連續(xù)去除89或所得商，然后取余數.具體計算方法如下：

因為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取余法，還可以用右邊的除法算式表示：

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

02

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

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

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

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

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

（四）隨堂練習

1、將十進制數34轉化為二進制數． 解：

即34(10)=100 010(2)

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

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

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

32（五）歸納總結

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

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

（九）五、教學反思：

_________________________________________________________ ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________

第二篇：高中數學 算法案例思維過程教案

?思維過程

【例1】用“等值算法”求161、253的最大公約數.分析:所謂“等值算法”就是以兩個數中較大的數減去較小的數,以差和較小的數構成新的一對數.對于這一對數,再用大數減去小數,用同樣的方法一直做下去,直到得到兩個相等的數,這個數就是最大公約數.解:253－161=92;161－92=69;92－69=23;69－23=46;46－23=23;即(161,253)→(92,161)→(69,92)→(23,69)→(23,46)→(23,23)所以253和161的最大公約數為23.【例2】求1734,816,1343的最大公約數.分析:三個數的最大公約數分別是每個數的約數,因此也是任意兩個數的最大公約數的約數,也就是說三個數的最大公約數是其中任意兩個數的最大公約數與第三個數的最大公約數.解法一:等值算法

先求1734和816的最大公約數, 1734－816=918;918－816=102;816－102=714;714－102=612;612－102=510;510－102=408;408－102=306;306－102=204;204－102=102.即(1734,816)→(816,918)→(816,102)→(714,102)→(612,102)→(510,102)→(408,102)→(306,102)→(204,102)→(102,102).所以 1734和816的最大公約數是102, 再求102和1343的最大公約數, 1343－102=1241;1241－102=1139;1139－102=1037;1037－102=935;935－102=833;833－102=731;731－102=629,629－102=527;527－102=425;425－102=323;323－102=221;221－102=119;119－102=17;102－17=85;85－17=68;68－17=51;51－17=34;34－17=17.所以1343與102的最大公約數是17,即 1734,816,1343的最大公約數是17.解法二:輾轉相除法

先求1734和816的最大公約數, 1734=816×2+102;816=102×8;所以1734與816的最大公約數為102.再求102與1343的最大公約數, 1343=102×13+17;102=17×6;所以1343與102的最大公約數為17,即1734,816,1343的最大公約數為17.【例3】有甲、乙、丙三種溶液,分別重

413 kg、3 kg、2 kg千克.先要將它們分別641

用心

愛心

專心 全部裝入小瓶中,每個小瓶裝入液體的重量相同.問:每瓶最多裝多少？

分析:根據題意,每個小瓶裝的溶液的質量應是三種溶液質量的最大公約數.先求任意兩個數的最大公約數,然后再求這個數與第三個數的最大公約數.125***080==;3==;2==;663644369936******05－=;－=;－=;***636105***51560－=;－=;－=;******301515－=;－=;－=;***6361315即4,3的最大公約數為.643680***01535351520－=;－=;－=;－=;***63636363620***5－=;－=;－=.***6361325即4、3、2的最大公約數是.649365因此每瓶最多裝 kg.3665432【例4】用秦九韶算法求多項式f(x)=3x+12x+8x－3.5x+7.2x+5x－13在x=6時的值.解:f(x)=(((((3x+12)x+8)x－3.5)x+7.2)x+5)x－13 u0=3;u1=3×6+12=30;u2=u1×6+8=180+8=188;u3=u2×6－3.5=188×6－3.5=1128－3.5=1124.5;u4=u3×6+7.2=1124.5×6+7.2=6747+7.2=6754.2;u5=u4×6+5=6754.2×6+5=40525.2+5=40530.2;u6=u5×6－13=40530.2×6－13=243181.2－13=243168.2.所以f(6)=243168.2.【例5】填空:用冒泡排序法將下列各數排序

12,7,50,18,21,3,6排序時,請你填上第二趟和第四趟的順序.解:4

12750***2***82***150

解:

用心

愛心

專心 2

12750***2***62*********150用心

愛心

專心 3

第三篇：算法和算法描述教案

一、教學內容：算法和算法的描述（選修1算法與程序設計 廣東教育出版社）

二、教學課時：1課時

三、教學地點：計算機室2

四、教學目標：

1、知識目標

（1）明白算法的概念，理解算法的特征。（2）掌握算法描述的三種方法，能看懂流程圖。（3）了解算法的意義，找出三種算法描述的優(yōu)缺點。

2、技能目標

（1）知道在什么場合應該用什么算法描述。

（2）能對算法和算法的描述正確定位，能用算法解決實際問題，為學習后面的程序設計打下基礎。

3、情感目標

（1）能把現實社會中的問題用算法描述出來，培養(yǎng)學生們的合作精神和想象能力，以提高學生們的信息素養(yǎng)。

五、教學方法：任務驅動法

六、教學重點：

算法的概念、描述算法的三種方法。

七、教學難點：

用流程圖描述算法。

八、教學過程

1.激發(fā)興趣、創(chuàng)設情景

這節(jié)課內容主要是一些概念和理論，而算法的概念和理論都太抽象，講起來非常的枯燥乏味，那么就要把這些抽象的東西變得通俗易懂，使學生能輕松而又愉快的接受并理解。

舉出一個例子如炒土豆絲如何做？引導學生們一步步說出步驟，最后教師總結：算法就是解決問題的方法和步驟。在以后的編程中也要記住了，有些步驟是可以顛倒的，不影響程序的結果；但是有些一但顛倒了那最終的結果也就全變了。

2.講.解

激發(fā)學生的興趣后對算法、算法的特征（確定性、有窮性）進行講解，注意運用生活中的實例，以便讓學生們理解。

講述算法的三種描述方法：自然語言、流程圖、偽代碼。學生們比較熟悉的是自然語言，陌生難理解的是流程圖和偽代碼。

先帶學生們了解自然語言，然后講偽代碼，講完偽代碼后，引導學生們如何把這些程序用流程圖表示出來。流程圖的基本圖形及其功能

給出一個程序，讓學生們先讀這個程序，再用流程圖表示這個程序如：

Private Sub Command1_Click()a = InputBox(“輸入數字”)If a Mod 2 = 0 Then Print a & “是偶數” Else Print a & “是奇數” End If End Sub 學生們自學后，由教師引導發(fā)現這是一個判斷奇偶數的程序，找一個學生展示他的流程圖，然后大家共同檢查這個流程圖是否正確。

九、課堂作業(yè) 再給學生們一個程序，讓學生們讀并且在word中畫出流程圖，然后教到主機上。

十、課后反思：

在本節(jié)課中進行任務驅動式教學，充分發(fā)揮學生的主觀能動性。同時這節(jié)課內容多，而且難以理解，練習生活中的實例，既可以激發(fā)學生們的興趣，又有助于知識的遷移和內化。

第四篇：算法案例教學設計

算法案例——輾轉相除法與更相減損術

唐勁松

一、教材解讀

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

二、教學重難點

重點：輾轉相除法與更相減損術的方法和步驟；

難點：輾轉相除法的原理及其程序。

三、教學過程

Ⅰ引入新課

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

Ⅱ知識探究

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

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

3、訓練（學生演排），了解學生的掌握情況，及時指出問題。

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

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

6、鞏固提高：

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

7、介紹另一種求最大公約數的方法——更相減損術，簡單介紹相關數學史的知識，對學生進行數學文化熏陶，增強民族自豪感。

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

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

Ⅲ課堂小結

學生回顧總結兩種方法的步驟，教師加以補充和點評。

第五篇：《算法案例：秦九韶算法》教學教案

秦九韶算法

學習目標

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

2.掌握數據排序的原理能使用直接排序法與冒泡排序法給一組數據排序，進而能設計冒泡排序法的程序框圖及程序，理解數學算法與計算機算法的區(qū)別，理解計算機對數學的輔助作用。學習重難點

重點：1.秦九韶算法的特點

2.兩種排序法的排序步驟及計算機程序設計 難點：1.秦九韶算法的先進性理解

2.排序法的計算機程序設計

學法與學習用具

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

2.模仿排序法中數字排序的步驟，理解計算機計算的一般步驟，領會數學計算在計算機上實施的要求。

學習用具：電腦，計算器，圖形計算器 學習設想

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

我們已經學過了多項式的計算，下面我們計算一下多項式

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

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

（二）研探新知

/ 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 用秦九韶算法求這個多項式當x?5時的值。解：略

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

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

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

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

/ 4

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

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

2.排序

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

/ 4

練習:寫出用冒泡排序法對5個數據4,11,7,9,6排序的過程中每一趟排序的結果.例4 設計冒泡排序法對5個數據進行排序的程序框圖.解: 程序框圖如下:

開始輸入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結束 思考:直接排序法的程序框圖如何設計?可否把上述程序框圖轉化為程序? 練習:用直接排序法對例3中的數據從小到大排序 3.小結:(1)秦九韶算法計算多項式的值及程序設計

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

/ 4