創(chuàng)新設(shè)計2016_2017學(xué)年高中數(shù)學(xué)第1章算法初步1.3算法案例課件

1、第一章算法初步學(xué)習(xí)目標1.理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義，了解其執(zhí)行過程.2.理解秦九韶算法的計算過程，并了解它提高計算效率的實質(zhì).3.理解進位制的概念，能進行不同進位制間的轉(zhuǎn)化.4.了解進位制的程序框圖和程序.知識梳理 自主學(xué)習(xí)題型探究 重點突破當堂檢測 自查自糾欄目索引 知識梳理 自主學(xué)習(xí)知識點一輾轉(zhuǎn)相除法與更相減損術(shù)1.輾轉(zhuǎn)相除法(1)輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個正整數(shù)的 的古老而有效的算法.(2)輾轉(zhuǎn)相除法的算法步驟第一步，給定 .第二步，計算 .第三步， .第四步，若r0，則m，n的最大公約數(shù)等于 ；否則，返回 .最大公約數(shù)兩個正整數(shù)m，nm除以n所得的余數(shù)rmn，n

2、rm第二步答案2.更相減損術(shù)第一步，任意給定兩個正整數(shù)，判斷它們是否都是 .若是，用 約簡；若不是，執(zhí)行 .第二步，以 的數(shù)減去 的數(shù)，接著把所得的差與 的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個操作，直到所得的數(shù) 為止，則這個數(shù)(等數(shù))或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).偶數(shù)2第二步較大較小較小相等答案3.輾轉(zhuǎn)相除法和更相減損術(shù)的區(qū)別與聯(lián)系：名稱輾轉(zhuǎn)相除法更相減損術(shù)區(qū)別(1)以除法為主；(2)兩個整數(shù)的差值較大時，運算次數(shù)較少；(3)相除，余數(shù)為0時得結(jié)果(1)以減法為主；(2)兩個整數(shù)的差值較大時，運算次數(shù)較多；(3)相減，減數(shù)與差相等時得結(jié)果；(4)相減前要進行是否都是偶數(shù)的判斷聯(lián)系(

3、1)都是求兩個正整數(shù)最大公約數(shù)的方法；(2)二者的實質(zhì)都是遞歸的過程；(3)二者都要用循環(huán)結(jié)構(gòu)來實現(xiàn)思考實際應(yīng)用更相減損術(shù)時要做的第一步工作是什么？答先判斷a，b是否為偶數(shù)，若是，都除以2再進行.答案知識點二秦九韶算法1.秦九韶算法簡介(1)秦九韶算法要解決的問題是求多項式的值.(2)秦九韶算法的特點：通過一次式的反復(fù)計算，逐步得到高次多項式的值，即將一個n次多項式的求值問題歸結(jié)為重復(fù)計算n個一次多項式的值的問題.(3)秦九韶算法的原理：將f(x)anxnan1xn1a1xa0改寫為：f(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0先計算最內(nèi)層括號內(nèi)一次

4、多項式的值，即v1anxan1，再由內(nèi)向外逐層計算一次多項式vk的值.2.秦九韶算法的操作方法(1)算法步驟如下：第一步，輸入多項式次數(shù)n、最高次項的系數(shù)an和x的值.第二步，將v的值初始化為an，將i的值初始化為n1.第三步，輸入i次項的系數(shù)ai.第四步，vvxai，ii1.第五步，判斷i是否大于或等于0.若是，則返回第三步；否則，輸出多項式的值v.(2)程序框圖如圖所示.(3)程序如下：INPUT“n”；nINPUT“an”；aINPUT“x”；xvain1WHILEi0PRINT“i”；iINPUT“ai”；avv*xaii1WENDPRINTvEND知識點三進位制1.進位制的概念進位制

5、是為了計數(shù)和運算方便而約定的記數(shù)系統(tǒng)，約定“滿幾進一”就是幾進制，幾進制的基數(shù)(大于1的整數(shù))就是幾.2.常見的進位制(1)二進制：只使用0和1兩個數(shù)學(xué)；滿二進一，即1110(2).(2)八進制；使用0,1,2,3,4,5,6,7這八個不同數(shù)學(xué)；滿八進一，即7110(8).思考任何進位制中都要用到的數(shù)字是什么？答0和1.返回答案 題型探究 重點突破題型一求兩個正整數(shù)的最大公約數(shù)例1分別用輾轉(zhuǎn)相除法和更相減損術(shù)求261和319的最大公約數(shù).解方法一(輾轉(zhuǎn)相除法)3192611(余58)，261584(余29)，58292(余0)，所以319與261的最大公約數(shù)為29.方法二(更相減損術(shù))3192

6、6158，26158203，20358145，1455887，875829，582929，29290，所以319與261的最大公約數(shù)是29.解析答案反思與感悟反思與感悟(1)利用輾轉(zhuǎn)相除法求給定的兩個數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時的較小數(shù)就是原來兩個數(shù)的最大公約數(shù).(2)利用更相減損術(shù)求兩個正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個正整數(shù)是否都是偶數(shù).若是，用2約簡.也可以不除以2，直接求最大公約數(shù)，這樣不影響最后結(jié)果.跟蹤訓(xùn)練1用輾轉(zhuǎn)相除法求80與36的最大公約數(shù)，并用更

7、相減損術(shù)檢驗?zāi)愕慕Y(jié)果.解803628，36844,8420，即80與36的最大公約數(shù)是4.驗證：80240,36218；40220,1829；20911,1192；927,725；523,321；211,1224；所以80與36的最大公約數(shù)為4.解析答案題型二秦九韶算法的應(yīng)用例2用秦九韶算法求多項式f(x)x55x410 x310 x25x1當x2時的值.解f(x)x55x410 x310 x25x1(x5)x10)x10)x5)x1.當x2時，有v01；v1v0 xa41(2)53；v2v1xa33(2)104；v3v2xa24(2)102；v4v3xa12(2)51；v5v4xa01(2)

