算法初步單元小結(jié)ppt課件

1、算法初步單元小結(jié)算法初步單元小結(jié)第一課時第一課時第一章第一章 單元復(fù)習(xí)單元復(fù)習(xí)知識構(gòu)造知識構(gòu)造t57301p2算法算法程序框圖程序框圖算法語句算法語句輾轉(zhuǎn)相除法與輾轉(zhuǎn)相除法與更相減損術(shù)更相減損術(shù) 秦九韶算法秦九韶算法 進(jìn)位制進(jìn)位制知識梳理知識梳理1.1.算法的概念算法的概念 在數(shù)學(xué)中，按照一定規(guī)那么處理某一類問題的明確和有限的步驟稱為算法. 用程序框、流程線及文字闡明來表示算法的圖形稱為程序框圖.2.2.程序框圖的概念程序框圖的概念3.3.程序框、流程線的稱號與功能程序框、流程線的稱號與功能圖形符號圖形符號 名名 稱稱 功功 能能 終端框終端框 起止框起止框 輸入、輸出輸入、輸出框框 處置框處

2、置框 執(zhí)執(zhí)行框行框 判別框判別框 流程線流程線 表示一個算法的起始和終了表示一個算法的起始和終了 表示一個算法輸入和輸出的表示一個算法輸入和輸出的信息信息 賦值、計算賦值、計算 判別某一條件能否成立，成立時在判別某一條件能否成立，成立時在出口處標(biāo)明出口處標(biāo)明“是或是或“Y；不成立；不成立時標(biāo)明時標(biāo)明“否或否或“N 銜接程序框，表示算法步驟的銜接程序框，表示算法步驟的執(zhí)行順序執(zhí)行順序 4.4.算法的順序構(gòu)造算法的順序構(gòu)造1 1概念：概念： 由假設(shè)干個依次執(zhí)行的步驟組成的由假設(shè)干個依次執(zhí)行的步驟組成的邏輯構(gòu)造，稱為順序構(gòu)造邏輯構(gòu)造，稱為順序構(gòu)造. .2 2程序框圖：程序框圖：步驟步驟n步驟步驟n+

3、15.5.算法的條件構(gòu)造算法的條件構(gòu)造1 1概念：概念： 由假設(shè)干個在一定條件下才會被執(zhí)由假設(shè)干個在一定條件下才會被執(zhí)行的步驟組成的邏輯構(gòu)造，稱為條件構(gòu)行的步驟組成的邏輯構(gòu)造，稱為條件構(gòu)造造. .2 2程序框圖：程序框圖：滿足條件？滿足條件？步驟步驟A步驟步驟B是是否否滿足條件？滿足條件？步驟步驟A是是否否6.6.算法的循環(huán)構(gòu)造算法的循環(huán)構(gòu)造1 1概念：概念： 由按照一定的條件反復(fù)執(zhí)行的某些由按照一定的條件反復(fù)執(zhí)行的某些步驟組成的邏輯構(gòu)造，稱為循環(huán)構(gòu)造步驟組成的邏輯構(gòu)造，稱為循環(huán)構(gòu)造. .2 2程序框圖：程序框圖：循環(huán)體循環(huán)體滿足條件？滿足條件？是是否否循環(huán)體循環(huán)體滿足條件？滿足條件？是是否否

4、7.7.算法的輸入語句算法的輸入語句INPUT INPUT “提示內(nèi)容；變量提示內(nèi)容；變量8.8.算法的輸出語句算法的輸出語句PRINT PRINT “提示內(nèi)容；表達(dá)式提示內(nèi)容；表達(dá)式9.9.算法的賦值語句算法的賦值語句變量變量= =表達(dá)式表達(dá)式10.10.算法的條件語句算法的條件語句IF IF 條件條件 THEN THEN 語句體語句體END IFEND IFIF IF 條件條件 THEN THEN 語句體語句體1 1ELSEELSE 語句體語句體2 2END IFEND IF滿足條件？滿足條件？步驟步驟1步驟步驟1是是否否滿足條件？滿足條件？步驟步驟A是是否否11.11.算法的循環(huán)語句算法

5、的循環(huán)語句DODO 循環(huán)體循環(huán)體LOOP UNTIL LOOP UNTIL 條件條件滿足條件？滿足條件？是是循環(huán)體循環(huán)體否否WHILE WHILE 條件條件 循環(huán)體循環(huán)體WEND WEND 循環(huán)體循環(huán)體滿足條件？滿足條件？是是否否12.12.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n(mn).n(mn).第二步，計算第二步，計算m m除以除以n n所得的余數(shù)所得的余數(shù)r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，假設(shè)第四步，假設(shè)r=0r=0，那么，那么m m，n n的最大公約的最大公約數(shù)等數(shù)等 于于m m；否那么，前往第二步；否那么，前往第二

