




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、1.3 算法案例,第二課時(shí),例2 求325,130,270三個(gè)數(shù)的最大公約數(shù).,因?yàn)?25=1302+65,130=652,所以325與130的最大公約數(shù)是65.,因?yàn)?70=654+10,65=106+5,10=52,所以65與270最大公約數(shù)是5.,故325,130,270三個(gè)數(shù)的最大公約數(shù)是5.,問題提出,1.輾轉(zhuǎn)相除法和更相減損術(shù),是求兩個(gè)正整數(shù)的最大公約數(shù)的優(yōu)秀算法,我們將算法轉(zhuǎn)化為程序后,就可以由計(jì)算機(jī)來執(zhí)行運(yùn)算,實(shí)現(xiàn)了古代數(shù)學(xué)與現(xiàn)代信息技術(shù)的完美結(jié)合.,2.對(duì)于求n次多項(xiàng)式的值,在我國古代數(shù)學(xué)中有一個(gè)優(yōu)秀算法,即秦九韶算法,我們將對(duì)這個(gè)算法作些了解和探究.,秦九韶算法,問題1設(shè)計(jì)
2、求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值的算法,并寫出程序.,x=5 f=2x5-5x4-4x3+3x2-6x+7 PRINT f END,程序,點(diǎn)評(píng):上述算法一共做了15次乘法運(yùn)算,5次加法運(yùn)算.優(yōu)點(diǎn)是簡單,易懂;缺點(diǎn)是不通用,不能解決任意多項(xiàng)多求值問題,而且計(jì)算效率不高.,知識(shí)探究(一):秦九韶算法的基本思想,思考2:在上述問題中,若先計(jì)算x2的值,然后依次計(jì)算x2x,(x2x)x,(x2x)x)x的值,這樣每次都可以利用上一次計(jì)算的結(jié)果,那么一共做了多少次乘法運(yùn)算和多少次加法運(yùn)算?,9次乘法運(yùn)算,5次加法運(yùn)算.,第二種做法與第一種做法相比,乘法的運(yùn)算次數(shù)減
3、少了,因而能提高運(yùn)算效率.而且對(duì)于計(jì)算機(jī)來說,做一次乘法所需的運(yùn)算時(shí)間比做一次加法要長得多,因此第二種做法能更快地得到結(jié)果.,思考3:能否探索更好的算法,來解決任意多項(xiàng)式的求值問題?,f(x)=2x5-5x4-4x3+3x2-6x+7 =(2x4-5x3-4x2+3x-6)x+7 =(2x3-5x2-4x+3)x-6)x+7 =(2x2-5x-4)x+3)x-6)x+7 =(2x-5)x-4)x+3)x-6)x+7,v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=534
4、5+7=2677,所以,當(dāng)x=5時(shí),多項(xiàng)式的值是2677.,這種求多項(xiàng)式值的方法就叫秦九韶算法.,5次乘法運(yùn)算,5次加法運(yùn)算.,思考4:利用最后一種算法求多項(xiàng)式f(x)=anxn+an-1xn-1+a1x+a0的值,這個(gè)多項(xiàng)式應(yīng)寫成哪種形式?,f(x)=anxn+an-1xn-1+a1x+a0 =(anxn-1+an-1xn-2+a2x+a1)x+a0 =(anxn-2+an-1xn-3+a2)x+a1)x+a0 = =(anx+an-1)x+an-2)x+a1)x+a0.,思考4:對(duì)于f(x)=(anx+an-1)x+ an-2)x+a1)x+a0,由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,其算法步驟
5、如何?,第一步,計(jì)算v1=anx+an-1.,第二步,計(jì)算v2=v1x+an-2.,第三步,計(jì)算v3=v2x+an-3. ,第n步,計(jì)算vn=vn-1x+a0.,思考5:上述求多項(xiàng)式 f(x)=anxn+an-1xn-1+a1x+a0的值的方法稱為秦九韶算法,利用該算法求f(x0)的值,一共需要多少次乘法運(yùn)算,多少次加法運(yùn)算?,思考6:在秦九韶算法中,記v0=an,那么第k步的算式是什么?,vk=vk-1x+an-k (k=1,2,n),n次乘法運(yùn)算, n次加法運(yùn)算,知識(shí)探究(二):秦九韶算法的程序設(shè)計(jì),思考1:用秦九韶算法求多項(xiàng)式的值,可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法?其算法步驟如何設(shè)計(jì)?,第一
6、步,輸入多項(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.,第五步,判斷i0是否成立.若是,則返回第 二步;否則,輸出多項(xiàng)式的值v.,思考2:該算法的程序框圖如何表示?,思考3:該程序框圖對(duì)應(yīng)的程序如何表述?,INPUT “n=”;n,INPUT “an=”;a,INPUT “x=”;x,v=an,i=n-1,WHILE i=0,INPUT “ai=”;b,v=v*x+b,i=i-1,WEND,PRINT y,END,理論遷移,例1 已知一個(gè)5次多項(xiàng)式為 用秦九韶算法求f(5)的值.,f(x)=
7、(5x+2)x+3.5)x-2.6)x+1.7)x-0.8.,v1=55+2=27;,v2=275+3.5=138.5;,v3=138.55-2.6=689.9;,v4=689.95+1.7=3451.2;,v5=3451.25-0.8=17255.2.,所以f(5)= =17255.2.,變式:例2 已知一個(gè)5次多項(xiàng)式為 用秦九韶算法求當(dāng)x=5時(shí),V1,V3的值及求f(5)的值做多少次乘法運(yùn)算.,解:f(x)=(5x+0)x+3.5)x+0)x+1.7)x-0.8.,v1=55+0=25;,v2=255+3.5=128.5;,v3=128.55+0=642.5;,v4=642.55+1.7=3214.2;,v5=3214.25-0.8=16070.8.,所以v1=25, v3=642.5 ,f(5)=16070.8.,例3 閱讀下列程序,說明它解決的實(shí)際問題是什么?,INPUT “x=”;a n=0 y=0 WHLE n5 y=y+(n+1)*an n=n+1 WEND PRINT y END,求多項(xiàng)式 在x=a時(shí)的值.,小結(jié)作業(yè),評(píng)價(jià)一
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年放射科護(hù)士長述職報(bào)告范文
- 一年級(jí)年級(jí)組長新學(xué)期工作計(jì)劃
- 地鐵站周邊景觀成品保護(hù)措施
- 外研社版英語三起五年級(jí)上冊(cè)教學(xué)提升計(jì)劃
- 幼兒園小班心理健康計(jì)劃他
- 監(jiān)事會(huì)職責(zé)培訓(xùn)與能力提升
- 電子制造勞動(dòng)力和材料投入計(jì)劃及其保證措施
- 三年級(jí)語文教材使用提升計(jì)劃
- 印刷廠安全生產(chǎn)教育培訓(xùn)計(jì)劃
- 幕墻施工協(xié)調(diào)與溝通管理措施
- 英國和美國社區(qū)居家安寧療護(hù)服務(wù)模式及其對(duì)我國的啟示
- 2024年中小學(xué)教師職稱審定答辯題目
- 橙黃橘綠半甜時(shí) 季羨林 史鐵生 汪曾祺等文學(xué)大家
- 極化曲線研究論文
- 鋼絲繩吊裝時(shí)最大允許吊裝重物對(duì)應(yīng)表
- 2023年呂梁市文水縣社區(qū)工作者招聘考試真題
- 國開2023秋《習(xí)近平總書記教育重要論述研究》形考任務(wù)一參考答案
- 2023年廣西公需科目關(guān)于人才工作的重要論述答案
- 設(shè)計(jì)報(bào)價(jià)單模板
- DB41T2513-2023核桃蛀果害蟲防控技術(shù)規(guī)程
- 比例方程練習(xí)題
評(píng)論
0/150
提交評(píng)論