高中數(shù)學(xué)新課標(biāo)人教A版必修三1.3.算法案例三課時課件

1、算 法 案 例(第一課時)案例1 輾轉(zhuǎn)相除法與更相減損術(shù)1. 回憶算法的三種表述：自然語言程序框圖程序語言三種邏輯結(jié)構(gòu)五種根本語句2. 思考： 小學(xué)學(xué)過的求兩個數(shù)最大公約數(shù)的方法？ 先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.1、求兩個正整數(shù)的最大公約數(shù)1求25和35的最大公約數(shù)2求49和63的最大公約數(shù)25（1）5535749（2）77639所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為72、除了用這種方法外還有沒有其它方法？算出8256和6105的最大公約數(shù). 輾轉(zhuǎn)相除法歐幾里得算法觀察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的

2、過程 第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146結(jié)論： 8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。第二步 對6105和2146重復(fù)第一步的做法6105=21462+1813同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。 為什么呢？思考：從上述的過程你體會到了什么？完整的過程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例2 用輾轉(zhuǎn)

3、相除法求225和135的最大公約數(shù)225=1351+90135=901+4590=452顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù) 顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù) 思考1：從上面的兩個例子可以看出計算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0 輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m

4、 = n q r用程序框圖表示出右邊的過程r=m MOD nm = nn = rr=0?是否思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？ 1、輾轉(zhuǎn)相除法歐幾里得算法1算理：所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。假設(shè)余數(shù)不為零，那么將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，那么這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。2算法步驟第一步：輸入兩個正整數(shù)m,n(mn).第二步：計算m除以n所得的余數(shù)r.第三步：m=n,n=r.第四步：假設(shè)r0,那么m,n的最大公約數(shù)等于m； 否那么轉(zhuǎn)到第二步. 第五步：輸出最大公約數(shù)m.3程序框圖4程序INPUT “

5、m,n=“;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND開始輸入m,n r=m MOD n m=nr=0?是否 n=r 輸出m結(jié)束?九章算術(shù)?更相減損術(shù) 算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。假設(shè)是，那么用2約簡；假設(shè)不是那么執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，那么這個等數(shù)就是所求的最大公約數(shù)。2、更相減損術(shù)1算理：所謂更相減損術(shù)，就是對于給定的兩個數(shù)，

6、用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù)。2算法步驟第一步：輸入兩個正整數(shù)a,b(ab);第二步：假設(shè)a不等于b ,那么執(zhí)行第三步；否那么轉(zhuǎn)到第五步；第三步：把a(bǔ)-b的差賦予r;第四步：如果br, 那么把b賦給a,把r賦給b;否那么把r賦給a，執(zhí)行第二步；第五步：輸出最大公約數(shù)b.3程序框圖4程序INPUT “a,b=“;a,bWHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND開始輸入a,bab?是

7、否 輸出b結(jié)束 b=ra=br=a-br=0?輸出v結(jié)束v=vx+aii=i-1YNi=n-1V=an3程序：INPUT “n=；nINPUT “an=“;aINPUT “x=“;xv=ai=n-1WHILE i=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1WENDPRINT vEND1、多項式f(x)=x5+5x4+10 x3+10 x2+5x+1用秦九韶算法求這個多項式當(dāng)x=-2時的值。練習(xí)：2、多項式f(x)=2x4-6x3-5x2+4x-6用秦九韶算法求這個多項式當(dāng)x=5時的值。作業(yè)：P48 A2小結(jié)：1、秦九韶算法的方法和步驟2、秦九韶算法的程

8、序框圖算法案例3一、進(jìn)位制1、什么是進(jìn)位制？進(jìn)位制是人們?yōu)榱擞嫈?shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)。進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進(jìn)位制，簡稱n進(jìn)制。新課講解： 比方： 滿二進(jìn)一，就是二進(jìn)制； 滿十進(jìn)一，就是十進(jìn)制； 滿十二進(jìn)一，就是十二進(jìn)制； 滿六十進(jìn)一，就是六十進(jìn)制“滿幾進(jìn)一就是幾進(jìn)制，幾進(jìn)制的基數(shù)就是幾.基數(shù)：2、最常見的進(jìn)位制是什么？除此之外還有哪些常見的進(jìn)位制？請舉例說明最常見的進(jìn)位制應(yīng)該是我們數(shù)學(xué)中的十進(jìn)制,比方一般的數(shù)值計算，但是并不是生活中的每一種數(shù)字都是十進(jìn)制的.古人有半斤八兩之說，就是十六進(jìn)制與十進(jìn)制的

9、轉(zhuǎn)換.比方時間和角度的單位用六十進(jìn)位制, 計算“一打數(shù)值時是12進(jìn)制的。電子計算機(jī)用的是二進(jìn)制 。 式中1處在百位，第一個3所在十位，第二個3所在個位，5和9分別處在十分位和百分位。十進(jìn)制數(shù)是逢十進(jìn)一的。 我們最常用最熟悉的就是十進(jìn)制數(shù)，它的數(shù)值局部是十個不同的數(shù)字符號0，1，2，3，4，5，6，7，8，9來表示的。十進(jìn)制：例如133.59，它可用一個多項式來表示：133.59=1*102+3*101+3*100 +5*10-1+9*10-2 實際上，十進(jìn)制數(shù)只是計數(shù)法中的一種，但它不是唯一記數(shù)法。除了十進(jìn)制數(shù)，生產(chǎn)生活中還會遇到非十進(jìn)制的記數(shù)制。如時間：60秒為1分，60分為1小時，它是六十

