算法初步知識結(jié)構(gòu)算法程序框圖算法語句輾轉(zhuǎn)相除法與更相減損術(shù)

秦九韶算法

進(jìn)位制知識梳理1.算法的概念

在數(shù)學(xué)中，按照一定規(guī)則解決某一類問題的明確和有限的步驟稱為算法.

第一步，

令i=2；第一步，

令i=2；第一步，

第二步，

用i除89，得到余數(shù)r；令i=2；第一步，

第二步，

用i除89，得到余數(shù)r；令i=2；第一步，

第三步，

第二步，

用i除89，得到余數(shù)r；令i=2；第一步，

第三步，

第二步，

用i除89，得到余數(shù)r；令i=2；第一步，

第四步，

第三步，

第二步，

用i除89，得到余數(shù)r；令i=2；第一步，

第四步，

第三步，

第二步，

第一步，給定一個(gè)大于2的整數(shù)n.第二步，令i=2．第三步，用i除n，得到余數(shù)r．(1)符合運(yùn)算規(guī)則，計(jì)算機(jī)能操作；(2)每個(gè)步驟都有一個(gè)明確的計(jì)算任務(wù)；(4)步驟個(gè)數(shù)盡可能少；(5)每個(gè)步驟的語言描述要準(zhǔn)確、簡明．(3)對重復(fù)操作步驟作返回處理；知識梳理1.算法的概念

在數(shù)學(xué)中，按照一定規(guī)則解決某一類問題的明確和有限的步驟稱為算法.

用程序框、流程線及文字說明來表示算法的圖形稱為程序框圖.2.程序框圖的概念3.程序框、流程線的名稱與功能圖形符號

名稱

功能

終端框（起止框）

輸入、輸出框

處理框（執(zhí)行框）

判斷框

流程線表示一個(gè)算法的起始和結(jié)束表示一個(gè)算法輸入和輸出的信息

賦值、計(jì)算判斷某一條件是否成立，成立時(shí)在出口處標(biāo)明“是”或“Y”；不成立時(shí)標(biāo)明“否”或“N”連接程序框，表示算法步驟的執(zhí)行順序4.算法的順序結(jié)構(gòu)（1）概念：（2）程序框圖：步驟n步驟n+12.例1:若一個(gè)三角形的三條邊長分別為a，b，c令，則三角形的面積

.試用這個(gè)公式設(shè)計(jì)一個(gè)計(jì)算三角形面積的算法步驟.第一步，輸入三角形三條邊的邊長 a，b，c.

第二步，計(jì)算

.第三步，計(jì)算

.第四步，輸出S.3:將上述算法的用程序框圖表示。開始結(jié)束輸出S輸入a，b，c4：練習(xí)已知下圖是“求一個(gè)正奇數(shù)的平方-5的值”的程序框圖，若輸出的數(shù)是20，求輸入的數(shù)n的值.開始結(jié)束輸入正整數(shù)n輸出yy=x2-5x=2n+15.算法的條件結(jié)構(gòu)（1）概念：

由若干個(gè)在一定條件下才會被執(zhí)行的步驟組成的邏輯結(jié)構(gòu)，稱為條件結(jié)構(gòu).（2）程序框圖：滿足條件？步驟A步驟B是否滿足條件？步驟A是否2:例2.判斷“以任意給定的3個(gè)正實(shí)數(shù)為三條邊邊長的三角形是否存在”的算法步驟如何設(shè)計(jì)？第二步，判斷a+b>c，b+c>a，c+a>b是否同時(shí)成立.若是，則存在這樣的三角形；否則，不存在這樣的三角形.第一步，輸入三個(gè)正實(shí)數(shù)a，b，c.3:請畫出這個(gè)算法的程序框圖。開始輸入a，b，ca+b>c，b+c>a，c+a>b是否同時(shí)成立？是存在這樣的三角形結(jié)束否不存在這樣的三角形例１：設(shè)計(jì)求一個(gè)數(shù)a的絕對值的算法并畫出相應(yīng)的程序框圖第一步：輸入a;第二步：如果a>=0；則lal＝a，否則lal＝－a；第三步：輸出lal．NY結(jié)束輸出|a|a≥0輸入a開始

|a|=a

