1、一、知識結構一、知識結構算法算法程序框圖程序框圖算法語句算法語句輾轉相除法與輾轉相除法與更相減損術更相減損術 秦九韶算法秦九韶算法 進位制進位制二、知識梳理二、知識梳理1.1.算法的概念算法的概念 在數學中，按照一定規則解決某一類問題的在數學中，按照一定規則解決某一類問題的明確和有限的步驟稱為算法明確和有限的步驟稱為算法. . 用程序框、流程線及文字說明來表示算法的圖用程序框、流程線及文字說明來表示算法的圖形稱為程序框圖形稱為程序框圖. .2.2.程序框圖的概念程序框圖的概念3.3.程序框、流程線的名稱與功能程序框、流程線的名稱與功能圖形符號圖形符號 名名 稱稱 功功 能能 終端框終端框 （起

2、止框）（起止框） 輸入、輸出輸入、輸出框框 處理框處理框 （執行框）（執行框） 判斷框判斷框 流程線流程線 表示一個算法的起始和結束表示一個算法的起始和結束 表示一個算法輸入和輸出的表示一個算法輸入和輸出的信息信息 賦值、計算賦值、計算 判斷某一條件是否成立，成立時在判斷某一條件是否成立，成立時在出口處標明出口處標明“是是”或或“Y”Y”；不成立；不成立時標明時標明“否否”或或“N” N” 連接程序框，表示算法步驟的連接程序框，表示算法步驟的執行順序執行順序 4.4.算法的順序結構算法的順序結構（1 1）概念：）概念： 由若干個依次執行的步驟組成的邏輯結構，由若干個依次執行的步驟組成的邏輯結構

3、，稱為順序結構稱為順序結構. .（2 2）程序框圖：）程序框圖：步驟步驟n步驟步驟n+15.5.算法的條件結構算法的條件結構（1 1）概念：）概念： 由若干個在一定條件下才會被執行的步驟組由若干個在一定條件下才會被執行的步驟組成的邏輯結構，稱為條件結構成的邏輯結構，稱為條件結構. .（2 2）程序框圖：）程序框圖：滿足條件？滿足條件？步驟步驟A步驟步驟B是是否否滿足條件？滿足條件？步驟步驟A是是否否6.6.算法的循環結構算法的循環結構（1 1）概念：）概念： 由按照一定的條件反復執行的某些步驟組成由按照一定的條件反復執行的某些步驟組成的邏輯結構，稱為循環結構的邏輯結構，稱為循環結構. .（2

4、2）程序框圖：）程序框圖：循環體循環體滿足條件？滿足條件？是是否否循環體循環體滿足條件？滿足條件？是是否否7.7.算法的輸入語句算法的輸入語句INPUT “INPUT “提示內容提示內容”；變量；變量8.8.算法的輸出語句算法的輸出語句PRINT “PRINT “提示內容提示內容”；表達式；表達式9.9.算法的賦值語句算法的賦值語句變量變量= =表達式表達式10.10.算法的條件語句算法的條件語句IF IF 條件條件 THENTHEN 語句體語句體END IFEND IFIFIF 條件條件 THENTHEN 語句體語句體1 1ELSEELSE 語句體語句體2 2END IFEND IF滿足條件

5、？滿足條件？步驟步驟1步驟步驟1是是否否滿足條件？滿足條件？步驟步驟A是是否否11.11.算法的循環語句算法的循環語句DODO 循環體循環體LOOP UNTILLOOP UNTIL 條件條件滿足條件？滿足條件？是是循環體循環體否否WHILEWHILE 條件條件 循環體循環體WENDWEND 循環體循環體滿足條件？滿足條件？是是否否12.12.輾轉相除法輾轉相除法第一步，給定兩個正整數第一步，給定兩個正整數m m，n(mn(mn).n).第二步，計算第二步，計算m m除以除以n n所得的余數所得的余數r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，則，

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

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