6、步. . 求兩個正整數(shù)的最大公約數(shù)求兩個正整數(shù)的最大公約數(shù)13.13.更相減損術(shù)更相減損術(shù)第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n(mn). n(mn). 第二步，計算第二步，計算m-nm-n所得的差所得的差k. k. 第三步，比較第三步，比較n n與與k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，假設(shè)第四步，假設(shè)m=nm=n，那么，那么m m，n n的最大公約數(shù)等的最大公約數(shù)等于于 m m；否那么，前往第二步；否那么，前往第二步. . 求兩個正整數(shù)的最大公約數(shù)求兩個正整數(shù)的最大公約數(shù)14.14.秦九韶算法秦九韶算法第一步

7、，輸入多項式的次數(shù)第一步，輸入多項式的次數(shù)n n，最高次，最高次 項的系數(shù)項的系數(shù)anan和和x x的值的值. . 第二步，令第二步，令v=anv=an，i=n-1. i=n-1. 第三步，輸入第三步，輸入i i次項的系數(shù)次項的系數(shù)ai. ai. 第四步，第四步，v=vx+aiv=vx+ai，i=i-1.i=i-1.第五步，判別第五步，判別i0i0能否成立能否成立. .假設(shè)是，那么前假設(shè)是，那么前往第往第 二步；否那么，輸出多項式的值二步；否那么，輸出多項式的值v. v. 求多項式求多項式f(x)=anxn+an-1xn-1+a1x+a0f(x)=anxn+an-1xn-1+a1x+a0的的值

8、值15.k15.k進(jìn)制化十進(jìn)制的算法進(jìn)制化十進(jìn)制的算法110( )110110nnknnnna aa aakakakak-=+LL第四步，判別第四步，判別in in 能否成立能否成立. .假設(shè)是，假設(shè)是，那么那么輸出輸出b b的值；否那么，前往的值；否那么，前往第三步第三步. .第一步，輸入第一步，輸入a a，k k和和n n的值的值. .第二步，令第二步，令b=0b=0，i=1.i=1.第三步，第三步， ，i=i+1.i=i+1.1iibbak-=+16. 16. 十進(jìn)制化十進(jìn)制化k k進(jìn)制的算法進(jìn)制的算法第四步，假設(shè)第四步，假設(shè)q0q0，那么，那么a=qa=q，前往第二，前往第二步；步；

9、否那么，輸出全部余數(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ù)，余數(shù)r.r.第三步，把所得的余數(shù)依次從右到左排第三步，把所得的余數(shù)依次從右到左排 列列. .除除k k取余法取余法 例例 某工廠某工廠20052005年的年消費總值為年的年消費總值為200200萬元，技術(shù)革新后估計以后每年的年消萬元，技術(shù)革新后估計以后每年的年消費總值都比上一年增長費總值都比上一年增長5%.5%.設(shè)計一個程序，設(shè)計一個程序，輸出估計年消費

10、總值超越輸出估計年消費總值超越300300萬元的最早萬元的最早年份年份. .第三步，判別所得的結(jié)果能否大于第三步，判別所得的結(jié)果能否大于300.300. 假設(shè)是，那么輸出該年的年份；否假設(shè)是，那么輸出該年的年份；否那么，那么， 前往第二步前往第二步. .第一步，輸入第一步，輸入20052005年的年消費總值年的年消費總值. .第二步，計算下一年的年消費總值第二步，計算下一年的年消費總值. .算法分析：算法分析：穩(wěn)定練習(xí)穩(wěn)定練習(xí)3 3控制條件：當(dāng)控制條件：當(dāng)“a300a300時終止循環(huán)時終止循環(huán). .1 1循環(huán)體：設(shè)循環(huán)體：設(shè)a a為某年的年消費總值，為某年的年消費總值，t t為年消費總值的年增長量，為年消費總值的年增長量，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)構(gòu)造：循環(huán)構(gòu)造：開場開場n=2005a=200t=0.05aa=a+tn=n+1a300？終了終了輸出輸出n是是否否程序框圖：程序框圖：程序：程序：開場開場n=2005a=200t=0.05aa=a+tn=n+1