高中數(shù)學(xué)算法案例教案新課標(biāo)人教版必修3(B)

算法案例第一、二課時(shí)輾轉(zhuǎn)相除法與更相減損術(shù)（1）授課目標(biāo)（a）知識(shí)與技術(shù)理解輾轉(zhuǎn)相除法與更相減損術(shù)中包括的數(shù)學(xué)原理，并能依照這些原理進(jìn)行算法分析?；灸芤勒账惴ㄕZ句與程序框圖的知識(shí)設(shè)計(jì)完滿的程序框圖并寫出算法程序。（b）過程與方法在輾轉(zhuǎn)相除法與更相減損術(shù)求最大合約數(shù)的學(xué)習(xí)過程中比較我們常有的約分求公因式的方法，比較它們?cè)谒惴ㄉ系牟町?，并從程序的學(xué)習(xí)中領(lǐng)悟數(shù)學(xué)的謹(jǐn)慎，領(lǐng)悟數(shù)學(xué)算法計(jì)算機(jī)辦理的結(jié)合方式，初步掌握把數(shù)學(xué)算法轉(zhuǎn)變成計(jì)算機(jī)語言的一般步驟。（c）神情與價(jià)值經(jīng)過閱讀中國古代數(shù)學(xué)中的算法案例，領(lǐng)悟中國古代數(shù)學(xué)對(duì)世界數(shù)學(xué)發(fā)展的貢獻(xiàn)。在學(xué)習(xí)古代數(shù)學(xué)家解決數(shù)學(xué)識(shí)題的方法的過程中培養(yǎng)謹(jǐn)慎的邏輯思想能力，在利用算法解決數(shù)學(xué)識(shí)題的過程中培養(yǎng)理性的精神和著手實(shí)踐的能力。（2）授課重難點(diǎn)重點(diǎn)：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大合約數(shù)的方法。難點(diǎn)：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法變換成程序框圖與程序語言。（3）學(xué)法與授課用具學(xué)法：在理解最大合約數(shù)的基礎(chǔ)上去發(fā)現(xiàn)輾轉(zhuǎn)相除法與更相減損術(shù)中的數(shù)學(xué)規(guī)律，并能模擬已經(jīng)學(xué)過的程序框圖與算法語句設(shè)計(jì)出輾轉(zhuǎn)相除法與更相減損術(shù)的程序框圖與算法程序。授課用具：電腦，計(jì)算器，圖形計(jì)算器（4）授課設(shè)想（一）創(chuàng)立情況，揭穿課題1.教師第一提出問題：在初中，我們已經(jīng)學(xué)過求最大合約數(shù)的知識(shí)，你能求出18與30的合約數(shù)嗎？接著教師進(jìn)一步提出問題，我們都是利用找合約數(shù)的方法來求最大合約數(shù)，若是合約數(shù)比較大而且依照我們的察看又不能夠獲取一些合約數(shù)，我們又應(yīng)當(dāng)怎樣求它們的最大合約數(shù)？比方求8251與6105的最大合約數(shù)？這就是我們這一堂課所要商議的內(nèi)容。（二）研探新知輾轉(zhuǎn)相除法例1求兩個(gè)正數(shù)8251和6105的最大合約數(shù)。（分析：8251與6105兩數(shù)都比較大，而且沒有顯然的合約數(shù)，如能把它們都變小一點(diǎn)，依照已有的知識(shí)即可求出最大合約數(shù)）解：8251＝6105×1＋2146顯然8251的最大合約數(shù)也必是2146的約數(shù)，同樣6105與2146的合約數(shù)也必是8251的約數(shù)，所以8251與6105的最大合約數(shù)也是6105與2146的最大合約數(shù)。6105＝2146×2＋18132146＝1813×1＋3331813＝333×5＋148333＝148×2＋37148＝37×4＋0則37為8251與6105的最大合約數(shù)。以上我們求最大合約數(shù)的方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右第一提出的。利用輾轉(zhuǎn)相除法求最大合約數(shù)的步驟以下：第一步：用較大的數(shù)m除以較小的數(shù)n獲取一個(gè)商q0和一個(gè)余數(shù)r0；第二步：若r0＝0，則n為m，n的最大合約數(shù)；若r0≠0，則用除數(shù)n除以余數(shù)r0獲取一個(gè)商q1和一個(gè)余數(shù)r1；第三步：若r1＝0，則r1為m，n的最大合約數(shù)；若r1≠0，則用除數(shù)r0除以余數(shù)r1獲取一個(gè)商q2和一個(gè)余數(shù)r2；依次計(jì)算直至rn＝0，此時(shí)所獲取的rn－1即為所求的最大合約數(shù)。練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大合約數(shù)（答案：53）更相減損術(shù)我國早期也有解決求最大合約數(shù)問題的算法，就是更相減損術(shù)。更相減損術(shù)求最大合約數(shù)的步驟以下：可半者半之，不能半者，副置分母·子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯出來為：第一步：隨意給出兩個(gè)正數(shù)；判斷它們可否都是偶數(shù)。若是，用2約簡(jiǎn)；若不是，履行第二步。第二步：以較大的數(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)相減，即：98－63＝3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7所以，98與63的最大合約數(shù)是7。練習(xí)：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大合約數(shù)。（答案：12）比較輾轉(zhuǎn)相除法與更相減損術(shù)的差異（1）都是求最大合約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小差異較大時(shí)計(jì)算次數(shù)的差異較顯然。（2）從結(jié)果表現(xiàn)形式來看，輾轉(zhuǎn)相除法表現(xiàn)結(jié)果是以相除余數(shù)為術(shù)則以減數(shù)與差相等而獲取

