1.3 算法案例,【學(xué)習(xí)目標(biāo)】,1.理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法. 2.理解秦九韶算法中求多項(xiàng)式的值的步驟原理. 3.能利用除 k 取余法把十進(jìn)制數(shù)化為 k 進(jìn)制數(shù).,1.輾轉(zhuǎn)相除法的算法步驟 第一步，給定兩個(gè)正整數(shù) m，n(mn). 第二步，計(jì)算_除以_所得的_數(shù) r. 第三步，mn，nr. 第四步，若 r0，則 m，n 的最大公約數(shù)等于_；否,則，返回第二步.,m,n,余,n,2.更相減損術(shù)的算法步驟 第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù).若 是用 2 約簡(jiǎn)；若不是，執(zhí)行第二步. 第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與 _比較，并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作，直到所得的數(shù) _為止，則這個(gè)數(shù)(等數(shù))或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就 是所求的最大公約數(shù).,較小的數(shù),相等,3.秦九韶算法 把一個(gè)n次多項(xiàng)式f(x)anxnan1xn1a1xa0改寫(xiě),成如下形式：,(anxn1an1xn2a1)xa0,f(x)anxnan1xn1a1xa0 _ (anxn2an1xn3a2)xa1)xa0 _.,(anxan1)xan2)xa1)xa0,求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)的一次多項(xiàng)式的 值，即v1anxan1，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，,即：,n,這樣，求 n 次多項(xiàng)式 f(x)的值就轉(zhuǎn)化為求_個(gè)一次多項(xiàng) 式的值.,v1anxan1， v2_， v3v2xan3， vn_，,v1xan2,vn1xa0,4.進(jìn)位制,(1)k進(jìn)制數(shù)anan1a1a0(k)轉(zhuǎn)化為十進(jìn)制數(shù)為 _. (2)把十進(jìn)制數(shù)化為 k 進(jìn)制數(shù)用“_”，即把所給 的十進(jìn)制數(shù)除以_，得到商數(shù)和余數(shù)，再用商數(shù)除以 k， 得到商數(shù)和余數(shù)，直到商數(shù)為_(kāi) ，把上面各步所得的 _從右到左排列，即得到 k 進(jìn)制數(shù).,除 k 取余法,k,0,余數(shù),anknan1kn1a1ka0,【問(wèn)題探究】,用秦九韶算法求多項(xiàng)式的值有什么優(yōu)點(diǎn)？,答案：減少了做乘法運(yùn)算的次數(shù)，優(yōu)化了求多項(xiàng)式的值的,算法.,題型 1 最大公約數(shù)的求法 【例 1】 用輾轉(zhuǎn)相除法求下面兩數(shù)的最大公約數(shù)，并用更 相減損術(shù)檢驗(yàn)?zāi)愕慕Y(jié)果：,(1)80,36；,(2)294,84.,思維突破：輾轉(zhuǎn)相除法的結(jié)束條件是余數(shù)為 0，更相減損 術(shù)的結(jié)束條件是差與減數(shù)相等.,解：(1)803628， 36844， 8420，,即 80 與 36 的最大公約數(shù)是 4. 驗(yàn)證：803644，,44368,36828,28820， 20812,1284,844， 80 與 36 的最大公約數(shù)是 4.,(2)29484342,84422， 即 294 與 84 的最大公約數(shù)是 42.,驗(yàn)證：294 與 84 都是偶數(shù)可同時(shí)除以2，即取147 與42,的最大公約數(shù)后再乘 2.,14742105,1054263， 634221,422121，,294 與 84 的最大公約數(shù)為 21242.,輾轉(zhuǎn)相除法求最大公約數(shù)的步驟較少，而更相減,損術(shù)運(yùn)算簡(jiǎn)易，因此解題時(shí)要靈活運(yùn)用.,【變式與拓展】,1.試用算法程序表示用輾轉(zhuǎn)相除法求 144 與 60 的最大公約,數(shù)的算法.,解：程序如下：,m144 n60,DO,rm MOD n mn nr,LOOP UNTIL r0,PRINT m END,題型 2 秦九韶算法的應(yīng)用,【例 2】 當(dāng) x3 時(shí)，求多項(xiàng)式 f(x)x5x3x2x1 的,值.,解：根據(jù)秦九韶算法，把多項(xiàng)式改寫(xiě)成如下形式：,f(x)x50 x4x3x2x1 (x0)x1)x1)x1)x1.,按照從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng) x3 時(shí)的,值：v01，,v11303， v233110， v3103131， v4313194， v59431283.,所以當(dāng) x3 時(shí)，多項(xiàng)式的值為 283.,當(dāng)多項(xiàng)式函數(shù)的中間出現(xiàn)空項(xiàng)時(shí)，應(yīng)先補(bǔ)上系 數(shù)為 0 的相應(yīng)項(xiàng).解題時(shí)關(guān)鍵是能正確地改寫(xiě)多項(xiàng)式，然后由內(nèi) 向外逐項(xiàng)計(jì)算.由于后項(xiàng)計(jì)算用到前項(xiàng)的結(jié)果，故要認(rèn)真確保每 一項(xiàng)計(jì)算的準(zhǔn)確性.,【變式與拓展】 2.利用秦九韶算法計(jì)算多項(xiàng)式 f(x)115x3x27x3 在,x 23 的值時(shí)，不會(huì)用到下列哪個(gè)值(,),D,A.161,B.3772,C.86 641,D.85 169,解析：f(x)115x3x27x3(7x3)x5x11. 所以當(dāng)x23時(shí)，v07； v172331613164； v2164235377253767； v33767231186 6411186 652.,題型 3 進(jìn)制數(shù)之間的轉(zhuǎn)化,【例 3】 (1)將 101 111 011(2)轉(zhuǎn)化為十進(jìn)制數(shù)； (2)將 1231(5)轉(zhuǎn)化為七進(jìn)制數(shù).,思維突破：k進(jìn)制數(shù)anan1a2a1a0(k)(0ai<k)轉(zhuǎn)化為十進(jìn)制數(shù)：anan1a2a1a0(k)anknan1kn1a2k2a1ka01.要將k進(jìn)制數(shù)轉(zhuǎn)化為n進(jìn)制數(shù)(n，k10)，可先將 k 進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)，然后再轉(zhuǎn)化為所求的n進(jìn)制數(shù).,解：(1)101 111 011(2)128027126125124123022121120379(10). (2)1231(5)153252351191(10)， 1231(5)362(7).,【變式與拓展】,3.填空：,248,130,(1)11 111 000(2)_(10)； (2)154(6)_(7).,【例4】 已知f(x)x52x43x34x25x6，用秦九韶 算法求這個(gè)多項(xiàng)式當(dāng) x2 時(shí)的值時(shí)，做了幾次乘法運(yùn)算？幾次 加法運(yùn)算？,解：共做了 5 次乘法運(yùn)算，5 次加法運(yùn)算.,易錯(cuò)分析：用秦九韶算法計(jì)算多項(xiàng)式f(x)anxnan1xn1a1xa0.當(dāng)xx0時(shí)，首先將多項(xiàng)式改寫(xiě)成f(x)(anx an1)xan2)xa1)xa0形式，然后再計(jì)算v1anxan1，v2v1xan2，vnvn1xa0.因此，盡管an是1，但仍進(jìn)行了5次乘法.,方法規(guī)律小結(jié),1.輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的區(qū)別與聯(lián)系.,2.秦九韶算法的優(yōu)點(diǎn).,(1)減少乘法運(yùn)算的次數(shù).,(2)規(guī)律性強(qiáng)，便于利用循環(huán)語(yǔ)句實(shí)現(xiàn).,(3)不用對(duì) x 做冪的運(yùn)算，每次都是計(jì)算一個(gè)一次多項(xiàng)式的,值，提高了計(jì)算精度.,3.進(jìn)位制的理解.,進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示 不同的數(shù)值.使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)，基數(shù)為 n，即稱為 n 進(jìn)位制，簡(jiǎn)稱 n 進(jìn)制.現(xiàn)在最常用的是十進(jìn)制，通常使用 10 個(gè) 阿拉伯?dāng)?shù)字 09 進(jìn)行記數(shù).,對(duì)于任何一個(gè)數(shù)，我們可以用不同的進(jìn)位制來(lái)表示.比如： 十進(jìn)數(shù) 57，可以用二進(jìn)制表示為 111 001，也可以用八進(jìn)制表 示為 71，用十六進(jìn)制表示為 39，它們所代表的數(shù)值都是一樣的. 表示各種進(jìn)制數(shù)時(shí)，一般要在數(shù)字右下角加注來(lái)表示.如 111 001(2)表示二進(jìn)制數(shù)，34(5)表示五進(jìn)制數(shù).電子計(jì)算機(jī)一般都 使用二進(jìn)制.,