第一章復(fù)習(xí)課

1、主備人：唐強(qiáng)主備人：唐強(qiáng) 王廷偉王廷偉 向妍艷向妍艷 審審核人：牟必繼核人：牟必繼 溫故而知新溫故而知新 第一章第一章 算法初步復(fù)習(xí)課算法初步復(fù)習(xí)課知識(shí)結(jié)構(gòu)知識(shí)結(jié)構(gòu)算法算法程序框圖程序框圖算法語(yǔ)句算法語(yǔ)句輾轉(zhuǎn)相除法與輾轉(zhuǎn)相除法與更相減損術(shù)更相減損術(shù) 秦九韶算法秦九韶算法 進(jìn)位制進(jìn)位制知識(shí)梳理知識(shí)梳理1.1.算法的概念算法的概念 在數(shù)學(xué)中，按照一定規(guī)則解決某一在數(shù)學(xué)中，按照一定規(guī)則解決某一類(lèi)問(wèn)題的明確和有限的步驟稱(chēng)為算法類(lèi)問(wèn)題的明確和有限的步驟稱(chēng)為算法. . 用程序框、流程線(xiàn)及文字說(shuō)明來(lái)表用程序框、流程線(xiàn)及文字說(shuō)明來(lái)表示算法的圖形稱(chēng)為示算法的圖形稱(chēng)為程序框圖程序框圖. .2.2.程序框圖的概念程

2、序框圖的概念3.3.程序框、流程線(xiàn)的名稱(chēng)與功能程序框、流程線(xiàn)的名稱(chēng)與功能圖形符號(hào)圖形符號(hào) 名名 稱(chēng)稱(chēng) 功功 能能 終端框終端框 （起止框）（起止框） 輸入、輸出輸入、輸出框框 處理框處理框 （執(zhí)行框）（執(zhí)行框） 判斷框判斷框 流程線(xiàn)流程線(xiàn) 表示一個(gè)算法的起始和結(jié)束表示一個(gè)算法的起始和結(jié)束 表示一個(gè)算法輸入和輸出的表示一個(gè)算法輸入和輸出的信息信息 賦值、計(jì)算賦值、計(jì)算 判斷某一條件是否成立，成立時(shí)在判斷某一條件是否成立，成立時(shí)在出口處標(biāo)明出口處標(biāo)明“是是”或或“Y”Y”；不成立；不成立時(shí)標(biāo)明時(shí)標(biāo)明“否否”或或“N” N” 連接程序框，表示算法步驟的連接程序框，表示算法步驟的執(zhí)行順序執(zhí)行順序 4.

3、4.算法的順序結(jié)構(gòu)算法的順序結(jié)構(gòu)（1 1）概念：）概念： 由若干個(gè)依次執(zhí)行的步驟組成的邏由若干個(gè)依次執(zhí)行的步驟組成的邏輯結(jié)構(gòu)，稱(chēng)為輯結(jié)構(gòu)，稱(chēng)為順序結(jié)構(gòu)順序結(jié)構(gòu). .（2 2）程序框圖：）程序框圖：步驟步驟n步驟步驟n+15.5.算法的條件結(jié)構(gòu)算法的條件結(jié)構(gòu)（1 1）概念：）概念： 由若干個(gè)在一定條件下才會(huì)被執(zhí)行由若干個(gè)在一定條件下才會(huì)被執(zhí)行的步驟組成的邏輯結(jié)構(gòu)，稱(chēng)為的步驟組成的邏輯結(jié)構(gòu)，稱(chēng)為條件結(jié)構(gòu)條件結(jié)構(gòu). .（2 2）程序框圖：）程序框圖：滿(mǎn)足條件？滿(mǎn)足條件？步驟步驟A步驟步驟B是是否否滿(mǎn)足條件？滿(mǎn)足條件？步驟步驟A是是否否6.6.算法的循環(huán)結(jié)構(gòu)算法的循環(huán)結(jié)構(gòu)（1 1）概念：）概念： 由按

4、照一定的條件反復(fù)執(zhí)行的某些由按照一定的條件反復(fù)執(zhí)行的某些步驟組成的邏輯結(jié)構(gòu)，稱(chēng)為步驟組成的邏輯結(jié)構(gòu)，稱(chēng)為循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu). .（2 2）程序框圖：）程序框圖：循環(huán)體循環(huán)體滿(mǎn)足條件？滿(mǎn)足條件？是是否否循環(huán)體循環(huán)體滿(mǎn)足條件？滿(mǎn)足條件？是是否否7.7.算法的輸入語(yǔ)句算法的輸入語(yǔ)句INPUT “INPUT “提示內(nèi)容提示內(nèi)容”；變量；變量8.8.算法的輸出語(yǔ)句算法的輸出語(yǔ)句PRINT “PRINT “提示內(nèi)容提示內(nèi)容”；表達(dá)式；表達(dá)式9.9.算法的賦值語(yǔ)句算法的賦值語(yǔ)句變量變量= =表達(dá)式表達(dá)式10.10.算法的條件語(yǔ)句算法的條件語(yǔ)句IF IF 條件條件 THENTHEN 語(yǔ)句體語(yǔ)句體END IFEN