|a|=－a3.練習(xí)題練習(xí)鞏固１看下面的程序框圖，分析算法的作用（1）開始結(jié)束輸入xy=3*x*x+4*x+5輸出y（2）開始結(jié)束輸入a,ba<b?否是輸出a,b輸出b,a開始輸入a，b，ca>b?a>c?是x=a是x=c否b>c?否x=b是x=c否輸出x結(jié)束2.考察如下程序框圖，當(dāng)輸入a,b,c分別為3，7，5時(shí)，輸出x=___.1.寫出如下程序框圖所對應(yīng)的函數(shù)解析式。一.練習(xí)題6.算法的循環(huán)結(jié)構(gòu)（1）概念：

由按照一定的條件反復(fù)執(zhí)行的某些步驟組成的邏輯結(jié)構(gòu)，稱為循環(huán)結(jié)構(gòu).（2）程序框圖：循環(huán)體滿足條件？是否循環(huán)體滿足條件？是否直到型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)循環(huán)體滿足條件？是否

這種循環(huán)結(jié)構(gòu)稱為直到型循環(huán)結(jié)構(gòu)，你能指出直到型循環(huán)結(jié)構(gòu)的特征嗎？在執(zhí)行了一次循環(huán)體后，對條件進(jìn)行判斷，如果條件不滿足，就繼續(xù)執(zhí)行循環(huán)體，直到條件滿足時(shí)終止循環(huán).循環(huán)體滿足條件？是否這種循環(huán)結(jié)構(gòu)稱為當(dāng)型循環(huán)結(jié)構(gòu)，你能指出當(dāng)型循環(huán)結(jié)構(gòu)的特征嗎？在每次執(zhí)行循環(huán)體前，對條件進(jìn)行判斷，當(dāng)條件滿足時(shí)，執(zhí)行循環(huán)體，否則終止循環(huán).計(jì)算1+2+3+…+100的值可按如下過程進(jìn)行：第1步，0+1=1.第2步，1+2=3.第3步，3+3=6.第4步，6+4=10.……第100步，4950+100=5050.

我們用一個(gè)累加變量S表示每一步的計(jì)算結(jié)果，即把S+i的結(jié)果仍記為S，從而把第i步表示為S=S+i，其中S的初始值為0，i依次取1，2，…，100，通過重復(fù)操作，上述問題的算法如何設(shè)計(jì)？

第四步，判斷i>100是否成立.若是，則輸出S，結(jié)束算法；否則，返回第二步.第一步，令i=1，S=0.第二步，計(jì)算S+i，仍用S表示.第三步，計(jì)算i+1，仍用i表示.思考5:用直到型循環(huán)結(jié)構(gòu)，上述算法的程序框圖如何表示？開始i=1i>100？是輸出S結(jié)束S=0i=i+1S=S+i否思考6:用當(dāng)型循環(huán)結(jié)構(gòu)，上述算法的程序框圖如何表示？開始i=1結(jié)束輸出S否是S=0S=S+ii≤100？i=i+1例1：用描點(diǎn)法作函數(shù)y=x3+3x2-24x+30的圖象時(shí)，需要求出自變量和函數(shù)的一組對應(yīng)值，編寫程序，分別計(jì)算當(dāng)x=-5，-4，-3，-2，-1，0，1，2，3，4，5時(shí)的函數(shù)值。算法：S1：輸入一個(gè)自變量X值S2：計(jì)算y=x3+3x2-24x+30S3：輸出y開始輸入X

y=x3+3x2-24x+30輸出y結(jié)束程序框圖：計(jì)算機(jī)程序：Input“x=“;xy=x^3+3*x^2-24*x+30PrintyendInput“x=“;xy=x^3+3*x^2-24*x+30Printyend輸入語句輸出語句1、輸入語句：一般格式：INPUT“提示信息“；變量程序框圖輸入變量的值例：INPUT“a,b,c=“;a,b,c2、輸出語句：一般格式：PRINT“提示內(nèi)容”;表達(dá)式輸出表達(dá)式的值例：PRINT“S=“;S賦值語句3、賦值語句：一般格式：變量=表達(dá)式程序框圖變量=表達(dá)式說明：計(jì)算機(jī)執(zhí)行賦值語句時(shí)，先計(jì)算”=“右邊的表達(dá)式的值，然后把這個(gè)值賦給”=“左邊的變量。例：給一個(gè)變量重復(fù)賦值.程序如下：A=10A=A+15PRINTAEND問：A的輸出值是多少?

