- 相關推薦
完整版算法案例教案
在教學工作者開展教學活動前，編寫教案是必不可少的，編寫教案有利于我們科學、合理地支配課堂時間。那么優(yōu)秀的教案是什么樣的呢？以下是小編為大家整理的完整版算法案例教案，僅供參考，大家一起來看看吧。
第1課時 輾轉相除法與更相減損術、秦九韶算法
一、教學目標：
根據(jù)課標要求：在學生學習了算法的初步知識，理解了表示算法的算法步驟、程序框圖和程序三種不同方式以后，再結合典型算法案例，讓學生經(jīng)歷設計算法解決問題的全過程，體驗算法在解決問題中的重要作用，體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學表達能力。制定以下三維目標：
1、知識與技能
理解算法案例的算法步驟和程序框圖.
2、過程與方法：
引導學生得出自己設計的算法程序.
3、情感態(tài)度與價值觀：
體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學表達能力. 二、重點與難點：
重點：引導學生得出自己設計的算法步驟、程序框圖和算法程序. 解決策略：通過分析解決具體問題的算法步驟來引導學生寫出算法，根據(jù)算法畫出程序框圖，再根據(jù)框圖用規(guī)范的語言寫出程序。
難點：體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學表達能力. 解決策略：讓學生能嚴謹?shù)匕凑兆约菏浅绦蚩驁D寫出程序。
三、學法與教學用具：
1、學法：直觀感知、操作確認。
2、教學用具：多媒體。
四、教學過程
�。ㄒ唬┮胝n題
大家喜歡打乒乓球吧，由于東、西方文化及身體條件的不同，西方人喜歡橫握拍打球，東方人喜歡直握拍打球，對于同一個問題，東、西方人處理問題方式是有所不同的在小學，我們學過求兩個正整數(shù)的最大公約數(shù)的方法：先用兩個數(shù)公有的質因數(shù)連續(xù)去除，一直除到所得的商是互質數(shù)為止，然后把所有的除數(shù)連乘起來. 當兩個數(shù)公有的質因數(shù)較大時（如8 251與6 105），使用上述方法求最大公約數(shù)就比較困難.下面我們介紹兩種不同的算法——輾轉相除法與更相減損術,由此可以體會東、西方文化的差異. （二）研探新知
�。�1）怎樣用短除法求最大公約數(shù)？
�。�2）怎樣用窮舉法（也叫枚舉法）求最大公約數(shù)？
�。�3）怎樣用輾轉相除法求最大公約數(shù)？
�。�4）怎樣用更相減損術求最大公約數(shù)？
討論結果：
（1）短除法
求兩個正整數(shù)的最大公約數(shù)的步驟：先用兩個數(shù)公有的質因數(shù)連續(xù)去除，一直除到所得的商是兩個互質數(shù)為止，然后把所有的除數(shù)連乘起來.
�。�2）窮舉法（也叫枚舉法）
窮舉法求兩個正整數(shù)的最大公約數(shù)的解題步驟：從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù).
（3）輾轉相除法
輾轉相除法求兩個數(shù)的最大公約數(shù)，其算法步驟可以描述如下：
第一步，給定兩個正整數(shù)m，n.
第二步，求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中.
第三步，更新被除數(shù)和余數(shù)：m=n，n=r.
第四步，判斷余數(shù)r是否為0.若余數(shù)為0，則輸出結果；否則轉向第二步繼續(xù)循環(huán)執(zhí)行. 如此循環(huán)，直到得到結果為止. 這種算法是由歐幾里得在公元前300年左右首先提出的，因而又叫歐幾里得算法.
�。�4）更相減損術
我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術. 《九章算術》是中國古代的數(shù)學專著，其中的“更相減損術”也可以用來求兩個數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”翻譯為現(xiàn)代語言如下：
第一步，任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù)，若是，用2約簡；若不是，執(zhí)行第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).
（三）范例分析
例1 用輾轉相除法求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重復上述步驟：6 105=2 146×2+1 813.
同理，2 146與1 813的最大公約數(shù)也是6 105與2 146的最大公約數(shù).繼續(xù)重復上述步驟：
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ù). 這就是輾轉相除法.由除法的性質可以知道，對于任意兩個正整數(shù)，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉相除法求出兩個正整數(shù)的最大公約數(shù). 算法分析：從上面的例子可以看出，輾轉相除法中包含重復操作的步驟，因此可以用循環(huán)結構來構造算法.
算法步驟如下：
第一步，給定兩個正整數(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 用更相減損術求98與63的最大公約數(shù).
解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉相減，如下圖所示. 98-63=35
63-35=28
35-28=7
28-7=21
21-7=14 14-7=7
所以，98和63的最大公約數(shù)等于7.
前面我們學習了輾轉相除法與更相減損術，現(xiàn)在我們來學習一種新的算法：秦九韶算法. 5432（1）怎樣求多項式f(x)=x+x+x+x+x+1當x=5時的值呢？
一個自然的做法就是把5代入多項式f(x)，計算各項的值，然后把它們加起來，這時，我們一共做了1+2+3+4=10次乘法運算，5次加法運算. 2222另一種做法是先計算x的值，然后依次計算x·x，（x·x）·x，（（x·x）·x）·x的值，這樣每次都可以利用上一次計算的結果，這時，我們一共做了4次乘法運算，5次加法運算.
第二種做法與第一種做法相比，乘法的運算次數(shù)減少了，因而能夠提高運算效率，對于計算機來說，做一次乘法運算所用的時間比做一次加法運算要長得多，所以采用第二種做法，計算機能更快地得到結果.
（2）上面問題有沒有更有效的算法呢？我國南宋時期的數(shù)學家秦九韶（約1202~1261）在他的著作《數(shù)書九章》中提出了下面的算法：
nn-1把一個n次多項式f(x)=ax+ax+…+ax+a改寫成如下形式： nn-110nn-1f(x)=ax+ax+…+ax+a nn-110n-1n-2=（ax+ax+…+a）x+ a nn-110n-2n-3=（（ax+ax+…+a）x+a)x+a nn-1210=…
=（…（（ax+a）x+a）x+…+a）x+a. nn-1n-210
求多項式的值時，首先計算最內(nèi)層括號內(nèi)一次多項式的值，即v=ax+a， 1nn-1然后由內(nèi)向外逐層計算一次多項式的值，即
v=vx+a， 21n-2
v=vx+a， 32n-3
…
v=vx+a，nn-10這樣，求n次多項式f（x）的值就轉化為求n個一次多項式的值. 上述方法稱為秦九韶算法.直到今天，這種算法仍是多項式求值比較先進的算法. （3）計算機的一個很重要的特點就是運算速度快，但即便如此，算法好壞的一個重要標志仍然是運算的次數(shù).如果一個算法從理論上需要超出計算機允許范圍內(nèi)的運算次數(shù)，那么這樣的算法就只能是一個理論的算法. 5432例3 已知一個5次多項式為f（x）=5x+2x+3.5x-2.6x+1.7x-0.8，用秦九韶算法求這個多項式當x=5時的值.
解：根據(jù)秦九韶算法，把多項式改寫成如下形式：
f(x)=（(((5x+2)x+3.5)x-2.6)x+1.7)x-0.8，按照從內(nèi)到外的順序，依次計算一次多項式當x=5時的值：
v=5； 0
v=5×5+2=27; 1
v=27×5+3.5=138.5; 2
v=138.5×5-2.6=689.9; 3
v=689.9×5+1.7=3 451.2; 4
v=3 415.2×5-0.8=17 255.2;
5
所以，當x=5時，多項式的值等于17 255.2.
算法分析：觀察上述秦九韶算法中的n個一次式，可見v的計算要用到v的值，若令v=a，kk-10n我們可以得到下面的公式：
va,0n vvxa(k1,2,n).kk1nk
這是一個在秦九韶算法中反復執(zhí)行的步驟，因此可用循環(huán)結構來實現(xiàn). 算法步驟如下：
第一步，輸入多項式次數(shù)n、最高次的系數(shù)a和x的值. n
第二步，將v的值初始化為a，將i的值初始化為n-1. n
第三步，輸入i次項的系數(shù)a. i
第四步，v=vx+a,i=i-1. i
第五步，判斷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
�。ㄎ澹w納總結
（1）用輾轉相除法求最大公約數(shù). （2）用更相減損術求最大公約數(shù). （3）.秦九韶算法的方法和步驟.以及計算機程序框圖.
�。┳鳂I(yè)布置
1、P48 習題1.3 A組1、2 2、完成課后鞏固作業(yè)（八）
五、教學反思：
_________________________________________________________
1.3 算法案例
第2課時 進位制
一、教學目標：
根據(jù)課標要求：掌握不同進制之間的相互轉化，會用程序描述不同進制之間的轉化，體會數(shù)學的轉化思想，制定以下三維目標：
1、知識與技能
學生理解各種進位制與十進制之間轉換的規(guī)律，會利用十進制與各種進制之間的聯(lián)系進行各種進位制之間的轉換。
2、過程與方法
學生經(jīng)歷得出各種進位制與十進制之間轉換的規(guī)律的過程，進一步掌握進位制之間轉換的方法。
3、情感、態(tài)度與價值觀
學生通過合作完成任務后，領悟十進制，二進制的特點，了解計算機的電路與二進制的聯(lián)系，進一步認識到計算機與數(shù)學的聯(lián)系，培養(yǎng)他們的合作精神和嚴謹?shù)膽B(tài)度。
二、教學重點、難點
重點：各進位制之間的轉換。
解決策略：讓學生弄懂各進位制的特點和聯(lián)系，再搭配習題講解。
難點：“除k取余法”的理解。
解決策略：先給出具體的例子講解，再延伸到一般的情況。
三、學法與教學用具
1、學法：講授法、歸納法、討論法。
2、教學用具：多媒體，投影儀
四、教學過程
�。ㄒ唬┮胝n題
在日常生活中，我們最熟悉、最常用的是十進制，據(jù)說這與古人曾以手指計數(shù)有關，愛好天文學的古人也曾經(jīng)采用七進制、十二進制、六十進制，至今我們?nèi)匀皇褂靡恢芷咛�、一年十二個月、一小時六十分的歷法.今天我們來學習一下進位制.
（二）研探新知
進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的計數(shù)系統(tǒng)，約定滿二進一，就是二進制；滿十進一，就是十進制；滿十二進一，就是十二進制；滿六十進一，就是六十進制等等.也就是說：“滿幾進一”就是幾進制，幾進制的基數(shù)（都是大于1的整數(shù)）就是幾. 在日常生活中，我們最熟悉、最常用的是十進制，據(jù)說這與古人曾以手指計數(shù)有關，愛好天文學的古人也曾經(jīng)采用七進制、十二進制、六十進制，至今我們?nèi)匀皇褂靡恢芷咛臁⒁荒晔䝼�月、一小時六十分的歷法.
十進制使用0 ~9十個數(shù)字.計數(shù)時，幾個數(shù)字排成一行，從右起，第一位是個位，個位上的數(shù)字是幾，就表示幾個一；第二位是十位，十位上的數(shù)字是幾，就表示幾個十；接著依次是百位、千位、萬位……
例如：十進制數(shù)3 721中的3表示3個千，7表示7個百，2表示2個十，1表示1個一.于是，我們得到下面的式子： 32103 721=3×10+7×10+2×10+1×10.
與十進制類似，其他的進位制也可以按照位置原則計數(shù).由于每一種進位制的基數(shù)不同，所用的數(shù)字個數(shù)也不同.如二進制用0和1兩個數(shù)字，七進制用0~6七個數(shù)字. 一般地，若k是一個大于1的整數(shù)，那么以k為基數(shù)的k進制數(shù)可以表示為一串數(shù)字連寫在一起的形式 aa…aa（k）（0＜a＜k，0≤a，…，a，a＜k). nn-110nn-110其他進位制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)的冪的乘積之和的形式，如 543210110 011=1×2+1×2+0×2+0×2+1×2+1×2， （2）32107 342=7×8+3×8+4×8+2×8. （8）非十進制數(shù)轉換為十進制數(shù)比較簡單，只要計算下面的式子值即可： nn-1aa…aa=a×k+a×k+…+a×k+a. nn-110(k)nn-110第一步：從左到右依次取出k進制數(shù)aa…aa(k)各位上的數(shù)字，乘以相應的k的冪，knn-110nn-10的冪從n開始取值，每次遞減1，遞減到0，即a×k,a×k,…,a×k,a×k；
nn-110第二步：把所得到的乘積加起來，所得的結果就是相應的十進制數(shù). 關于進位制的轉換，教科書上以十進制和二進制之間的轉換為例講解，并推廣到十進制和其他進制之間的轉換.這樣做的原因是，計算機是以二進制的形式進行存儲和計算數(shù)據(jù)的，而一般我們傳輸給計算機的數(shù)據(jù)是十進制數(shù)據(jù)，因此計算機必須先將十進制數(shù)轉換為二進制數(shù)，再處理，顯然運算后首次得到的結果為二進制數(shù)，同時計算機又把運算結果由二進制數(shù)轉換成十進制數(shù)輸出.
1°十進制數(shù)轉換成非十進制數(shù)
把十進制數(shù)轉換為二進制數(shù)，教科書上提供了“除2取余法”，我們可以類比得到十進制數(shù)轉換成k進制數(shù)的算法“除k取余法”.
2°非十進制之間的轉換
一個自然的想法是利用十進制作為橋梁.教科書上提供了一個二進制數(shù)據(jù)與16進制數(shù)據(jù)之間的互化的方法，也就是先由二進制數(shù)轉化為十進制數(shù)，再由十進制數(shù)轉化成為16進制數(shù).
�。ㄈ┓独治�
例1 把二進制數(shù)110 011化為十進制數(shù).
(2)543210解：110 011=1×2+1×2+0×2+0×2+1×2+1×2=1×32+1×16+1×2+1=51.
(2)點評：先把二進制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式，再按照十進制的運算規(guī)則計算出結果.
例2設計一個算法，把k進制數(shù)a（共有n位）化為十進制數(shù)b. i-1算法分析：從例1的計算過程可以看出，計算k進制數(shù)a的右數(shù)第i位數(shù)字a與k的乘ii-1積a·k，再將其累加，這是一個重復操作的步驟.所以，可以用循環(huán)結構來構造算法. i
算法步驟如下：
第一步，輸入a，k和n的值.
第二步，將b的值初始化為0，i的值初始化為1. i-1第三步，b=b+a·k，i=i+1. i第四步，判斷i＞n是否成立.若是，則執(zhí)行第五步；否則，返回第三步. 第五步，輸出b的值.
程序框圖如右圖：
程序：
INPUT “a,k，n=”；a，k，n b=0
i=1
t=a MOD 10 DO
b=b+t*k^（i-1）
a=a\10
t=a MOD 10
i=i+1
LOOP UNTIL i＞n
PRINT b END
例3 把89化為二進制數(shù).
解：根據(jù)二進制數(shù)“滿二進一”的原則，可以用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×（2+1）+1）+0）+0）+1 6543210=…=1×2+0×2+1×2+1×2+0×2+0×2+1×2
【算法案例教案】相關文章：
案例教學教案02-09
《導數(shù)運算法則》教案01-09
加、減法的一些簡便算法教案04-12
分數(shù)除法的意義和計算法則教案02-26
溝通的案例【經(jīng)典】10-01
溝通的案例09-27
溝通的案例（精選）09-28
教學反思案例05-17
教學反思案例09-27