5、D IFIF IF 條件條件 THENTHEN 語(yǔ)句體語(yǔ)句體1 1ELSEELSE 語(yǔ)句體語(yǔ)句體2 2END IFEND IF滿(mǎn)足條件？滿(mǎn)足條件？步驟步驟1步驟步驟1是是否否滿(mǎn)足條件？滿(mǎn)足條件？步驟步驟A是是否否11.11.算法的循環(huán)語(yǔ)句算法的循環(huán)語(yǔ)句DODO 循環(huán)體循環(huán)體LOOP UNTILLOOP UNTIL 條件條件滿(mǎn)足條件？滿(mǎn)足條件？是是循環(huán)體循環(huán)體否否WHILE WHILE 條件條件 循環(huán)體循環(huán)體WEND WEND 循環(huán)體循環(huán)體滿(mǎn)足條件？滿(mǎn)足條件？是是否否12.12.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn(mn).n).第二步，計(jì)算第二步，計(jì)

6、算m m除以除以n n所得的余數(shù)所得的余數(shù)r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，則，則m m，n n的最大公約數(shù)等的最大公約數(shù)等 于于m m；否則，返回第二步；否則，返回第二步. . 求兩個(gè)正整數(shù)的最大公約數(shù)求兩個(gè)正整數(shù)的最大公約數(shù)13.13.更相減損術(shù)更相減損術(shù)第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn(mn).n). 第二步，計(jì)算第二步，計(jì)算m-nm-n所得的差所得的差k. k. 第三步，比較第三步，比較n n與與k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若

7、第四步，若m=nm=n，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于 m m；否則，返回第二步；否則，返回第二步. . 求兩個(gè)正整數(shù)的最大公約數(shù)求兩個(gè)正整數(shù)的最大公約數(shù)14.14.秦九韶算法秦九韶算法第一步，輸入多項(xiàng)式的次數(shù)第一步，輸入多項(xiàng)式的次數(shù)n n，最高次，最高次 項(xiàng)的系數(shù)項(xiàng)的系數(shù)a an n和和x x的值的值. . 第二步，令第二步，令v=av=an n，i=n-1.i=n-1. 第三步，輸入第三步，輸入i i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)a ai i. . 第四步，第四步，v=vx+av=vx+ai i，i=i-1.i=i-1.第五步，判斷第五步，判斷i0i0是否成立是否成立. .若是

8、，則返回第若是，則返回第 二步；否則，輸出多項(xiàng)式的值二步；否則，輸出多項(xiàng)式的值v. v. 求多項(xiàng)式求多項(xiàng)式f(xf(x)=a)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值的值15. 15. 十進(jìn)制化十進(jìn)制化k k進(jìn)制的算法進(jìn)制的算法第四步，若第四步，若q0q0，則，則a=qa=q，返回第二步；，返回第二步； 否則，輸出全部余數(shù)否則，輸出全部余數(shù)r r排列得到排列得到 的的k k進(jìn)制數(shù)進(jìn)制數(shù). .第一步，輸入十進(jìn)制數(shù)第一步，輸入十進(jìn)制數(shù)a a和基數(shù)和基數(shù)k k的值的值. .第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余數(shù)

9、，余數(shù)r.r.第三步，把所得的余數(shù)依次從右到左排第三步，把所得的余數(shù)依次從右到左排 列列. .除除k k取余法取余法 例例1 1、某工廠、某工廠20052005年的年生產(chǎn)總值為年的年生產(chǎn)總值為200200萬(wàn)元，技術(shù)革新后預(yù)計(jì)以后每年的年生產(chǎn)總?cè)f元，技術(shù)革新后預(yù)計(jì)以后每年的年生產(chǎn)總值都比上一年增長(zhǎng)值都比上一年增長(zhǎng)5%.5%.設(shè)計(jì)一個(gè)程序，輸出預(yù)設(shè)計(jì)一個(gè)程序，輸出預(yù)計(jì)年生產(chǎn)總值超過(guò)計(jì)年生產(chǎn)總值超過(guò)300300萬(wàn)元的最早年份萬(wàn)元的最早年份. .第三步，判斷所得的結(jié)果是否大于第三步，判斷所得的結(jié)果是否大于300.300. 若是，則輸出該年的年份；否則，若是，則輸出該年的年份；否則， 返回第二步返回第二