8、11.故f(2)1.解析答案反思與感悟反思與感悟(1)先將多項式寫成一次多項式的形式，然后運算時從里到外，一步一步地做乘法和加法即可.這樣比直接將x2代入原式大大減少了計算量.若用計算機計算，則可提高運算效率.(2)注意：當多項式中n次項不存在時，可將第n次項看作0 xn.跟蹤訓(xùn)練2用秦九韶算法計算多項式f(x)x612x560 x4160 x3240 x2192x64當x2時的值.解根據(jù)秦九韶算法，把多項式改寫成如下形式：f(x)(x12)x60)x160)x240)x192)x64.由內(nèi)向外依次計算一次多項式當x2時的值；v01；v1121210；v21026040；v340216080；

9、v480224080；v580219232；v6322640.所以當x2時，多項式的值為0.解析答案題型三進位制之間的互化例3(1)把二進制數(shù)1110011(2)化為十進制數(shù).解1110011(2)1261251240230221211115.(2)將8進制數(shù)314706(8)化為十進制數(shù).解314706(8)385184483782081680104902.所以，化為十進制數(shù)是104902.解析答案反思與感悟反思與感悟(1)將k進制轉(zhuǎn)化為十進制的方法是：先將這個k進制數(shù)寫成各個數(shù)位上的數(shù)字與k的冪的乘積之和的形式，再按照十進制的運算規(guī)則計算出結(jié)果.(2)十進制轉(zhuǎn)化為k進制，采用除k取余法，也

10、就是除基數(shù)，倒取余.跟蹤訓(xùn)練3將53(8)轉(zhuǎn)化為二進制數(shù).解先將八進制數(shù)53(8)轉(zhuǎn)化為十進制數(shù)：53(8)58138043；再將十進制數(shù)43轉(zhuǎn)化為二進制數(shù)：所以53(8)101011(2).解析答案 轉(zhuǎn)化與化歸思想思想方法例4下列各數(shù)中，最小的數(shù)是()A.85(9) B.210(6)C.1000(4)D.111111(2)分析先將它們轉(zhuǎn)化為十進制數(shù)，再進行比較.解析85(9)89577,210(6)26216078,1000(4)14364,111111(2)12512412312212163.故最小的是63.D解析答案解后反思分析解后反思合理的轉(zhuǎn)化是解題的關(guān)鍵.對于進位制之間的轉(zhuǎn)化問題，一

11、般要先把k進制數(shù)轉(zhuǎn)化為十進制數(shù)，再轉(zhuǎn)化為其他進制數(shù). 數(shù)制轉(zhuǎn)化方法掌握不牢致錯易錯點例5把十字進制數(shù)49化為二進制數(shù).分析對進位制間的換算，要弄清解題的辦法，將十進制數(shù)轉(zhuǎn)化為k進制數(shù)用“除k取余法”.解所以49110 001(2).解后反思本例常出現(xiàn)的錯誤是把上式中各步所得的余數(shù)從上到下排列，這是基本方法掌握不牢造成的，應(yīng)加以注意.分析解析答案解后反思返回 當堂檢測1.1 337與382的最大公約數(shù)是()A.3 B.382 C.191 D.201解析利用輾轉(zhuǎn)相除法，1 3373823191,3821912，故兩數(shù)的最大公約數(shù)為191.C解析答案2.把189化為三進制數(shù)，則末位數(shù)字是()A.0

12、B.1 C.2 D.3解析采用“除k取余法”，得即18921 000(3)A解析答案3.用秦九韶算法求n次多項式f(x)anxnan1xn1a1xa0當xx0時的值，求f(x0)需要乘方、乘法、加法的次數(shù)分別為()A. ，n，n B.n,2n，nC.0,2n，n D.0，n，n解析因為f(x)(anxan1)xan2)xa1)xa0，所以乘方、乘法、加法的次數(shù)分別為0，n，n.D解析答案4.用秦九韶算法求多項式f(x)7x66x53x22，當x4時的值時，先算的是()A.4416 B.7428C.44464 D.74634解析因為f(x)anxnan1xn1a1xa0(anxan1)xan2)xa1)xa0，所以用秦九韶算法求多項式f(x)7x66x53x22當x4時的值時，先算的是74634.D解析答案5.用更相減損術(shù)求36與134的最大公約數(shù)，第一步應(yīng)為_.解析36與134都是偶數(shù)，第一步應(yīng)為：先除以2，得到18與67.先除以2，得到18與67解析答案課堂小結(jié)返回1.求兩個正整數(shù)的最大公約數(shù)的問題，可以用輾轉(zhuǎn)相除法，也可以用更相減損術(shù).用輾轉(zhuǎn)相除法，即根據(jù)anbr這個式子，反復(fù)相除，直到r0為止；用更相減損術(shù)，即根據(jù)r|ab|這個式子，反