10、進(jìn)制的。兩根筷子一雙，兩只手套為一副，它們是二進(jìn)制的。其它進(jìn)制： 二進(jìn)制、七進(jìn)制、八進(jìn)制、十二進(jìn)制、六十進(jìn)制二進(jìn)制只有0和1兩個數(shù)字，七進(jìn)制用06七個數(shù)字十六進(jìn)制有09十個數(shù)字及ABCDEF六個字母. 為了區(qū)分不同的進(jìn)位制，常在數(shù)的右下角標(biāo)明基數(shù)，十進(jìn)制一般不標(biāo)注基數(shù).例如十進(jìn)制的133.59，寫成133.59(10)七進(jìn)制的13，寫成13(7)；二進(jìn)制的10，寫成10(2) 一般地，若k是一個大于1的整數(shù)，那么以k為基數(shù)的k進(jìn)制可以表示為一串?dāng)?shù)字連寫在一起的形式：A3、十進(jìn)制的構(gòu)成十進(jìn)制由兩個局部構(gòu)成例如：3721其它進(jìn)位制的數(shù)又是如何的呢？第一、它有09十個數(shù)字；第二、它有“數(shù)位”，即從右

11、往左為個位、十位、百位、千位等等。(用10個數(shù)字來記數(shù)，稱基數(shù)為10)表示有：1個1，2個十， 7個百即7個10的平方，3個千即3個10的立方十進(jìn)制：“滿十進(jìn)一”探究：P40其它進(jìn)制數(shù)化成十進(jìn)制數(shù)公式二、 二進(jìn)制二進(jìn)制是用0、1兩個數(shù)字來描述的如11001二進(jìn)制的表示方法區(qū)分的寫法：110012或者(11001)2八進(jìn)制呢？如7342(8)k進(jìn)制呢？anan-1an-2a1(k)？三、二進(jìn)制與十進(jìn)制的轉(zhuǎn)換1、二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)例1：將二進(jìn)制數(shù)110011(2)化成十進(jìn)制數(shù)。解：根據(jù)進(jìn)位制的定義可知所以，1100112=51其它進(jìn)制數(shù)化成十進(jìn)制數(shù)公式1、將下面的二進(jìn)制數(shù)化為十進(jìn)制數(shù)？（1）1

12、1（2）110練習(xí)2、把其他進(jìn)位制的數(shù)化為十進(jìn)制數(shù)的公式是什么？例2、設(shè)計一個算法，將k進(jìn)制數(shù)a(共有n位)轉(zhuǎn)換為十進(jìn)制數(shù)b。(1)算法步驟:第一步，輸入a,k和n的值；第二步，將b的值初始化為0,i的值初始化為1；第三步，b=b+ai*ki-1, i=i+1第四步，判斷in是否成立.假設(shè)是,那么執(zhí)行第五步,否那么,返回第三步；第五步，輸出b的值.(2)程序框圖:開始輸入a,k,nb=0i=1把a(bǔ)的右數(shù)第i位數(shù)字賦給tb=b+t*ki-1i=i+1in?否是輸出b結(jié)束(3)程序：INPUT “a,k,n=;a,k,nb=0i=1t=a MOD 10DO b=b+t*k(i-1) a=a10 t

13、=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND方法：除2取余法，即用2連續(xù)去除89或所得的商，然后取余數(shù)。例、 把89化為二進(jìn)制數(shù)解：根據(jù)“逢二進(jìn)一的原那么，有892441 2 (2220)+1 2( 2( 2110)+0)+1 2 (2 (2 (2 51)+0)+0)+15 2 212222221100189126025124123022021120所以：89=101100122222321001222422200122523+220012624+23002089244144 222022 211011 2 51 2 (2 (2 (2 (2 21)+1)+0)+

14、0)+1所以8922222 2 110012、十進(jìn)制轉(zhuǎn)換為二進(jìn)制注意：1.最后一步商為0，2.將上式各步所得的余數(shù)從下到上排列，得到： 89=10110012另解除2取余法的另一直觀寫法：522212010余數(shù)11224489222201101練習(xí)將下面的十進(jìn)制數(shù)化為二進(jìn)制數(shù)？（1）10（2）20例1：把89化為五進(jìn)制數(shù)。3、十進(jìn)制轉(zhuǎn)換為其它進(jìn)制解：根據(jù)除k取余法以5作為除數(shù)，相應(yīng)的除法算式為：所以，89=3245895175350423余數(shù)例2、設(shè)計一個程序，實現(xiàn)“除k取余法。(1)、 算法步驟：第一步，給定十進(jìn)制正整數(shù)a和轉(zhuǎn)化后的數(shù)的基數(shù)k；第二步，求出a 除以k 所得的商q ,余數(shù)r；第三步，假設(shè)q 0, 那么a=q, 返回第二步；否那么，執(zhí)行第四步；第四步，將依次得到的余數(shù)從右到左排列，得到k 進(jìn)制數(shù)。2程序框圖：開始輸入a,k 求a除以k的商q 求a除以k的余數(shù)rq=0?是否 a=q 將依次輸出的r從右到左排列結(jié)束輸出r(3)程序：INPUT “a，k=；a,kb=0i=0DO q=ak r=a MOD k b=b+r*10i i=i+1 a=qLOOP UNTIL q=0PRINT bEND練習(xí)：完成以下進(jìn)位制之間的轉(zhuǎn)化：1102314= 10；22357= 10；313710= 6；412315= 7；52134= 3；610101112=