B3--13算法案例(4課時(shí))

1、高中數(shù)學(xué)新課標(biāo)必修課時(shí)計(jì)劃 東升高中高一備課組 授課時(shí)間: 2006年 月 日(星期 )第 節(jié) 總第 課時(shí)第一課時(shí) 1.3.1 算法案例-輾轉(zhuǎn)相除法與更相減損術(shù)教學(xué)要求：理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊(yùn)含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析； 基本能根據(jù)算法語(yǔ)句與程序框圖的知識(shí)設(shè)計(jì)出輾轉(zhuǎn)相除法與更相減損術(shù)完整的程序框圖并寫(xiě)出它們的算法程序.教學(xué)重點(diǎn)：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法.教學(xué)難點(diǎn)：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語(yǔ)言. 教學(xué)過(guò)程：一、復(fù)習(xí)準(zhǔn)備：1. 回顧算法的三種表述：自然語(yǔ)言、程序框圖（三種邏輯結(jié)構(gòu)）、程序語(yǔ)言（五種基本語(yǔ)句）. 2. 提問(wèn)：小學(xué)學(xué)

2、過(guò)的求兩個(gè)數(shù)最大公約數(shù)的方法？（先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái).）口算出36和64的最大公約數(shù). 除了用這種方法外還有沒(méi)有其它方法？，和28的最大公約數(shù)就是64和36的最大公約數(shù)，反復(fù)進(jìn)行這個(gè)步驟，直至，得出4即是36和64的最大公約數(shù).二、講授新課：1. 教學(xué)輾轉(zhuǎn)相除法：例1：求兩個(gè)正數(shù)1424和801的最大公約數(shù). 分析：可以利用除法將大數(shù)化小，然后逐步找出兩數(shù)的最大公約數(shù). （適用于兩數(shù)較大時(shí)）以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法，也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的. 利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如

3、下：（1）用較大的數(shù)m除以較小的數(shù)n得到一個(gè)商和一個(gè)余數(shù)；（2）若0，則n為m，n的最大公約數(shù)；若0，則用除數(shù)n除以余數(shù)得到一個(gè)商和一個(gè)余數(shù)；（3）若0，則為m，n的最大公約數(shù)；若0，則用除數(shù)除以余數(shù)得到一個(gè)商和一個(gè)余數(shù)；依次計(jì)算直至0，此時(shí)所得到的即為所求的最大公約數(shù). 由上述步驟可以看出，輾轉(zhuǎn)相除法中的除法是一個(gè)反復(fù)執(zhí)行的步驟，且執(zhí)行次數(shù)由余數(shù)是否等于0來(lái)決定，所以我們可以把它看成一個(gè)循環(huán)體，它的程序框圖如右圖：（師生共析，寫(xiě)出輾轉(zhuǎn)相除法完整的程序框圖和程序語(yǔ)言）練習(xí)：求兩個(gè)正數(shù)8251和2146的最大公約數(shù). （乘法格式、除法格式）2. 教學(xué)更相減損術(shù)：我國(guó)早期也有求最大公約數(shù)問(wèn)題的算法

4、，就是更相減損術(shù). 在九章算術(shù)中有更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之. 翻譯為：（1）任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù). 若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步.（2）以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù). 繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù).例2：用更相減損術(shù)求91和49的最大公約數(shù). 分析：更相減損術(shù)是利用減法將大數(shù)化小，直到所得數(shù)相等時(shí)，這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù). （反思：輾轉(zhuǎn)相除法與更相減損術(shù)是否存在相通的地方）練習(xí)：用更相減損術(shù)求