8、an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值的值第一步，輸入第一步，輸入a,ka,k和和n n的值；的值；第二步，將第二步，將b b的值初始化為的值初始化為0,i0,i的值初始化為的值初始化為1 1；第三步，第三步，b=b+ab=b+ai i* *k ki-1i-1, i=i+1;, i=i+1;第四步，判斷第四步，判斷inin是否成立是否成立. .若是若是, ,則執行第五則執行第五步步, ,否則否則, ,返回第三步；返回第三步；第五步，輸出第五步，輸出b b的值的值. .15.k15.k進制化十進制的算法進制化十進制的算法110( )110110(10)nnknnnn

9、a aa aakakakak16. 16. 十進制化十進制化k k進制的算法進制的算法第四步，若第四步，若q0q0，則，則a=qa=q，返回第二步；否則，返回第二步；否則，輸出全部余數輸出全部余數r r排列得到的排列得到的k k進制數進制數. .第一步，輸入十進制數第一步，輸入十進制數a a和基數和基數k k的值的值. .第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余數，余數r.r.第三步，把所得的余數依次從右到左排列第三步，把所得的余數依次從右到左排列. .除除k k取余法取余法三、鞏固練習三、鞏固練習 習題習題1.3 B組：組：某班有某班有45位學生，設計一個算法，

10、輸入每個學生的數學成位學生，設計一個算法，輸入每個學生的數學成績后，分別統計在區間績后，分別統計在區間0,60), 60,80), 80,100內的成績的個數，用自然語言內的成績的個數，用自然語言描述算法步驟，可用描述算法步驟，可用a(i)表示第表示第i個學生的成績。個學生的成績。算法步驟：算法步驟：S1:令令p=0,q=0,m=0，i=1,n=45S2:輸入學生的成績輸入學生的成績ts3:判斷判斷0t60，若是則，若是則p=p+1,執行執行S6s4:判斷判斷60t80，若是則，若是則q=q+1,執行執行S6s5:判斷判斷80t 100，若是則，若是則m=m+1, 執行執行S6開始p=0,q=

11、0,m=0,i=1,n=45輸入t0t6060t45i=i+1 輸出p,q,m結束p=p+1q=q+1m=m+1YYYYNNNNS6:i=i+1,判斷是否判斷是否i45,若是執行若是執行S7，否則返回，否則返回S2S7：輸出輸出p,q,m開始p=0,q=0,m=0,i=1,n=45輸入t0t6060t45i=i+1 輸出p,q,m結束p=p+1q=q+1m=m+1YYYYNNNNp=0q=0m=0i=1n=45DOINPUT “ t=“;tIF 0=t AND t60 THENp=p+1END IFIF 60=t AND t80 THENq=q+1ENF IFIF 80=t AND t45PR

12、INT “p,q,m=“;p.q.mEND復習參考題復習參考題:A組組:1、畫程序框圖對于輸入的、畫程序框圖對于輸入的X值，輸出相應的值，輸出相應的Y值：值： 0 (x0)(1)y= 1 (0 x1) x (x1) (x+2)2 (x0)(2)開始開始輸入輸入XX0y=0 x1y=xy=1輸出輸出y結束結束NYYN開始開始輸入輸入XX0y=(x+2)2x=0y=4y=(x-2)2輸出輸出y結束結束NYYN1. INPUT “a1,b1,c1=“;a1,b1,c1 INPUT “a2,b2,c2=“;a2,b2,c2 d=a1*b2-a2*b1 IF D0 THEN x=(b2*c1-b1*c2

13、)/d y=(a1*c2-a2*c1)/d PRINT “x,y=“; x,y ELSE PRINT “輸入的數據不符題意輸入的數據不符題意” END IF END 開始開始d0 x=(b2*c1-b1*c2)/dy=(a1*c2-a2*c1)/d輸出輸出x,y輸入的數據不符題意輸入的數據不符題意結束結束輸入輸入 a1,b1,c1輸入輸入a2,b2,c2d=a1*b2-a2*b12、求解二元一次方程組：、求解二元一次方程組：NY3、某市固定電話（市話）的收費標準為：、某市固定電話（市話）的收費標準為：3分鐘之內（包括三分鐘分鐘之內（包括三分鐘)收取收取0.2元元;超過超過3分鐘分鐘,每分鐘每分

