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

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

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

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

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

5、是為了計(jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)，約定“滿幾進(jìn)一”就是幾進(jìn)制，幾進(jìn)制的基數(shù)(大于1的整數(shù))就是幾.2.常見的進(jìn)位制(1)二進(jìn)制：只使用0和1兩個(gè)數(shù)學(xué)；滿二進(jìn)一，即1110(2).(2)八進(jìn)制；使用0,1,2,3,4,5,6,7這八個(gè)不同數(shù)學(xué)；滿八進(jìn)一，即7110(8).思考任何進(jìn)位制中都要用到的數(shù)字是什么？答0和1.返回答案 題型探究 重點(diǎn)突破題型一求兩個(gè)正整數(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)相除法求給定的兩個(gè)數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對(duì)中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì)，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù).(2)利用更相減損術(shù)求兩個(gè)正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個(gè)正整數(shù)是否都是偶數(shù).若是，用2約簡.也可以不除以2，直接求最大公約數(shù)，這樣不影響最后結(jié)果.跟蹤訓(xùn)練1用輾轉(zhuǎn)相除法求80與36的最大公約數(shù)，并用更

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

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

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

10、就是除基數(shù)，倒取余.跟蹤訓(xùn)練3將53(8)轉(zhuǎn)化為二進(jìn)制數(shù).解先將八進(jìn)制數(shù)53(8)轉(zhuǎn)化為十進(jìn)制數(shù)：53(8)58138043；再將十進(jìn)制數(shù)43轉(zhuǎn)化為二進(jì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)化為十進(jìn)制數(shù)，再進(jìn)行比較.解析85(9)89577,210(6)26216078,1000(4)14364,111111(2)12512412312212163.故最小的是63.D解析答案解后反思分析解后反思合理的轉(zhuǎn)化是解題的關(guān)鍵.對(duì)于進(jìn)位制之間的轉(zhuǎn)化問題，一

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

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