5、72和168的最大公約數(shù). 3. 小結(jié)：輾轉(zhuǎn)相除法與更相減損術(shù)及比較都是求最大公約數(shù)的方法，輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少；結(jié)果上，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0得到，而更相減損術(shù)則以減數(shù)與差相等而得到.三、鞏固練習(xí)：1、練習(xí)：教材P35第1題2、作業(yè)：教材P38第1題第二課時(shí) 1.3.2 算法案例-秦九韶算法教學(xué)要求：了解秦九韶算法的計(jì)算過(guò)程，并理解利用秦九韶算法可以減少計(jì)算次數(shù)、提高計(jì)算效率的實(shí)質(zhì)；理解數(shù)學(xué)算法與計(jì)算機(jī)算法的區(qū)別，理解計(jì)算機(jī)對(duì)數(shù)學(xué)的輔助作用. 教學(xué)重點(diǎn)：秦九韶算法的特點(diǎn)及其程序設(shè)計(jì). 教學(xué)難點(diǎn)：秦九韶算法的先進(jìn)性理解及其

6、程序設(shè)計(jì). 教學(xué)過(guò)程：一、復(fù)習(xí)準(zhǔn)備：1. 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求出兩個(gè)正數(shù)623和1513的最大公約數(shù). 2. 設(shè)計(jì)一個(gè)求多項(xiàng)式當(dāng)時(shí)的值的算法. （學(xué)生自己提出一般的解決方案：將代入多項(xiàng)式進(jìn)行計(jì)算即可）提問(wèn)：上述算法在計(jì)算時(shí)共用了多少次乘法運(yùn)算？多少次加法運(yùn)算？此方案有何優(yōu)缺點(diǎn)？(上述算法一共做了5432115次乘法運(yùn)算，5次加法運(yùn)算. 優(yōu)點(diǎn)是簡(jiǎn)單、易懂；缺點(diǎn)是不通用，不能解決任意多項(xiàng)式的求值問(wèn)題，而且計(jì)算效率不高.)二、講授新課：1. 教學(xué)秦九韶算法： 提問(wèn)：在計(jì)算的冪值時(shí)，可以利用前面的計(jì)算結(jié)果，以減少計(jì)算量，即先計(jì)算，然后依次計(jì)算，的值，這樣計(jì)算上述多項(xiàng)式的值，一共需要多少次乘法

7、，多少次加法?（上述算法一共做了4次乘法運(yùn)算，5次加法運(yùn)算） 結(jié)論：第二種做法與第一種做法相比，乘法的運(yùn)算次數(shù)減少了，因而能提高運(yùn)算效率，而且對(duì)于計(jì)算機(jī)來(lái)說(shuō)，做一次乘法所需的運(yùn)算時(shí)間比做一次加法要長(zhǎng)得多，因此第二種做法能更快地得到結(jié)果. 更有效的一種算法是：將多項(xiàng)式變形為：，依次計(jì)算，故. 這種算法就是“秦九韶算法”. （注意變形，強(qiáng)調(diào)格式） 練習(xí)：用秦九韶算法求多項(xiàng)式當(dāng)時(shí)的值. （學(xué)生板書(shū)師生共評(píng)教師提問(wèn)：上述算法共需多少次乘法運(yùn)算？多少次加法運(yùn)算？） 如何用秦九韶算法完成一般多項(xiàng)式的求值問(wèn)題？改寫(xiě)：.首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，即，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即，. 結(jié)論：

8、秦九韶算法將求次多項(xiàng)式的值轉(zhuǎn)化為求個(gè)一次多項(xiàng)式的值，整個(gè)過(guò)程只需次乘法運(yùn)算和次加法運(yùn)算；觀察上述個(gè)一次式，可發(fā)出的計(jì)算要用到的值，若令，可得到下列遞推公式：. 這是一個(gè)反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn). 練習(xí)：用秦九韶算法求多項(xiàng)式當(dāng)時(shí)的值并畫(huà)出程序框圖. 2. 小結(jié)：秦九韶算法的特點(diǎn)及其程序設(shè)計(jì)三、鞏固練習(xí)：1、練習(xí)：教材P35第2題2、作業(yè)：教材P36第2題第三課時(shí) 1.3.3 算法案例-進(jìn)位制教學(xué)要求：了解各種進(jìn)位制與十進(jìn)制之間轉(zhuǎn)換的規(guī)律，會(huì)利用各種進(jìn)位制與十進(jìn)制之間的聯(lián)系進(jìn)行各種進(jìn)位制之間的轉(zhuǎn)換；學(xué)習(xí)各種進(jìn)位制轉(zhuǎn)換成十進(jìn)制的計(jì)算方法，研究十進(jìn)制轉(zhuǎn)換為各種進(jìn)位制的除k去余法，并理解其