14、鐘(不足一分鐘不足一分鐘,按一分鐘計算按一分鐘計算)按按0.10元計算元計算,設計一個算法設計一個算法,根據根據通話時間計算話費通話時間計算話費.INPUT “t=“;tIf t0 then PRINT “輸入有誤輸入有誤”END IFIF t0 THEN y=0.2ELSE t=t1+1 y=0.1*tEND IFPRINT y;”元元”END 開始開始t0輸入輸入t0tni=i+1輸出輸出s結束結束YNi=1,s=0s=s+1/iINPUT “n=“;ni=1s=0DO s=s+1/i i=i+1LOOP UNTIL inPRINT sEND5.一個球從一個球從100M高處自由落下高處自由

15、落下,每次著地后又跳回到原來高度的一半再落下每次著地后又跳回到原來高度的一半再落下,編寫編寫程序程序,求當它第求當它第10次著地時次著地時,(1)向下的運動共經過多少米向下的運動共經過多少米?(2).第第10次著地后反彈多次著地后反彈多高高?(3).全程共經過多少米全程共經過多少米?開始開始k=10i=i/2輸出輸出i結束結束YNk=1,s=0s=s+ii=100k=k+1輸出輸出2s-100輸出輸出sk=1s=0i=100WHILE k=100 s=s+I i=i/2 k=k+1WENDPRINT “(1)=“;sPRINT “(2)=“;iPRINT “(3)=“;2*s-100END 復

16、習參考題復習參考題B組：組：1、編寫程序，將用戶輸入的正、編寫程序，將用戶輸入的正整數轉換成相應的星期值輸出。整數轉換成相應的星期值輸出。開始開始輸入輸入 nr=0r=1r=2r=3r=4r=5r=6結束結束r=n mod 7SundayTuesdayMondayWednesdayThursdayFridaySaturdayYYYYYYYNNNNNNNINPUT “n=“;nr=n MOD 7IF r=0 THEN PRINT “Sunday”END IFIF r=1 THEN PRINT “Monday”END IFIF r=2 THEN PRINT “Tuesday”END IFIF r=

17、3 THEN PRINT “Wednesday”END IFIF r=4 THEN PRINT “Thursday”END IFIF r=5 THEN PRINT “Friday”END IFIF r=6 THEN PRINT “Saturday”END IFend開始開始輸入輸入nr=n MOD 7r=0輸出星期日輸出星期日輸出輸出 r結束結束NYINPUT “n=“;nr =n MOD 7IF r =0 THENPRINT “星期日星期日”ELSEPRINT ”星期星期”;rEND IFEND2.畫出程序框圖畫出程序框圖,用二分法求方程用二分法求方程1.3x2-26.013x2+0.975

18、x-19.50975=0在在(20,21)之之間的近似根間的近似根(精確度為精確度為0.005)開始開始a=20：b=21:d=0.005f(x)=1.3x2-26.013x2+0.975x-19.50975m=(a+b)/2b=ma=mf(a)f(m)0|a-b|d或或f(m)= 0結束結束輸出所求的近似根輸出所求的近似根m否否是是否否是是a=20b=21d=0.005y=1.3*x3-26.013*x2+0.975*x-19.50975DO m=(a+b)/2 g= 1.3*a3-26.013*a2+0.975*a-19.50975 f=1.3*m3-26.013*m2+0.975*m-19.50975 IF g*f0 THEN b=m ELSE a=m END IFLOOP UNTIL ABS(a-b)2)位數是位數是不是回文數，用自然語言描述算法步驟。不是回文數，用自然語言描述算法步驟。算法步驟：算法步驟：S1：輸入一個正整數輸入一個正整數X和它的位數和它的位數n。S2：判斷判斷n是不是偶數，如果是不是偶數，如果n是偶數，令是偶數，令m=n/2,如果如果n 是奇數，令是奇數，令m=(n-1)/2。S3：當當I 從從1到到m取值時，依次判斷取值時，依次判斷x的第的第i位與第位與第(n+i-1)位位是的數字是不是相等，如果都相等，則是的數字是