10、步. .第一步，輸入第一步，輸入20052005年的年生產(chǎn)總值年的年生產(chǎn)總值. .第二步，計(jì)算下一年的年生產(chǎn)總值第二步，計(jì)算下一年的年生產(chǎn)總值. .算法分析算法分析：鞏固練習(xí)鞏固練習(xí)（3 3）控制條件控制條件：當(dāng)：當(dāng)“a a300”300”時(shí)終止循時(shí)終止循環(huán)環(huán). .（1 1）循環(huán)體循環(huán)體：設(shè)：設(shè)a a為某年的年生產(chǎn)總值，為某年的年生產(chǎn)總值，t t為年生產(chǎn)總值的年增長(zhǎng)量，為年生產(chǎn)總值的年增長(zhǎng)量，n n為年份，為年份，則則t=0.05at=0.05a，a=a+ta=a+t，n=n+1.n=n+1.（2 2）初始值初始值：n=2005n=2005，a=200.a=200.循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)：開(kāi)始開(kāi)始n

11、=2005a=200t=0.05aa=a+tn=n+1a300？結(jié)束結(jié)束輸出輸出n是是否否程序框圖程序框圖：開(kāi)始開(kāi)始n=2005a=200t=0.05aa=a+tn=n+1a300？結(jié)束結(jié)束輸出輸出n是是否否程序程序：n=2005n=2005a=200a=200DODOt=0.05t=0.05* *a aa=a+ta=a+tn=n+1n=n+1LOOP UNTIL aLOOP UNTIL a300300PRINT nPRINT nENDEND 例例2 2、一個(gè)球從、一個(gè)球從100m100m高處自由落下高處自由落下, ,每次每次著地后又跳回到原高度的一半再落下著地后又跳回到原高度的一半再落下.

12、.編寫(xiě)編寫(xiě)程序程序, ,求當(dāng)它第求當(dāng)它第1010次著地時(shí)次著地時(shí), , (1)(1)第第1010次著地后反彈多高次著地后反彈多高? ? (2)(2)向下的運(yùn)動(dòng)共經(jīng)過(guò)多少米向下的運(yùn)動(dòng)共經(jīng)過(guò)多少米? ? (3)(3)全程共經(jīng)過(guò)多少米全程共經(jīng)過(guò)多少米? ? 100100505025251 12 23 34 41010著地次數(shù)著地次數(shù)高度高度0 0(1)(1)第第1010次著地后反彈多高次著地后反彈多高? ?開(kāi)始開(kāi)始h=50h=50i10?i10?h=h/2h=h/2i=1i=1結(jié)束結(jié)束輸出輸出h h否否i=i+1i=i+1h=50h=50i=1i=1WHILE iWHILE i=10=10h=h/2

13、h=h/2i=i+1i=i+1WENDWENDPRINT hPRINT hENDEND是是(2)(2)第第1010次著地時(shí)向下的運(yùn)動(dòng)共經(jīng)次著地時(shí)向下的運(yùn)動(dòng)共經(jīng)過(guò)多少米過(guò)多少米? ?開(kāi)始開(kāi)始h=100h=100s=100s=100h=h/2h=h/2s=s+hs=s+hi=1i=1結(jié)束結(jié)束輸出輸出s s否否i=i+1i=i+1是是h100h100s=100s=100i=1i=1WHILE iWHILE i=10=10h=h/2h=h/2s=s+hs=s+hi=i+1i=i+1WENDWENDPRINT sPRINT sENDENDi10?i10?(3)(3)全程共經(jīng)過(guò)多少米全程共經(jīng)過(guò)多少米? ?

14、s=s+hs=s+h開(kāi)始開(kāi)始h=100h=100s=100s=100i10?i10?h=h/2h=h/2i=1i=1結(jié)束結(jié)束輸出輸出s s否否i=i+1i=i+1是是s=s+2hs=s+2hs=s+hs=s+hh=100h=100s=100s=100i=1i=1WHILE iWHILE i=10=10h=h/2h=h/2i=i+1i=i+1WENDWENDPRINT sPRINT sENDENDs=s+2s=s+2* *h h 例例3 3、閱讀下列程序：若輸入的兩個(gè)、閱讀下列程序：若輸入的兩個(gè)數(shù)數(shù)m=428m=428，n=284n=284，求計(jì)算機(jī)輸出的數(shù)，求計(jì)算機(jī)輸出的數(shù). .INPUT m

15、INPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND 例例4 4、求、求324324，243243，270270三個(gè)數(shù)的最大三個(gè)數(shù)的最大公約數(shù)公約數(shù). . 2727 例例5 5、已知、已知f(xf(x)=8x)=8x7 7+5x+5x6 6+3x+3x4 4+2x+1,+2x+1,用用秦九韶算法去秦九韶算法去f(2)f(2)的值的值. .f(xf(x)=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1)=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1f(2)=1397f(2)=1397 例例6 6、用秦九韶算法求多項(xiàng)式、用秦九韶算法求多項(xiàng)式f(xf(x)=a)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值，令的值，令v0=an， v vk k=v=vk-1k-1x+ax+an-kn-k(k=1(k=1，2 2，n).n).若若