9、中的數(shù)學(xué)規(guī)律.教學(xué)重點(diǎn)：各種進(jìn)位制之間的互化.教學(xué)難點(diǎn)：除k取余法的理解以及各進(jìn)位制之間轉(zhuǎn)換的程序框圖及其程序的設(shè)計(jì).教學(xué)過(guò)程：一、復(fù)習(xí)準(zhǔn)備：1. 試用秦九韶算法求多項(xiàng)式當(dāng)時(shí)的值，分析此過(guò)程共需多少次乘法運(yùn)算？多少次加法運(yùn)算？2. 提問(wèn)：生活中我們常見(jiàn)的數(shù)字都是十進(jìn)制的，但是并不是生活中的每一種數(shù)字都是十進(jìn)制的.比如時(shí)間和角度的單位用六十進(jìn)位制,電子計(jì)算機(jī)用的是二進(jìn)制，舊式的秤是十六進(jìn)制的，計(jì)算一打數(shù)值時(shí)是12進(jìn)制的.那么什么是進(jìn)位制？不同的進(jìn)位制之間又有什么聯(lián)系呢？二、講授新課：1. 教學(xué)進(jìn)位制的概念： 進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)，“滿幾進(jìn)一”就是幾進(jìn)制，幾進(jìn)制的基數(shù)就是

10、幾. 如：“滿十進(jìn)一”就是十進(jìn)制，“滿二進(jìn)一”就是二進(jìn)制. 同一個(gè)數(shù)可以用不同的進(jìn)位制來(lái)表示，比如：十進(jìn)數(shù)57，可以用二進(jìn)制表示為111001，也可以用八進(jìn)制表示為71、用十六進(jìn)制表示為39，它們所代表的數(shù)值都是一樣的. 表示各種進(jìn)位制數(shù)一般在數(shù)字右下腳加注來(lái)表示，如上例中： 一般地，任意一個(gè)進(jìn)制數(shù)都可以表示成不同位上數(shù)字與基數(shù)的冪的乘積之和的形式，即.如：把化為十進(jìn)制數(shù)，=125+124+023+022+121+120=32+16+2+1=51.把八進(jìn)制數(shù)化為十進(jìn)制數(shù)，.2. 教學(xué)進(jìn)位制之間的互化：例1：把二進(jìn)制數(shù)化為十進(jìn)制數(shù). （學(xué)生板書(shū)教師點(diǎn)評(píng)師生共同總結(jié)將非十進(jìn)制轉(zhuǎn)為十進(jìn)制數(shù)的方法）分

11、析此過(guò)程的算法過(guò)程，編寫(xiě)過(guò)程的程序語(yǔ)言. 見(jiàn)P34練習(xí)：將、轉(zhuǎn)化成十進(jìn)制數(shù). 例2、把89化為二進(jìn)制數(shù). 分析：根據(jù)進(jìn)位制的定義，二進(jìn)制就是“滿二進(jìn)一”，可以用2連續(xù)去除89或所得商，然后取余數(shù). （教師板書(shū)）上述方法也可以推廣為把十進(jìn)制化為k進(jìn)制數(shù)的算法,這種算法成為除k取余法.練習(xí)：用除k取余法將89化為四進(jìn)制數(shù)、六進(jìn)制數(shù). 例3、把二進(jìn)制數(shù)化為十進(jìn)制數(shù).解：.（小數(shù)也可利用上述方法化進(jìn)行不同進(jìn)位制之間的互化. ） 變式：化為八進(jìn)制方法：進(jìn)制互化3. 小結(jié)：進(jìn)位制的定義；進(jìn)位制之間的互化. 三、鞏固練習(xí)：1、練習(xí)：教材P35第3題2、作業(yè)：教材P38第3題第四課時(shí) 1.3.4 生活中的算法