0則獲取，而更相減損輾轉(zhuǎn)相除法與更相減損術(shù)計(jì)算的程序框圖及程序利用輾轉(zhuǎn)相除法與更相減損術(shù)的計(jì)算算法，我們能夠設(shè)計(jì)出程序框圖以及BSAIC程序來在計(jì)算機(jī)上實(shí)現(xiàn)輾轉(zhuǎn)相除法與更相減損術(shù)求最大合約數(shù)，下面由同學(xué)們?cè)O(shè)計(jì)相應(yīng)框圖并相互之間檢查框圖與程序的正確性，并在計(jì)算機(jī)上考證自己的結(jié)果。（1）輾轉(zhuǎn)相除法的程序框圖及程序程序框圖：開始輸入兩個(gè)正整數(shù)m，nm>n?否是r=mMODn否r=0?是輸出n結(jié)束程序：

x=nn=mm=xn=rm=nINPUT“m=”;mINPUT“n=”;nIFm<nTHENx=mm=nn=xENDIFr=mMODnWHILEr<>0r=mMODnm=nn=rWENDPRINTmEND講堂練習(xí).用輾轉(zhuǎn)相除法求以下各組數(shù)的最大合約數(shù)，并在自己編寫的BASIC程序中考證。（1）225；135（2）98；196（3）72；168（4）153；119二.思慮：用求質(zhì)因數(shù)的方法可否求上述4組數(shù)的最大合約數(shù)？可否利用求質(zhì)因數(shù)的算法設(shè)計(jì)出程序框圖及程序？若能，在電腦上測(cè)試自己的程序；若不能夠說明無法實(shí)現(xiàn)的原因。三。思慮：利用輾轉(zhuǎn)相除法可否能夠求兩數(shù)的最大公倍數(shù)？試設(shè)計(jì)程序框圖并變換成程序在BASIC中實(shí)現(xiàn)。小結(jié)：輾轉(zhuǎn)相除法與更相減損術(shù)求最大合約數(shù)的計(jì)算方法及完滿算法程序的編寫。（5）談?wù)撛O(shè)計(jì)作業(yè)：P38A（1）B（2）補(bǔ)充：設(shè)計(jì)更相減損術(shù)求最大合約數(shù)的程序框圖第三、四課時(shí)秦九韶算法與排序（1）授課目標(biāo)（a）知識(shí)與技術(shù)認(rèn)識(shí)秦九韶算法的計(jì)算過程，并理解利用秦九韶算法能夠減少計(jì)算次數(shù)提高計(jì)算效率的實(shí)質(zhì)。掌握數(shù)據(jù)排序的原理能使用直接排序法與冒泡排序法給一組數(shù)據(jù)排序，進(jìn)而能設(shè)計(jì)冒泡排序法的程序框圖及程序，理解數(shù)學(xué)算法與計(jì)算機(jī)算法的差異，理解計(jì)算機(jī)對(duì)數(shù)學(xué)的協(xié)助作用。（b）過程與方法模擬秦九韶計(jì)算方法，領(lǐng)悟先人計(jì)算構(gòu)想的巧妙。能依照排序法中的直接插入排序法與冒泡排序法的步驟，認(rèn)識(shí)數(shù)學(xué)計(jì)算變換為計(jì)算機(jī)計(jì)算的路子，進(jìn)而研究計(jì)算機(jī)算法與數(shù)學(xué)算法的差異，領(lǐng)悟計(jì)算機(jī)對(duì)數(shù)學(xué)學(xué)習(xí)的協(xié)助作用。（c）神情與價(jià)值經(jīng)過對(duì)秦九韶算法的學(xué)習(xí)，認(rèn)識(shí)中國古代數(shù)學(xué)家對(duì)數(shù)學(xué)的貢獻(xiàn)，充分認(rèn)識(shí)到我國文化歷史的悠久。經(jīng)過對(duì)排序法的學(xué)習(xí)，領(lǐng)悟數(shù)學(xué)計(jì)算與計(jì)算機(jī)計(jì)算的差異，充分認(rèn)識(shí)信息技術(shù)對(duì)數(shù)學(xué)的促使。（2）授課重難點(diǎn)重點(diǎn)：1.秦九韶算法的特點(diǎn)兩種排序法的排序步驟及計(jì)算機(jī)程序設(shè)計(jì)難點(diǎn)：1.秦九韶算法的先進(jìn)性理解排序法的計(jì)算機(jī)程序設(shè)計(jì)（3）學(xué)法與授課用具學(xué)法：1.研究秦九韶算法比較一般計(jì)算方法被騙算次數(shù)的改變，領(lǐng)悟科學(xué)的計(jì)算。模擬排序法中數(shù)字排序的步驟，理解計(jì)算機(jī)計(jì)算的一般步驟，領(lǐng)悟數(shù)學(xué)計(jì)算在計(jì)算機(jī)上推行的要求。授課用具：電腦，計(jì)算器，圖形計(jì)算器（4）授課設(shè)想（一）創(chuàng)立情況，揭穿課題我們已經(jīng)學(xué)過了多項(xiàng)式的計(jì)算，下面我們計(jì)算一下多項(xiàng)式f(x)x5x4x3x2x1當(dāng)x5時(shí)的值，并統(tǒng)計(jì)所做的計(jì)算的種類及計(jì)算次數(shù)。依照我們的計(jì)算統(tǒng)計(jì)能夠得出我們共需要10次乘法運(yùn)算，5次加法運(yùn)算。我們把多項(xiàng)式變形為：()x2(1x(1x(1)))x1再統(tǒng)計(jì)一下計(jì)算當(dāng)x5時(shí)的值fxx時(shí)需要的計(jì)算次數(shù)，能夠得出僅需4次乘法和5次加法運(yùn)算即可得出結(jié)果。顯然少了6次乘法運(yùn)算。這種算法就叫秦九韶算法。（二）研探新知秦九韶計(jì)算多項(xiàng)式的方法f(x)anxnan1xn1an2xn2a1xa0(anxn1an1xn2an2xn3a1)xa0((anxn2an1xn3a2)xa1)xa0(((anxan1)xan2)xa1)a0例1已知一個(gè)5次多項(xiàng)式為f(x)5x52x43.5x32.6x2用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x5時(shí)的值。解：略思慮：（1）例1計(jì)算時(shí)需要多少次乘法計(jì)算？多少次加法計(jì)算？（2）在利用秦九韶算法計(jì)算n次多項(xiàng)式當(dāng)xx0時(shí)需要多少次乘法計(jì)算和多少次加法計(jì)算？練習(xí)：利用秦九韶算法計(jì)算f(x)0.83x540.16x30.33x20.5x1當(dāng)x5時(shí)的值，并統(tǒng)計(jì)需要多少次乘法計(jì)算和多少次加法計(jì)算？例2設(shè)計(jì)利用秦九韶算法計(jì)算5次多項(xiàng)式f(x)a5x5a4x4a3x3a2x2a1xa0當(dāng)xx0時(shí)的值的程序框圖。解：程序框圖以下：開始輸入f(x)的系數(shù)：a1,a2,a3,a4,a5輸入x0n=1v=a5n=n+1v=vx0+a5-n是n≤5否輸出v結(jié)束練習(xí)：利用程序框圖試編寫B(tài)ASIC程序并在計(jì)算機(jī)上測(cè)試自己的程序。排序在信息技術(shù)課中我們學(xué)習(xí)過電子表格,電子表格對(duì)分?jǐn)?shù)的排序特別簡(jiǎn)單,那么電子計(jì)算機(jī)是怎么對(duì)數(shù)據(jù)進(jìn)行排序的呢?閱讀課本P30—P31面的內(nèi)容,回答下面的問題:(1)排序法中的直接插入排序法與冒泡排序法的步驟有什么差異?冒泡法排序中對(duì)5個(gè)數(shù)字進(jìn)行排序最多需要多少趟?(3)在冒泡法排序?qū)?個(gè)數(shù)字進(jìn)行排序的每一趟中需要比較大小幾次?游戲:5位同學(xué)每人拿一個(gè)數(shù)字牌在講臺(tái)演出示冒泡排序法對(duì)5個(gè)數(shù)據(jù)4,11,7,9,6過程,讓學(xué)生經(jīng)過察看表達(dá)冒泡排序法的主要步驟.并結(jié)合步驟解決例3的問題.例3用冒泡排序法對(duì)數(shù)據(jù)7,5,3,9,1從小到大進(jìn)行排序解:P32