A=25例：交換兩個(gè)變量A和B的值，并輸出交換前后的值.INPUTA,BPRINTA,BX=AA=BB=XPRINTA,BEND練習(xí)反饋一、分析下面程序執(zhí)行的結(jié)果INPUT“A,B=”;A,BB=A+BA=B-AB=B-APRINT“A,B=”;A,BEND(運(yùn)行時(shí)從鍵盤輸入3,7)(1)(2)A=-1000A=A+100PRINT“A=”;AEND

將一個(gè)變量的值賦給另一個(gè)變量，前一個(gè)變量的值保持不變；可先后給一個(gè)變量賦多個(gè)不同的值，但變量的取值總是最近被賦予的值。A=－900A，B=7，3二、某工種是計(jì)件算工資的，每月工資=每月完成的數(shù)量（件）×每件工資。試編寫一程序，通過輸入每件工資和完成數(shù)量，輸出每月工資。

INPUT“每件工資=”；AINPUT“完成數(shù)量=”；BM=A*BPRINT“每月工資=”;MEND練習(xí)反饋算法的輸入語句INPUT“提示內(nèi)容”；變量算法的輸出語句PRINT“提示內(nèi)容”；表達(dá)式算法的賦值語句變量=表達(dá)式算法的條件語句IF條件

THEN

語句體ENDIFIF條件

THEN

語句體1ELSE

語句體2ENDIF滿足條件？步驟1步驟2是否滿足條件？步驟A是否算法的循環(huán)語句DO

循環(huán)體LOOPUNTIL條件滿足條件？是循環(huán)體否WHILE

條件

循環(huán)體WEND

循環(huán)體滿足條件？是否直到型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)12.輾轉(zhuǎn)相除法第一步，給定兩個(gè)正整數(shù)m，n(m>n).第二步，計(jì)算m除以n所得的余數(shù)r.第三步，m=n，n=r.第四步，若r=0，則m，n的最大公約數(shù)等 于m；否則，返回第二步.

求兩個(gè)正整數(shù)的最大公約數(shù)13.更相減損術(shù)第一步，給定兩個(gè)正整數(shù)m，n(m>n).

第二步，計(jì)算m-n所得的差k.第三步，比較n與k的大小，其中大者用m表 示，小者用n表示.

第四步，若m=n，則m，n的最大公約數(shù)等于 m；否則，返回第二步.求兩個(gè)正整數(shù)的最大公約數(shù)14.秦九韶算法第一步，輸入多項(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.求多項(xiàng)式f(x)=anxn+an-1xn-1+…+a1x+a0的值15.k進(jìn)制化十進(jìn)制的算法第四步，判斷i>n是否成立.若是，則 輸出b的值；否則，返回第三步.第一步，輸入a，k和n的值.第二步，令b=0，i=1.第三步，，i=i+1.16.十進(jìn)制化k進(jìn)制的算法第四步，若q≠0，則a=q，返回第二步； 否則，輸出全部余數(shù)r排列得到 的k進(jìn)制數(shù).第一步，輸入十進(jìn)制數(shù)a和基數(shù)k的值.第二步，求出a除以k所得的商q，余數(shù)r.第三步，把所得的余數(shù)依次從右到左排 列.除k取余法

例某工廠2005年的年生產(chǎn)總值為200萬元，技術(shù)革新后預(yù)計(jì)以后每年的年生產(chǎn)總值都比上一年增長5%.設(shè)計(jì)一個(gè)程序，輸出預(yù)計(jì)年生產(chǎn)總值超過300萬元的最早年份.第三步，判斷所得的結(jié)果是否大于300. 若是，則輸出該年的年份；否則， 返回第二步.第一步，輸入2005年的年生產(chǎn)總值.第二步，計(jì)算下一年的年生產(chǎn)總值.算法分析：鞏固練習(xí)（3）控制條件：當(dāng)“a>300”時(shí)終止循環(huán).（1）循環(huán)體：設(shè)a為某年的年生產(chǎn)總值，t為年生產(chǎn)總