12、實(shí)例教學(xué)要求：通過(guò)生活實(shí)例進(jìn)一步了解算法思想.教學(xué)重點(diǎn)：生活實(shí)例的算法分析.教學(xué)難點(diǎn)：算法思想的理解.教學(xué)過(guò)程：一、復(fù)習(xí)準(zhǔn)備：1. 前面學(xué)習(xí)了哪幾種算法案例？每種算法的作用及操作方法是怎樣的？2. 算法思想在我們的生活中無(wú)處不在，如何利用我們所學(xué)習(xí)的知識(shí)解決生活中的實(shí)際問(wèn)題？二、講授新課：1. 霍奇森算法：提問(wèn)：同學(xué)們經(jīng)常會(huì)面對(duì)一個(gè)共同的問(wèn)題，就是有時(shí)有太多的事情要做. 例如，你可能要面臨好幾門(mén)課的作業(yè)的最后期限，你如何合理安排以確保每門(mén)課的作業(yè)都能如期完成？如果根本不可能全部按期完成，你該怎么辦？（霍奇森算法可以使得遲交作業(yè)的數(shù)目減到最小. 這一算法已經(jīng)廣泛應(yīng)用于工業(yè)生產(chǎn)安排的實(shí)踐中.）例如

13、：當(dāng)你拿到下面這組數(shù)據(jù)后，你會(huì)如何安排你的時(shí)間，以確保每門(mén)課的作業(yè)都能如期完成？若不能全部按期完成，也能盡量使遲交作業(yè)的數(shù)目減到最??？學(xué)科數(shù)學(xué)語(yǔ)文歷史外語(yǔ)物理化學(xué)期限/小時(shí) 252421所需時(shí)間/小時(shí)120.510.5 0.5若知道各項(xiàng)作業(yè)的到期日，并且知道或能估計(jì)出完成每項(xiàng)作業(yè)將花費(fèi)的時(shí)間，那么霍奇森算法可用自然語(yǔ)言描述為：把這些作業(yè)按到期日的順序從左到右排列，從最早到期的到最晚到期的；假設(shè)從左到右一項(xiàng)一項(xiàng)做這些作業(yè)的話，計(jì)算出從開(kāi)始到完成某一項(xiàng)作業(yè)時(shí)所花的時(shí)間. 依次做此計(jì)算直到完成了所列表中的全部作業(yè)而沒(méi)有一項(xiàng)作業(yè)會(huì)超期，停止；或你算出某項(xiàng)作業(yè)將會(huì)超期，繼續(xù)第三步；考慮第一項(xiàng)將會(huì)超期的作業(yè)以及它左邊的所有作業(yè)，從中取出花費(fèi)時(shí)間最長(zhǎng)的那項(xiàng)作業(yè)，并把它從表中去掉；回到第二步，并重復(fù)第二到四步，直到做完. 2. 孫子問(wèn)題：韓信是秦末漢初的著名軍事家. 據(jù)說(shuō)有一次漢高祖劉邦在衛(wèi)士的簇?fù)硐聛?lái)到練兵場(chǎng)，劉邦問(wèn)韓信有什么辦法，不要逐個(gè)報(bào)數(shù)，就能知道場(chǎng)上士兵的人數(shù). 韓信先令士兵排成了3列縱隊(duì)進(jìn)行操練，結(jié)果有2人多余；接著他立刻下令將隊(duì)形改為5列縱隊(duì)，這一改又多出3人；隨后他又下令改為7列縱隊(duì)，這一次又剩下2人無(wú)法成整行. 由此得出共有士兵2333人. 如何用現(xiàn)在的算法思想分析這一過(guò)程？孫子算經(jīng)中給出了它的具體解法，其步驟是：選定的倍數(shù)，被3除余1，即70；選定的一個(gè)倍數(shù)，被5除