排序的練習(xí):寫出用冒泡排序法對(duì)5個(gè)數(shù)據(jù)4,11,7,9,6排序的過程中每一趟排序的結(jié)果.例4設(shè)計(jì)冒泡排序法對(duì)5個(gè)數(shù)據(jù)進(jìn)行排序的程序框圖.解:程序框圖以下:開始輸入a1,a2,a3,a4,a5r=1i=1否a>a是x=aa=ai=i+1r=r+1ai+1=x否i=5是否r=5是輸出a1,a2,a3,a4,a5結(jié)束思慮:直接排序法的程序框圖怎樣設(shè)計(jì)?可否把上述程序框圖轉(zhuǎn)變成程序?練習(xí):用直接排序法對(duì)例3中的數(shù)據(jù)從小到大排序小結(jié):秦九韶算法計(jì)算多項(xiàng)式的值及程序設(shè)計(jì)數(shù)字排序法中的常有的兩種排序法直接插入排序法與冒泡排序法冒泡法排序的計(jì)算機(jī)程序框圖設(shè)計(jì)（5）談?wù)撛O(shè)計(jì)作業(yè)：P38A（2）（3）補(bǔ)充：設(shè)計(jì)程序框圖對(duì)上述兩組數(shù)進(jìn)行排序第五課時(shí)進(jìn)位制（1）授課目標(biāo)（a）知識(shí)與技術(shù)認(rèn)識(shí)各樣進(jìn)位制與十進(jìn)制之間變換的規(guī)律，會(huì)利用各樣進(jìn)位制與十進(jìn)制之間的聯(lián)系進(jìn)行各樣進(jìn)位制之間的變換。（b）過程與方法學(xué)習(xí)各樣進(jìn)位制變換成十進(jìn)制的計(jì)算方法，研究十進(jìn)制變換為各樣進(jìn)位制的除k去余法，并理解其中的數(shù)學(xué)規(guī)律。（c）神情與價(jià)值領(lǐng)悟十進(jìn)制，二進(jìn)制的特點(diǎn)，認(rèn)識(shí)計(jì)算機(jī)的電路與二進(jìn)制的聯(lián)系，進(jìn)一步認(rèn)識(shí)到計(jì)算機(jī)與數(shù)學(xué)的聯(lián)系。（2）授課重難點(diǎn)重點(diǎn)：各進(jìn)位制表示數(shù)的方法及各進(jìn)位制之間的變換難點(diǎn)：除k去余法的理解以及各進(jìn)位制之間變換的程序框圖的設(shè)計(jì)（3）學(xué)法與授課用具學(xué)法：在學(xué)習(xí)各樣進(jìn)位制特點(diǎn)的同時(shí)商議進(jìn)位制表示數(shù)與十進(jìn)制表示數(shù)的差異與聯(lián)系，熟悉各樣進(jìn)位制表示數(shù)的方法，進(jìn)而理解十進(jìn)制變換為各樣進(jìn)位制的除k去余法。授課用具：電腦，計(jì)算器，圖形計(jì)算器（4）授課設(shè)想（一）創(chuàng)立情況，揭穿課題我們常有的數(shù)字都是十進(jìn)制的,可是其實(shí)不是生活中的每一種數(shù)字都是十進(jìn)制的.比方時(shí)間和角度的單位用六十進(jìn)位制,電子計(jì)算機(jī)用的是二進(jìn)制.那么什么是進(jìn)位制?不同樣的進(jìn)位制之間又又什么聯(lián)系呢?（二）研探新知進(jìn)位制是一種記數(shù)方式，用有限的在不同樣的地址表示不同樣的數(shù)值?？墒褂脭?shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進(jìn)位制，簡(jiǎn)稱n進(jìn)制?，F(xiàn)在最常用的是，平常使用10個(gè)0-9進(jìn)行記數(shù)。關(guān)于任何一個(gè)數(shù)，我們能夠用不同樣的進(jìn)位制來表示。比方：57，能夠用表示為111001，也能夠用表示為71、用表示為39，它們所代表的數(shù)值都是同樣的。表示二進(jìn)制數(shù),34表示5表示各樣進(jìn)位制數(shù)一般在數(shù)字右下腳加注來表示,如111001(5)(2)進(jìn)制數(shù).電子計(jì)算機(jī)一般都使用二進(jìn)制,下面我們來進(jìn)行二進(jìn)制與十進(jìn)制之間的轉(zhuǎn)變例1把二進(jìn)制數(shù)110011(2)化為十進(jìn)制數(shù).解:110011=1*25+1*24+0*23+1*24+0*22+1*21+1*20=32+16+2+1=51例2把89化為二進(jìn)制數(shù).解:依照二進(jìn)制數(shù)滿二進(jìn)一的原則,能夠用2連續(xù)去除89或所得商,爾后去余數(shù).詳細(xì)的計(jì)算方法以下:89=2*44+144=2*22+022=2*11+011=2*5+15=2*2+1所以:89=2*(2*(2*(2*(2*2+1)+1)+0)+0)+1=1*26+0*25+1*24+1*23+0*22+0*21+1*20=1011001(2)這種算法叫做除2取余法,還能夠用下面的除法算式表示:289余數(shù)24412220211025122121001把上式中的各步所得的余數(shù)從下到上排列即可獲取89=1011001(2)上述方法也能夠推行為把十進(jìn)制化為k進(jìn)制數(shù)的算法,這種算法成為除k取余法.當(dāng)數(shù)字較小時(shí),也可直接利用各進(jìn)位制表示數(shù)的特點(diǎn),都是以冪的形式來表示各位數(shù)字,比方2*103表示千位數(shù)字是2,所以能夠直接求出各位數(shù)字.即把89變換為二進(jìn)制數(shù)時(shí),直接察看得出89與64最湊近故89=64*1+25同理:25=16*1+99=8*!+1即89=64*1+16*1+8*!+1=1*26+1*24+1*23+1*20位6543210數(shù)數(shù)1011001字即89=1011001(2)練習(xí):(1)把73變換為二進(jìn)制數(shù)利用除k取余法把89變換為5進(jìn)制數(shù)把k進(jìn)制數(shù)a(共有n位)變換為十進(jìn)制數(shù)b的過程能夠利用計(jì)算機(jī)程序來實(shí)現(xiàn),語句為:INPU