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

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

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

排序的練習:寫出用冒泡排序法對5個數據4,11,7,9,6排序的過程中每一趟排序的結果.例4設計冒泡排序法對5個數據進行排序的程序框圖.解:程序框圖以下:開始輸入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結束思慮:直接排序法的程序框圖怎樣設計?可否把上述程序框圖轉變成程序?練習:用直接排序法對例3中的數據從小到大排序小結:秦九韶算法計算多項式的值及程序設計數字排序法中的常有的兩種排序法直接插入排序法與冒泡排序法冒泡法排序的計算機程序框圖設計（5）談論設計作業：P38A（2）（3）補充：設計程序框圖對上述兩組數進行排序第五課時進位制（1）授課目標（a）知識與技術認識各樣進位制與十進制之間變換的規律，會利用各樣進位制與十進制之間的聯系進行各樣進位制之間的變換。（b）過程與方法學習各樣進位制變換成十進制的計算方法，研究十進制變換為各樣進位制的除k去余法，并理解其中的數學規律。（c）神情與價值領悟十進制，二進制的特點，認識計算機的電路與二進制的聯系，進一步認識到計算機與數學的聯系。（2）授課重難點重點：各進位制表示數的方法及各進位制之間的變換難點：除k去余法的理解以及各進位制之間變換的程序框圖的設計（3）學法與授課用具學法：在學習各樣進位制特點的同時商議進位制表示數與十進制表示數的差異與聯系，熟悉各樣進位制表示數的方法，進而理解十進制變換為各樣進位制的除k去余法。授課用具：電腦，計算器，圖形計算器（4）授課設想（一）創立情況，揭穿課題我們常有的數字都是十進制的,可是其實不是生活中的每一種數字都是十進制的.比方時間和角度的單位用六十進位制,電子計算機用的是二進制.那么什么是進位制?不同樣的進位制之間又又什么聯系呢?（二）研探新知進位制是一種記數方式，用有限的在不同樣的地址表示不同樣的數值。可使用數字符號的個數稱為基數，基數為n，即可稱n進位制，簡稱n進制?，F在最常用的是，平常使用10個0-9進行記數。關于任何一個數，我們能夠用不同樣的進位制來表示。比方：57，能夠用表示為111001，也能夠用表示為71、用表示為39，它們所代表的數值都是同樣的。表示二進制數,34表示5表示各樣進位制數一般在數字右下腳加注來表示,如111001(5)(2)進制數.電子計算機一般都使用二進制,下面我們來進行二進制與十進制之間的轉變例1把二進制數110011(2)化為十進制數.解:110011=1*25+1*24+0*23+1*24+0*22+1*21+1*20=32+16+2+1=51例2把89化為二進制數.解:依照二進制數滿二進一的原則,能夠用2連續去除89或所得商,爾后去余數.詳細的計算方法以下: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余數24412220211025122121001把上式中的各步所得的余數從下到上排列即可獲取89=1011001(2)上述方法也能夠推行為把十進制化為k進制數的算法,這種算法成為除k取余法.當數字較小時,也可直接利用各進位制表示數的特點,都是以冪的形式來表示各位數字,比方2*103表示千位數字是2,所以能夠直接求出各位數字.即把89變換為二進制數時,直接察看得出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數數1011001字即89=1011001(2)練習:(1)把73變換為二進制數利用除k取余法把89變換為5進制數把k進制數a(共有n位)變換為十進制數b的過程能夠利用計算機程序來實現,語句為:INPU