數(shù)學(xué)預(yù)習(xí)導(dǎo)航：算法案例（第課時(shí)）

學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精學(xué)必求其心得，業(yè)必貴于專精預(yù)習(xí)導(dǎo)航1．理解輾轉(zhuǎn)相除法與更相減損術(shù)的步驟,了解其執(zhí)行過程，并會(huì)求最大公約數(shù)．2．掌握秦九韶算法，了解它提高計(jì)算效率的實(shí)質(zhì)，并會(huì)求多項(xiàng)式的值．3．進(jìn)一步體會(huì)算法的基本思想．1．輾轉(zhuǎn)相除法與更相減損術(shù)(1)輾轉(zhuǎn)相除法．①算法步驟：第一步，給定兩個(gè)正整數(shù)m,n。第二步,計(jì)算m除以n所得的余數(shù)r。第三步，m＝n，n＝r.第四步,若r＝0,則m,n的最大公約數(shù)等于m；否則返回第二步．②程序框圖如圖所示．③程序:INPUTm,nDOr＝mMODnm＝nn＝rLOOPUNTILr＝0PRINTmEND(2)更相減損術(shù)．算法分析:第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)．若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步．第二步,以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)．繼續(xù)這個(gè)操作，直到所得的差與減數(shù)相等為止，則這個(gè)數(shù)（等數(shù))或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)．【做一做1】用更相減損術(shù)求294和84的最大公約數(shù)時(shí),第一步是__________．解析：由于294和84都是偶數(shù)，先用2約簡(jiǎn)．答案：用2約簡(jiǎn)2．秦九韶算法（1）概念:求多項(xiàng)式f（x）＝anxn＋an－1xn－1＋…＋a1x＋a0的值時(shí)，常用秦九韶算法，這種算法的運(yùn)算次數(shù)較少，是多項(xiàng)式求值比較先進(jìn)的算法，其實(shí)質(zhì)是轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值，共進(jìn)行n次乘法運(yùn)算和n次加法運(yùn)算．其過程是：改寫多項(xiàng)式為：f（x）＝anxn＋an－1xn－1＋…＋a1x＋a0＝（anxn－1＋an－1xn－2＋…＋a1）x＋a0＝（(anxn－2＋an－1xn－3＋…＋a2）x＋a1）x＋a0＝…＝（…（（anx＋an－1)x＋an－2)x＋…＋a1)x＋a0。設(shè)v1＝anx＋an－1,v2＝v1x＋an－2,v3＝v2x＋an－3，……vn＝vn－1x＋a0.(2)算法步驟：第一步，輸入多項(xiàng)式的次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值．第二步，將v的值初始化為an，將i的值初始化為n－1.第三步，輸入i次項(xiàng)的系數(shù)ai。第四步,v＝vx＋ai,i＝i－1。第五步，判斷i是否大于或等于0.若是，則返回第三步；否則，輸出多項(xiàng)式的值v。（3)程序框圖如圖所示．（4)程序：INPUT“n＝”；nINPUT“an＝”；aINPUT“x＝";xv＝ai＝n－1WHILEi＞＝0PRINT“i＝”；iINPUT“ai＝"；av＝v*x＋ai＝i－1WENDPRINTvEND【做一做2】設(shè)計(jì)