算法初步課件

1、a1a2a3先先去括號(hào)去括號(hào)再再乘除乘除后后加減加減65 (42) 1、什么是算法呢？什么是算法呢？a4 要把大象裝冰箱，分幾步？要把大象裝冰箱，分幾步？答：分三步：答：分三步：第一步：翻開冰箱門第一步：翻開冰箱門第二步：把大象裝冰箱第二步：把大象裝冰箱第三步：關(guān)上冰箱門第三步：關(guān)上冰箱門問(wèn)：?jiǎn)枺?問(wèn)題問(wèn)題a5 簡(jiǎn)單地說(shuō)，算法就是解決問(wèn)題的程序或步驟。什么是算法呢？什么是算法呢？a6第一步第一步, ,第二步第二步, ,第三步第三步, ,消元消元解一元一次方程解一元一次方程+ +2 2，得，得 711x 解得解得117x 代入求解代入求解117x 將將 代入代入, ,得得67y 寫一寫寫一寫解方

2、程組解方程組32324xyx y 寫出寫出的步驟的步驟a7寫出解第二個(gè)方程組的算法：寫出解第二個(gè)方程組的算法：第一步第一步, ,第二步第二步, ,第三步第三步, ,2 11 22 11 2()a ba bya ca c解，得 2 11 22 11 2a ca cya ba b將代入得2a1a 得32324xyx y 1 22 12 11 2bcb cxa bab變一變變一變111222a x b y ca x b y c1 22 1(0)aba ba8 在數(shù)學(xué)上，通常是按照一定規(guī)那在數(shù)學(xué)上，通常是按照一定規(guī)那么解決某一類問(wèn)題的明確有限的步么解決某一類問(wèn)題的明確有限的步驟。驟。算法的定義：a9例

3、例1 (1)設(shè)計(jì)一個(gè)算法設(shè)計(jì)一個(gè)算法,判斷判斷7是是否為質(zhì)數(shù)否為質(zhì)數(shù);(1)(1)第一步第一步, ,用2除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以2不能整除7.第二步第二步, ,用3除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以3不能整除7.第三步第三步, ,用4除7,得到余數(shù)3.因?yàn)橛鄶?shù)不為0,所以4不能整除7.第四步第四步, ,用5除7,得到余數(shù)2.因?yàn)橛鄶?shù)不為0,所以5不能整除7.第五步第五步, ,用6除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0,所以6不能整除7.因此,7是質(zhì)數(shù).a10(2)設(shè)計(jì)一個(gè)算法設(shè)計(jì)一個(gè)算法,判斷判斷35是否為質(zhì)數(shù)是否為質(zhì)數(shù).算法: 第一步第一步, ,用2除35,得到余數(shù)1.因?yàn)橛鄶?shù)不

4、為0,所以2不能整除35.第二步第二步, ,用3除35,得到余數(shù)2.因?yàn)橛鄶?shù)不為0,所以3不能整除35.第三步第三步, ,用4除35,得到余數(shù)3.因?yàn)橛鄶?shù)不為0,所以4不能整除35.第四步第四步, ,用5除35,得到余數(shù)0.因?yàn)橛鄶?shù)為0,所以5能整除35.因此,35不是質(zhì)數(shù).a11探究你能寫出判斷整數(shù)n(n2)是否為質(zhì)數(shù)的算法嗎? 第一步第一步, ,給定大于2的整數(shù)n. 第二步第二步, ,令i=2. 第三步第三步, ,用i除n,得到余數(shù)r. 第四步第四步, ,判斷”r=0”是否成立.若是,則n不是質(zhì)數(shù),結(jié)束算法;否則,將i的值增加1,仍用i表示. 第五步第五步, ,判斷”i(n-1)”是否成立

5、.若是,則n是質(zhì)數(shù),結(jié)束算法;否則,返回第三步.a12算法的根本特點(diǎn)算法的根本特點(diǎn)1、有窮性、有窮性一個(gè)算法應(yīng)包括有限的操作步驟，能在執(zhí)行有窮一個(gè)算法應(yīng)包括有限的操作步驟，能在執(zhí)行有窮的操作步驟之后結(jié)束。的操作步驟之后結(jié)束。2、確定性、確定性算法的計(jì)算規(guī)那么及相應(yīng)的計(jì)算步驟必須是唯一算法的計(jì)算規(guī)那么及相應(yīng)的計(jì)算步驟必須是唯一確定的，既不能模糊其詞，也不能有二義性。確定的，既不能模糊其詞，也不能有二義性。3、邏輯性、邏輯性算法中從開始的算法中從開始的“第一步到第一步到“最后一步之間最后一步之間做到做到環(huán)環(huán)相扣，分工明確，環(huán)環(huán)相扣，分工明確，“前一步是前一步是“后一步后一步的前提，的前提，“后一步

6、是后一步是“前一步的繼續(xù)。前一步的繼續(xù)。a13算法算法1 1：第二步第二步：計(jì)算：計(jì)算1011015050；第三步第三步：寫出運(yùn)算結(jié)果：寫出運(yùn)算結(jié)果算法算法2 2：第一步第一步：?。喝=100n=100；第二步第二步：計(jì)算：計(jì)算(1)2n n第三步第三步：寫出運(yùn)算結(jié)果：寫出運(yùn)算結(jié)果寫出求寫出求1+2+3+ +1001+2+3+ +100的一個(gè)算法的一個(gè)算法(1+100)+(2+99)+ +(50+51)(1+100)+(2+99)+ +(50+51)；第一步第一步：將原式變形為：將原式變形為你會(huì)了嗎？你會(huì)了嗎？a142.2.任意給定一個(gè)正實(shí)數(shù)任意給定一個(gè)正實(shí)數(shù), ,設(shè)計(jì)一個(gè)算法求以這個(gè)設(shè)計(jì)一

7、個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積數(shù)為半徑的圓的面積. .第一步第一步:輸入任意一個(gè)正實(shí)數(shù)輸入任意一個(gè)正實(shí)數(shù)r0；第二步第二步:計(jì)算圓的面積計(jì)算圓的面積: S=r2;第三步第三步:輸出圓的面積輸出圓的面積S.a15a16程序框圖程序框圖程序框圖又稱流程圖，是一種用程程序框圖又稱流程圖，是一種用程序框、流程線及文字說(shuō)明來(lái)表示算法序框、流程線及文字說(shuō)明來(lái)表示算法的圖形。的圖形。 在程序框圖中，一個(gè)或幾個(gè)程序框的組合表示算在程序框圖中，一個(gè)或幾個(gè)程序框的組合表示算法中的一個(gè)步驟；帶有方向箭頭的流程線將程序框法中的一個(gè)步驟；帶有方向箭頭的流程線將程序框連接起來(lái)，表示算法步驟的執(zhí)行順序。連接起來(lái)，表示算法

8、步驟的執(zhí)行順序。a17圖形符號(hào)圖形符號(hào)名稱名稱功能功能終端框（起止終端框（起止框）框） 表示一個(gè)算法的起始和結(jié)束表示一個(gè)算法的起始和結(jié)束 輸入、輸出框輸入、輸出框 表示一個(gè)算法輸入和輸出的信息表示一個(gè)算法輸入和輸出的信息 處理框處理框 賦值、計(jì)算賦值、計(jì)算判斷框判斷框 判斷某一條件是否成立，成立時(shí)在判斷某一條件是否成立，成立時(shí)在出口處標(biāo)明出口處標(biāo)明“是是”或或“Y”；不成立時(shí)；不成立時(shí)標(biāo)明標(biāo)明“否否”或或“N”。 流程線流程線 連接程序框連接程序框 連接點(diǎn)連接點(diǎn) 連接程序框圖的兩部分連接程序框圖的兩部分 a18例例 用程序框圖表示用程序框圖表示“判判斷整數(shù)斷整數(shù)n nn2n2是否為質(zhì)是否為質(zhì)數(shù)

9、的算法數(shù)的算法a19開始開始輸入輸入ni=2求求n除以除以i的余數(shù)的余數(shù)ri的值增加的值增加1仍用仍用i表示表示in-1或或r=0?輸出輸出“n不是質(zhì)數(shù)不是質(zhì)數(shù)”結(jié)束結(jié)束是是否否是是輸出輸出“n是質(zhì)數(shù)是質(zhì)數(shù)”否否r=0?設(shè)設(shè)n是一個(gè)大是一個(gè)大于于2的整數(shù)的整數(shù).一般用一般用i=i+1表示表示. i=i+1說(shuō)明說(shuō)明:i表示從表示從2(n-1)的所有正整數(shù)的所有正整數(shù),用以用以判斷例判斷例1步驟步驟2是否終是否終止止,i是一個(gè)計(jì)數(shù)變量是一個(gè)計(jì)數(shù)變量,有了這個(gè)變量有了這個(gè)變量,算法算法才能依次執(zhí)行才能依次執(zhí)行.逐步逐步考察從考察從2(n-1)的所的所有正整數(shù)中是否有有正整數(shù)中是否有n的因數(shù)存在的因數(shù)

10、存在.a201 1使用標(biāo)準(zhǔn)的圖形符號(hào)。使用標(biāo)準(zhǔn)的圖形符號(hào)。2 2框圖一般按從上到下，從左到右的方向畫?？驁D一般按從上到下，從左到右的方向畫。 3 3除判斷框外，大多數(shù)流程圖符號(hào)只有一個(gè)除判斷框外，大多數(shù)流程圖符號(hào)只有一個(gè)進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框具有超過(guò)一個(gè)退出進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框具有超過(guò)一個(gè)退出點(diǎn)的唯一符號(hào)。點(diǎn)的唯一符號(hào)。 4 4判斷框分兩大類，一類判斷框判斷框分兩大類，一類判斷框“是與是與“否否兩分支的判斷，而且又且僅有兩個(gè)結(jié)果；另一類兩分支的判斷，而且又且僅有兩個(gè)結(jié)果；另一類是多分支判斷，有幾種不同的結(jié)果。是多分支判斷，有幾種不同的結(jié)果。 5 5在圖形符號(hào)內(nèi)描述的語(yǔ)言要非常簡(jiǎn)練清楚

11、。在圖形符號(hào)內(nèi)描述的語(yǔ)言要非常簡(jiǎn)練清楚。 a21a22開始開始輸入輸入ni=2求求n除以除以i的余數(shù)的余數(shù)ri=i+1in或或r=0?n不是質(zhì)數(shù)不是質(zhì)數(shù)結(jié)束結(jié)束是是否否是是n是質(zhì)數(shù)是質(zhì)數(shù)否否r=0?順序結(jié)構(gòu)順序結(jié)構(gòu)用程序框圖來(lái)表示算法，有用程序框圖來(lái)表示算法，有三種不同的根本邏輯結(jié)構(gòu)：三種不同的根本邏輯結(jié)構(gòu)：條件結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)a23三種根本結(jié)構(gòu)表示一個(gè)良好算法的根本單元三種根本結(jié)構(gòu)表示一個(gè)良好算法的根本單元順序結(jié)構(gòu)順序結(jié)構(gòu)條件結(jié)構(gòu)選擇結(jié)構(gòu)條件結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)ABPAB成立成立不成立不成立 成立成立AP不成立不成立AP成立成立不成立不成立While當(dāng)型循環(huán)當(dāng)型循環(huán)Unt

12、il直到型循環(huán)直到型循環(huán)a24順序結(jié)構(gòu)順序結(jié)構(gòu) 順序結(jié)構(gòu)是由假設(shè)干個(gè)依次執(zhí)行的步驟組成的。這是任何一個(gè)算法都離不開的根本結(jié)構(gòu)ABa25例1 一個(gè)三角形的三邊邊長(zhǎng)分別為a、b、c，利用海倫-秦九韶公式設(shè)計(jì)一個(gè)算法，求出它的面積，畫出它的程序框圖.第一步：輸入三角形三條邊的邊長(zhǎng) a，b，c；第二步：計(jì)算 ；第三步：計(jì)算 ；第四步：輸出s。()/ 2pabc()()()Sp papbpc算法分析：算法分析：a26開始輸入a，b，c輸出S結(jié)束() / 2pabc()()()Sp papbpc程序框圖程序框圖a27習(xí)題1 設(shè)計(jì)一算法：輸入圓的半徑,輸出圓的面積，并畫出流程圖算法分析：第一步：輸入圓的半徑

13、輸入圓的半徑第二步：利用公式“圓的面積=圓周率半徑的平方計(jì)算圓的面積；第三步：輸出圓的面積。輸出圓的面積。開始結(jié)束輸入半徑R計(jì)算S=Pi*R*R輸出面積S定義Pi=3.14思考：整個(gè)程序框圖有什么特點(diǎn)？a28條件結(jié)構(gòu)選擇結(jié)構(gòu)條件結(jié)構(gòu)選擇結(jié)構(gòu) 算法的流程根據(jù)條件是否成立有不同的算法的流程根據(jù)條件是否成立有不同的流向。條件結(jié)構(gòu)就是處理這種過(guò)程的結(jié)構(gòu)。流向。條件結(jié)構(gòu)就是處理這種過(guò)程的結(jié)構(gòu)。PAB成立成立不成立不成立PA不成立不成立成立成立a29例2 任意給定3個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)算法，判斷分別以這3個(gè)數(shù)為三邊邊長(zhǎng)的三角形是否存在.畫出這個(gè)算法的程序框圖.開始輸入a、b、ca+bc,a+cb,b+ca是

14、否同時(shí)成立存在這樣的三角形結(jié)束否是不存在這樣的三角形a30解：算法如下。S1 輸入xS2 假設(shè)x為奇數(shù)，那么輸出A=3x+2；否那么輸出A=5x S3 算法結(jié)束。習(xí)題2 設(shè)x為一個(gè)正整數(shù)，規(guī)定如下運(yùn)算：假設(shè)x為奇數(shù)，那么求3x+2；假設(shè)x為偶數(shù)，那么為5x，寫出算法，并畫出程序框圖。 x為奇數(shù)？開始輸入xA=3x+2結(jié)束否是A=5xa31循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)AP成立成立不成立不成立While（當(dāng)型）循環(huán)）循環(huán) 成立成立AP不成立不成立Until（直到型）循環(huán)）循環(huán)在一些算法中，從否處開始，按照一定條件，反復(fù)執(zhí)行在一些算法中，從否處開始，按照一定條件，反復(fù)執(zhí)行某一處理步驟的情況，這就是循環(huán)結(jié)構(gòu)。反復(fù)

15、執(zhí)行的處某一處理步驟的情況，這就是循環(huán)結(jié)構(gòu)。反復(fù)執(zhí)行的處理步驟稱為循環(huán)體。理步驟稱為循環(huán)體。在循環(huán)結(jié)構(gòu)中，通常都有一個(gè)起到循環(huán)計(jì)數(shù)作用的變量，在循環(huán)結(jié)構(gòu)中，通常都有一個(gè)起到循環(huán)計(jì)數(shù)作用的變量，這個(gè)變量的取值一般都含在執(zhí)行或中止循環(huán)體的條件中。這個(gè)變量的取值一般都含在執(zhí)行或中止循環(huán)體的條件中。a32例3 設(shè)計(jì)一個(gè)計(jì)算1+2+3+100的值的算法，并畫出程序框圖。算法分析：需要一個(gè)累加變量和一個(gè)計(jì)數(shù)變量，將累加變量的初始值設(shè)為0，計(jì)數(shù)變量的值可以從1到100.i=100?i=1開始輸出sum結(jié)束否是sum=0i=i+1sum=sum+1a33根本算法語(yǔ)句根本算法語(yǔ)句第一章第一章 算法初步算法初步a

16、34【探究新知】【探究新知】我們知道，順序結(jié)構(gòu)是任何一個(gè)算法都離不開我們知道，順序結(jié)構(gòu)是任何一個(gè)算法都離不開的根本結(jié)構(gòu)。的根本結(jié)構(gòu)。語(yǔ)句語(yǔ)句n+1語(yǔ)句語(yǔ)句n 輸入、輸出語(yǔ)句和賦值語(yǔ)句根本上對(duì)應(yīng)輸入、輸出語(yǔ)句和賦值語(yǔ)句根本上對(duì)應(yīng)于算法中的順序結(jié)構(gòu)于算法中的順序結(jié)構(gòu). .計(jì)算機(jī)從上而下按照語(yǔ)句排列計(jì)算機(jī)從上而下按照語(yǔ)句排列的順序執(zhí)行這些語(yǔ)句的順序執(zhí)行這些語(yǔ)句. .輸入語(yǔ)句和輸出語(yǔ)句分別用來(lái)輸入語(yǔ)句和輸出語(yǔ)句分別用來(lái)實(shí)現(xiàn)算法的輸入信息實(shí)現(xiàn)算法的輸入信息, ,輸出結(jié)果的功輸出結(jié)果的功能能. .( (如右圖如右圖) )a35輸入語(yǔ)句和輸出語(yǔ)句分別用來(lái)實(shí)現(xiàn)算法的輸入語(yǔ)句和輸出語(yǔ)句分別用來(lái)實(shí)現(xiàn)算法的輸入信息

17、，輸出結(jié)果的功能。輸入信息，輸出結(jié)果的功能。 例例1 1 用描點(diǎn)法作函數(shù)用描點(diǎn)法作函數(shù)yx3 33 3x2 22424x3030的圖象時(shí)的圖象時(shí), ,需要需要求出自變量和函數(shù)的一組對(duì)應(yīng)值求出自變量和函數(shù)的一組對(duì)應(yīng)值. .編寫程序編寫程序, ,分別計(jì)算當(dāng)分別計(jì)算當(dāng) x5 5，4 4，3 3，2 2，1 1，0 0，1 1，2 2，3 3，4 4，5 5時(shí)的函數(shù)值時(shí)的函數(shù)值. . INPUT “x=;x y=x3+3*x2-24*x+30PRINT xPRINT yEND程序程序: : -輸入語(yǔ)句輸入語(yǔ)句 -賦值語(yǔ)句賦值語(yǔ)句-打印語(yǔ)句打印語(yǔ)句-打印語(yǔ)句打印語(yǔ)句-表示結(jié)束表示結(jié)束輸出語(yǔ)句輸出語(yǔ)句輸出

18、語(yǔ)句輸出語(yǔ)句a36一一. .輸入語(yǔ)句輸入語(yǔ)句 INPUT “INPUT “提示內(nèi)容；變量提示內(nèi)容；變量輸入語(yǔ)句的一般格式輸入語(yǔ)句的一般格式 說(shuō)明說(shuō)明: :(1)(1)輸入語(yǔ)句的作用是實(shí)現(xiàn)算法的輸入信息功能；輸入語(yǔ)句的作用是實(shí)現(xiàn)算法的輸入信息功能；(2)(2)“提示內(nèi)容提示用戶輸入什么樣的信息，提示內(nèi)容提示用戶輸入什么樣的信息，變量是指程序在運(yùn)行時(shí)其值是可以變化的量；變量是指程序在運(yùn)行時(shí)其值是可以變化的量；(3)(3)輸入語(yǔ)句要求輸入的值只能是具體的常數(shù)，輸入語(yǔ)句要求輸入的值只能是具體的常數(shù)，不能是函數(shù)、變量或表達(dá)式；不能是函數(shù)、變量或表達(dá)式；(4)(4)提示內(nèi)容與變量之間用分號(hào)提示內(nèi)容與變量之

19、間用分號(hào)“；隔開，；隔開，假設(shè)輸入多個(gè)變量，變量與變量之間用逗號(hào)假設(shè)輸入多個(gè)變量，變量與變量之間用逗號(hào)“，隔開，隔開. .a37例如例如, ,輸入一個(gè)學(xué)生數(shù)學(xué)輸入一個(gè)學(xué)生數(shù)學(xué), ,語(yǔ)文語(yǔ)文, ,英語(yǔ)三門課的成績(jī)英語(yǔ)三門課的成績(jī), ,可以寫成：可以寫成：INPUT “數(shù)學(xué)，語(yǔ)文，英語(yǔ)；數(shù)學(xué)，語(yǔ)文，英語(yǔ)；a，b，c注意注意: :INPUTINPUT語(yǔ)句不但可以給單個(gè)變量賦值語(yǔ)句不但可以給單個(gè)變量賦值, ,還可以還可以給多個(gè)變量賦值給多個(gè)變量賦值, ,其格式為：其格式為：INPUT “INPUT “提示內(nèi)容提示內(nèi)容1 1，提示內(nèi)容，提示內(nèi)容2 2，提示內(nèi)容，提示內(nèi)容3 3，；變量；變量1 1，變量，

20、變量2 2，變量，變量3 3，練一練練一練:請(qǐng)你用輸入語(yǔ)句表達(dá)課本請(qǐng)你用輸入語(yǔ)句表達(dá)課本P5和和P9頁(yè)程序框圖中輸入框中的內(nèi)容頁(yè)程序框圖中輸入框中的內(nèi)容.P7頁(yè)頁(yè): INPUT “n=; n P9頁(yè)頁(yè):INPUT a, b, c a38二二. .輸出語(yǔ)句輸出語(yǔ)句 PRINT “提示內(nèi)容；表達(dá)式提示內(nèi)容；表達(dá)式說(shuō)明說(shuō)明: :(1)(1)“提示內(nèi)容提示用戶輸出什么樣的信息提示內(nèi)容提示用戶輸出什么樣的信息, ,表表達(dá)式是指程序要輸出的數(shù)據(jù)；達(dá)式是指程序要輸出的數(shù)據(jù)；輸出常量，變量的值和字符串等系統(tǒng)信息。輸出常量，變量的值和字符串等系統(tǒng)信息。輸出數(shù)值計(jì)算的結(jié)果。輸出數(shù)值計(jì)算的結(jié)果。(2)(2)輸出語(yǔ)句

21、的用途：輸出語(yǔ)句的用途： 輸出語(yǔ)句的一般格式輸出語(yǔ)句的一般格式a39(3)同輸入語(yǔ)句一樣，表達(dá)式前也可以有同輸入語(yǔ)句一樣，表達(dá)式前也可以有“提示內(nèi)容提示內(nèi)容.思考思考: :在課本在課本P7P7頁(yè)圖程序框圖中的輸出框的頁(yè)圖程序框圖中的輸出框的內(nèi)容怎樣用輸出語(yǔ)句來(lái)表達(dá)？?jī)?nèi)容怎樣用輸出語(yǔ)句來(lái)表達(dá)？ 參考答案：參考答案：輸出框：輸出框： PRINT PRINT “n is a prime number .n is a prime number . PRINT PRINT “n is not a prime n is not a prime number.number.如如P9頁(yè)的輸出框頁(yè)的輸出框 可以

22、轉(zhuǎn)化為輸出語(yǔ)句可以轉(zhuǎn)化為輸出語(yǔ)句:輸出輸出SPRINT “S=; S a40三三. .賦值語(yǔ)句賦值語(yǔ)句(1)賦值語(yǔ)句的一般格式賦值語(yǔ)句的一般格式:變量表達(dá)式變量表達(dá)式(2)(2)賦值語(yǔ)句的作用是賦值語(yǔ)句的作用是: :先計(jì)算出賦值號(hào)右邊表達(dá)先計(jì)算出賦值號(hào)右邊表達(dá)式的值式的值, ,然后把這個(gè)值賦給左邊的變量然后把這個(gè)值賦給左邊的變量, ,使該變量的使該變量的值等于表達(dá)式的值。值等于表達(dá)式的值。(3)(3)賦值語(yǔ)句中的賦值語(yǔ)句中的“稱作賦值號(hào)稱作賦值號(hào), ,與數(shù)學(xué)中的等與數(shù)學(xué)中的等號(hào)的意義是不同的號(hào)的意義是不同的. .賦值號(hào)的左右兩邊不能對(duì)換賦值號(hào)的左右兩邊不能對(duì)換. .(4)(4)賦值語(yǔ)句左邊只能

23、是變量名字而不是表達(dá)式賦值語(yǔ)句左邊只能是變量名字而不是表達(dá)式, ,如如:2=x:2=x是錯(cuò)誤的是錯(cuò)誤的; ;右邊表達(dá)式可以是一個(gè)數(shù)據(jù)、右邊表達(dá)式可以是一個(gè)數(shù)據(jù)、常量或算式；不能利用賦值語(yǔ)句進(jìn)行代數(shù)式的常量或算式；不能利用賦值語(yǔ)句進(jìn)行代數(shù)式的演算。如化簡(jiǎn)、因式分解、解方程等演算。如化簡(jiǎn)、因式分解、解方程等 5 5對(duì)于一個(gè)變量可以屢次賦值。對(duì)于一個(gè)變量可以屢次賦值。a41【例題解析例題解析】例例2 2：編寫程序，計(jì)算一個(gè)學(xué)生數(shù)學(xué)、語(yǔ)文、：編寫程序，計(jì)算一個(gè)學(xué)生數(shù)學(xué)、語(yǔ)文、英語(yǔ)三門課的平均成績(jī)。英語(yǔ)三門課的平均成績(jī)。分析分析：先寫出算法，畫出程序框圖，再進(jìn)行編程。：先寫出算法，畫出程序框圖，再進(jìn)行編

24、程。結(jié)束結(jié)束開始開始輸入輸入a,b,c輸出輸出y3 3abcy 程序框圖程序框圖INPUT “Maths,Chinese,English；a,b,cy=(a+b+c)/3PRINT “y=；y END程序程序: :a42例例3 3：給一個(gè)變量重復(fù)賦值。：給一個(gè)變量重復(fù)賦值。程序程序: :A=10A=A+15PRINT AENDA的輸出的輸出值是多少值是多少?分析分析:此程序給變量此程序給變量A賦了兩次值賦了兩次值.A的初值為的初值為10,第二次賦值后第二次賦值后,初值被初值被“覆覆蓋蓋,A的值變?yōu)榈闹底優(yōu)?5,因此輸出值是因此輸出值是25.a43 變式引申變式引申:在此程序的根底上，設(shè)計(jì)一個(gè)程

25、序，在此程序的根底上，設(shè)計(jì)一個(gè)程序，要求最后要求最后A A的輸出值是的輸出值是30.30.A=10A=A+15PRINT AA=A+5PRINT AEND程序程序: :例例3 3：給一個(gè)變量重復(fù)賦值。：給一個(gè)變量重復(fù)賦值。程序程序: :A=10A=A+15PRINT AENDa44例例4 4交換兩個(gè)變量交換兩個(gè)變量A A和和B B的值的值, ,并輸出交換前后并輸出交換前后 的值。的值。分析：引入一個(gè)中間變量分析：引入一個(gè)中間變量X,X,將將A A的值賦予的值賦予X,X,又將又將B B的值賦予的值賦予A A，再將，再將X X的值賦予的值賦予B B，從而到達(dá)交換，從而到達(dá)交換A A，B B的值的值

26、. .比方交換裝滿水的兩個(gè)水桶里的水需要比方交換裝滿水的兩個(gè)水桶里的水需要再找一個(gè)空桶再找一個(gè)空桶INPUT AINPUT BPRINT A，BX=AA=BB=XPRINT A，BEND程序程序: :問(wèn)題問(wèn)題:能否用下列賦值能否用下列賦值語(yǔ)句交換語(yǔ)句交換A,B的值的值?A=BB=A不能不能!a45練習(xí)練習(xí)1 1: :編寫一個(gè)程序編寫一個(gè)程序, ,要求輸入一個(gè)圓的半徑要求輸入一個(gè)圓的半徑, ,便能輸出該圓的周長(zhǎng)和面積便能輸出該圓的周長(zhǎng)和面積. . 取取分析分析: :設(shè)圓的半徑為設(shè)圓的半徑為R,R,那么圓的周長(zhǎng)那么圓的周長(zhǎng)C=2R,C=2R,面積面積S=R2,S=R2,可以利用順序結(jié)構(gòu)中的可以利用

27、順序結(jié)構(gòu)中的INPUTINPUT語(yǔ)句語(yǔ)句,PRINT,PRINT語(yǔ)句和賦值語(yǔ)句設(shè)計(jì)程序。語(yǔ)句和賦值語(yǔ)句設(shè)計(jì)程序。INPUT “R=；RC=2*R*R2PRINT “C=；CPRINT “S=； S ENDa46算法中的條件結(jié)構(gòu)是由條件語(yǔ)句來(lái)表達(dá)的算法中的條件結(jié)構(gòu)是由條件語(yǔ)句來(lái)表達(dá)的, ,條件語(yǔ)句是處理?xiàng)l件分支邏輯結(jié)構(gòu)的算法語(yǔ)句條件語(yǔ)句是處理?xiàng)l件分支邏輯結(jié)構(gòu)的算法語(yǔ)句 . .條件語(yǔ)句的一般格式條件語(yǔ)句的一般格式 滿足條件？滿足條件？語(yǔ)句語(yǔ)句是是否否只含一個(gè)只含一個(gè)“分支的條件結(jié)構(gòu)分支的條件結(jié)構(gòu)寫成條件語(yǔ)句為寫成條件語(yǔ)句為IFIF 條件條件 THENTHEN 語(yǔ)句體語(yǔ)句體END IFEND IF當(dāng)

28、計(jì)算機(jī)執(zhí)行這種形式的條件語(yǔ)句時(shí)，首先對(duì)當(dāng)計(jì)算機(jī)執(zhí)行這種形式的條件語(yǔ)句時(shí)，首先對(duì)IFIF后的條件進(jìn)行判斷，如果條件符合，就執(zhí)行后的條件進(jìn)行判斷，如果條件符合，就執(zhí)行THENTHEN后的語(yǔ)句體，否那么執(zhí)行后的語(yǔ)句體，否那么執(zhí)行END IFEND IF之后的語(yǔ)之后的語(yǔ)句句. . a47滿足條件？滿足條件？語(yǔ)句語(yǔ)句1 1語(yǔ)句語(yǔ)句2 2是是否否含兩個(gè)含兩個(gè)“分支的條件結(jié)構(gòu)分支的條件結(jié)構(gòu)寫成條件語(yǔ)句為寫成條件語(yǔ)句為IFIF 條件條件 THENTHEN 語(yǔ)句體語(yǔ)句體1 1ELSEELSE 語(yǔ)句體語(yǔ)句體2 2END IFEND IF當(dāng)計(jì)算機(jī)執(zhí)行上述語(yǔ)句時(shí)，首先對(duì)當(dāng)計(jì)算機(jī)執(zhí)行上述語(yǔ)句時(shí)，首先對(duì)IFIF后的后的條

29、件進(jìn)行判斷，如果條件符合，就執(zhí)行條件進(jìn)行判斷，如果條件符合，就執(zhí)行THENTHEN后后的語(yǔ)句體的語(yǔ)句體1 1，否那么執(zhí)行，否那么執(zhí)行ELSEELSE后的語(yǔ)句體后的語(yǔ)句體2. 2. a48 條件語(yǔ)句的作用條件語(yǔ)句的作用 在程序執(zhí)行過(guò)程中，根據(jù)判斷是在程序執(zhí)行過(guò)程中，根據(jù)判斷是否滿足約定的條件而決定是否需要轉(zhuǎn)否滿足約定的條件而決定是否需要轉(zhuǎn)換到何處去。需要計(jì)算機(jī)按條件進(jìn)行換到何處去。需要計(jì)算機(jī)按條件進(jìn)行分析、比較、判斷，并按判斷后的不分析、比較、判斷，并按判斷后的不同情況進(jìn)行不同的處理。同情況進(jìn)行不同的處理。a491、編寫一個(gè)程序，求任意實(shí)數(shù)的絕對(duì)值。、編寫一個(gè)程序，求任意實(shí)數(shù)的絕對(duì)值。INPUT

30、 “x=”；xIF x0 THEN y=-xELSEy=xEND IFPRINT “x=”；yEND程序如下：程序如下：程序框圖：程序框圖：開始開始輸入輸入 xy=-xy=x輸出輸出 y結(jié)束結(jié)束x0時(shí)時(shí),一元二次方程有兩個(gè)不等的實(shí)數(shù)根一元二次方程有兩個(gè)不等的實(shí)數(shù)根.(2)當(dāng)當(dāng)=0時(shí)時(shí),一元二次方程有兩個(gè)相等的實(shí)數(shù)根一元二次方程有兩個(gè)相等的實(shí)數(shù)根.122bxxa (3)當(dāng)當(dāng)=0 THEN p=-b/(2*a) q=SQR(d)/(2*a)IF d=0 THEN PRINT “One real root:；pELSE x1=p+q x2=p-q PRINT “Two real roots:“；x1

31、,x2 END IFELSE PRINT “No real root!END IFENDa52例例7 7：編寫程序，使得任意輸入的：編寫程序，使得任意輸入的3 3個(gè)整個(gè)整數(shù)按從大到小的順序輸出。數(shù)按從大到小的順序輸出。算法分析：用算法分析：用a a，b b，c c表示輸入的表示輸入的3 3個(gè)整數(shù)；為個(gè)整數(shù)；為了節(jié)約變量，把它們重新排列后，仍用了節(jié)約變量，把它們重新排列后，仍用a a，b b，c c表示，表示，并使并使abc.abc.具體操作步驟如下。具體操作步驟如下。第一步：輸入第一步：輸入3 3個(gè)整數(shù)個(gè)整數(shù)a a，b b，c.c.第二步：將第二步：將a a與與b b比較，并把小者賦給比較，并

32、把小者賦給b b，大者，大者賦給賦給a.a.第三步：將第三步：將a a與與c c比較比較. . 并把小者賦給并把小者賦給c c，大者，大者賦給賦給a a，此時(shí)，此時(shí)a a已是三者中最大的。已是三者中最大的。第四步：將第四步：將b b與與c c比較，并把小者賦給比較，并把小者賦給c c，大者，大者賦給賦給b b，此時(shí)，此時(shí)a a，b b，c c已按從大到小的順序排列好。已按從大到小的順序排列好。第五步：按順序輸出第五步：按順序輸出a a，b b，c.c.a53【程序程序】INPUT “a，b，c =;a，b，cIF ba THEN t=a a=b b=tEND IFIF ca THEN t=a

33、a=c c=tEND IFIF cb THEN t=b b=c c=tEND IF END IF PRINT a，b，cENDENDa54算法中的循環(huán)結(jié)構(gòu)是由循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)的算法中的循環(huán)結(jié)構(gòu)是由循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)的 . .循環(huán)結(jié)構(gòu)有兩種循環(huán)結(jié)構(gòu)有兩種-當(dāng)型與直到型當(dāng)型與直到型.滿足條件？滿足條件？循環(huán)體循環(huán)體是是否否當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)(當(dāng)條件滿當(dāng)條件滿足時(shí)反復(fù)執(zhí)行循環(huán)體足時(shí)反復(fù)執(zhí)行循環(huán)體)直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)(反復(fù)執(zhí)反復(fù)執(zhí)行循環(huán)體直到條件滿足行循環(huán)體直到條件滿足)循環(huán)體循環(huán)體是是否否滿足條件？滿足條件？對(duì)應(yīng)于程序框圖中的兩種循環(huán)結(jié)構(gòu)，一般對(duì)應(yīng)于程序框圖中的兩種循環(huán)結(jié)構(gòu)，一般程序設(shè)計(jì)語(yǔ)

34、言中也有當(dāng)型程序設(shè)計(jì)語(yǔ)言中也有當(dāng)型WHILEWHILE型和直到型型和直到型UNTILUNTIL型兩種語(yǔ)句結(jié)構(gòu)。型兩種語(yǔ)句結(jié)構(gòu)。 a55即即WHILEWHILE語(yǔ)句和語(yǔ)句和UNTILUNTIL語(yǔ)句。語(yǔ)句。 (1)WHILE(1)WHILE語(yǔ)句的一般格式是語(yǔ)句的一般格式是: :WHILE WHILE 條件條件 循環(huán)體循環(huán)體WENDWEND其中循環(huán)體是由計(jì)算機(jī)反復(fù)執(zhí)行的一組語(yǔ)句其中循環(huán)體是由計(jì)算機(jī)反復(fù)執(zhí)行的一組語(yǔ)句構(gòu)成的。構(gòu)成的。WHLIEWHLIE后面的后面的“條件是用于控制計(jì)算機(jī)條件是用于控制計(jì)算機(jī)執(zhí)行循環(huán)體或跳出循環(huán)體的。執(zhí)行循環(huán)體或跳出循環(huán)體的。WHILEWHILE當(dāng)當(dāng) 時(shí)候時(shí)候WENDWE

35、ND朝朝方向方向 行走行走a56(1)WHILE(1)WHILE語(yǔ)句的一般格式是語(yǔ)句的一般格式是 WHILE 條件條件 循環(huán)體循環(huán)體WEND 當(dāng)計(jì)算機(jī)遇到當(dāng)計(jì)算機(jī)遇到WHILEWHILE語(yǔ)句時(shí)語(yǔ)句時(shí), ,先判斷條件的真假先判斷條件的真假, ,如果條件如果條件符合符合, ,就執(zhí)行就執(zhí)行WHILEWHILE與與WENDWEND之間之間的循環(huán)體的循環(huán)體; ;然后再檢查上述條然后再檢查上述條件件, ,如果條件仍符合如果條件仍符合, ,再次執(zhí)行再次執(zhí)行循環(huán)體循環(huán)體, ,這個(gè)過(guò)程反復(fù)進(jìn)行這個(gè)過(guò)程反復(fù)進(jìn)行, ,直直到某一次條件不符合為止到某一次條件不符合為止. .這這時(shí)時(shí), ,計(jì)算機(jī)將不執(zhí)行循環(huán)體計(jì)算機(jī)將不

36、執(zhí)行循環(huán)體, ,直直接跳到接跳到WENDWEND語(yǔ)句后語(yǔ)句后, ,接著執(zhí)行接著執(zhí)行WENDWEND之后的語(yǔ)句之后的語(yǔ)句. . 滿足條件？滿足條件？循環(huán)體循環(huán)體是是否否當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)a57(2)UNTIL(2)UNTIL語(yǔ)句的一般格式是語(yǔ)句的一般格式是: :DODO 循環(huán)體循環(huán)體LOOP UNTIL LOOP UNTIL 條件條件循環(huán)體循環(huán)體是是否否滿足條件？滿足條件？直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)DODO做什么做什么LOOP UNTILLOOP UNTIL繞環(huán)回線走繞環(huán)回線走, ,直到到達(dá)某種直到到達(dá)某種 條件為止條件為止思考思考: :參照其直到型循環(huán)結(jié)構(gòu)對(duì)應(yīng)的程序框圖參照其直到型循環(huán)

37、結(jié)構(gòu)對(duì)應(yīng)的程序框圖, ,說(shuō)說(shuō)說(shuō)說(shuō)計(jì)算機(jī)是按怎樣的順序執(zhí)行計(jì)算機(jī)是按怎樣的順序執(zhí)行UNTILUNTIL語(yǔ)句的？語(yǔ)句的？ a58(2)UNTIL(2)UNTIL語(yǔ)句的一般格式是語(yǔ)句的一般格式是: :DODO 循環(huán)體循環(huán)體LOOP UNTIL LOOP UNTIL 條件條件循環(huán)體循環(huán)體是是否否滿足條件？滿足條件？直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)從從UNTILUNTIL型循環(huán)結(jié)構(gòu)分析型循環(huán)結(jié)構(gòu)分析, ,計(jì)算機(jī)執(zhí)行該語(yǔ)句時(shí)計(jì)算機(jī)執(zhí)行該語(yǔ)句時(shí), ,先先執(zhí)行一次循環(huán)體執(zhí)行一次循環(huán)體, ,然后進(jìn)行條件的判斷然后進(jìn)行條件的判斷, ,如果條件不如果條件不滿足滿足, ,繼續(xù)返回執(zhí)行循環(huán)體繼續(xù)返回執(zhí)行循環(huán)體, ,然后再進(jìn)

38、行條件的判斷然后再進(jìn)行條件的判斷, ,這個(gè)過(guò)程反復(fù)進(jìn)行這個(gè)過(guò)程反復(fù)進(jìn)行, ,直到某一次條件滿足時(shí)直到某一次條件滿足時(shí), ,不再執(zhí)不再執(zhí)行循環(huán)體行循環(huán)體, ,跳到跳到LOOP UNTILLOOP UNTIL語(yǔ)句后執(zhí)行其他語(yǔ)句語(yǔ)句后執(zhí)行其他語(yǔ)句, ,是先執(zhí)行循環(huán)體后進(jìn)行條件判斷的循環(huán)語(yǔ)句是先執(zhí)行循環(huán)體后進(jìn)行條件判斷的循環(huán)語(yǔ)句. .a59提問(wèn)提問(wèn): :通過(guò)對(duì)照通過(guò)對(duì)照, ,大家覺(jué)得大家覺(jué)得WHILEWHILE型語(yǔ)句與型語(yǔ)句與UNTILUNTIL型型語(yǔ)句之間有什么區(qū)別呢？語(yǔ)句之間有什么區(qū)別呢？ 區(qū)別區(qū)別：在：在WHILEWHILE語(yǔ)句中語(yǔ)句中, ,是當(dāng)條件是當(dāng)條件滿足滿足時(shí)執(zhí)行循環(huán)時(shí)執(zhí)行循環(huán)體體, ,

39、而在而在UNTILUNTIL語(yǔ)句中語(yǔ)句中, ,是當(dāng)條件是當(dāng)條件不滿足不滿足時(shí)執(zhí)行循環(huán)時(shí)執(zhí)行循環(huán)體。體。WHILEWHILE語(yǔ)句的一般格式語(yǔ)句的一般格式WHILE WHILE 條件條件 循環(huán)體循環(huán)體WENDWENDUNTILUNTIL語(yǔ)句的一般格式語(yǔ)句的一般格式DODO 循環(huán)體循環(huán)體LOOP UNTIL LOOP UNTIL 條件條件a60例例1.1.編寫程序編寫程序, ,計(jì)算自然數(shù)計(jì)算自然數(shù)1+2+3+1+2+3+99+100+99+100的和的和. .分析分析: :這是一個(gè)累加問(wèn)題這是一個(gè)累加問(wèn)題. .我們可我們可以用以用WHILEWHILE型語(yǔ)句型語(yǔ)句, ,也可以用也可以用UNTILUNT

40、IL型語(yǔ)型語(yǔ)句。句。a61WHILEWHILE語(yǔ)句語(yǔ)句開始開始結(jié)束結(jié)束i=1S=0i=i+1S=S+i輸出輸出Si100?是是否否當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)i=1S=0WHLIE i100?否否是是直到型直到型i=1S=0DOS=S+ii=i+1LOOP UNTIL i100PRINT SENDa63開始開始i=1S=0i100?是是S=S+ii=i+1否否輸出輸出S結(jié)束結(jié)束當(dāng)型循環(huán)當(dāng)型循環(huán)結(jié)構(gòu)結(jié)構(gòu)變式訓(xùn)練變式訓(xùn)練(1):(1):編寫程序求編寫程序求:n!=1:n!=12 23 34 45 5n n的值的值. .如何修改如何修改? ?輸入輸入nWHILEWHILE語(yǔ)句語(yǔ)句i=1S=0WHLIE

41、i100PRINT SENDS=1101S=Sii=i+2是是開始開始結(jié)束結(jié)束i=1S=0i=i+1S=S+i輸出輸出Si100?否否直到型直到型S=1S=Si i=i+2i101?a65算法案例算法案例a66輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法更相減損術(shù)更相減損術(shù)a671、求兩個(gè)正整數(shù)的最大公約數(shù)、求兩個(gè)正整數(shù)的最大公約數(shù)1求求25和和35的最大公約數(shù)的最大公約數(shù)2求求225和和135的最大公約數(shù)的最大公約數(shù)2、求、求8251和和6105的最大公約數(shù)的最大公約數(shù) 25（1） 55357所以，所以，25和和35的最大公約數(shù)為的最大公約數(shù)為5所以，所以，225和和135的最大公約數(shù)為的最大公約數(shù)為533=45課

42、前復(fù)習(xí)225（2） 545135273159知識(shí)回憶：先用知識(shí)回憶：先用兩個(gè)數(shù)公有的質(zhì)兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，因數(shù)連續(xù)去除，一直除到所得的一直除到所得的商是互質(zhì)數(shù)為止，商是互質(zhì)數(shù)為止，然后把所有的除然后把所有的除數(shù)連乘起來(lái)數(shù)連乘起來(lái)335a68輾轉(zhuǎn)相除法歐幾里得算法輾轉(zhuǎn)相除法歐幾里得算法觀察用輾轉(zhuǎn)相除法求觀察用輾轉(zhuǎn)相除法求8251和和6105的最大公約數(shù)的過(guò)程的最大公約數(shù)的過(guò)程 第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商商和和余數(shù)余數(shù)8251=61051+2146結(jié)論：結(jié)論： 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù)

43、，求的公約數(shù)，求8251和和6105的最大公約數(shù)，只要求出的最大公約數(shù)，只要求出6105和和2146的公約數(shù)的公約數(shù)就可以了。就可以了。第二步第二步 對(duì)對(duì)6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大的最大公約數(shù)。公約數(shù)。 a69完整的過(guò)程完整的過(guò)程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求225和和135的最大公約數(shù)的最大

44、公約數(shù)225=1351+90135=901+4590=452顯然顯然37是是148和和37的最大公約的最大公約數(shù)，也就是數(shù)，也就是8251和和6105的最的最大公約數(shù)大公約數(shù) 顯然顯然45是是90和和45的最大公約數(shù)，也就是的最大公約數(shù)，也就是225和和135的最大公約數(shù)的最大公約數(shù) 思考思考1：從上面的兩個(gè)例子可以看出計(jì)：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)：重復(fù)S1，直到余數(shù)為，直到余數(shù)為0a70 第一步第一步, ,給定兩個(gè)正數(shù)給定兩個(gè)正數(shù)m m、n n 第

45、二步第二步, ,計(jì)算計(jì)算m m除以除以n n所得到余數(shù)所得到余數(shù)r r 第三步第三步,m=n,m=n；n=rn=r 第四步第四步, ,假設(shè)假設(shè)r=0,r=0,那么那么m m、n n的最大公約數(shù)等的最大公約數(shù)等于于m;m; 否那么返回第二步否那么返回第二步輾轉(zhuǎn)相除法求最大公約數(shù)算法：輾轉(zhuǎn)相除法求最大公約數(shù)算法： 輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0 0停止停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。a71否否開始開始 輸入兩個(gè)正數(shù)輸入兩個(gè)正數(shù)m,nmn?r=m MOD nr0?輸出輸出n結(jié)束結(jié)束m=xm=nn=r否否是是是是INPUT

46、 m,nIF mn THEN x=n n=m m=xEND IFr=m MOD nWHILE r0 m=nn=rr=m MOD n WENDPRINT nENDx=nn=ma72更相減損術(shù)更相減損術(shù)算理算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。假設(shè)是，那么用偶數(shù)。假設(shè)是，那么用2 2約簡(jiǎn)；假設(shè)不是，那么執(zhí)行約簡(jiǎn)；假設(shè)不是，那么執(zhí)行第二步。第二步。第二步：以較大的數(shù)減較小的數(shù)，

47、接著把所得的差與第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，那么這個(gè)等數(shù)或這個(gè)等到所得的減數(shù)和差相等為止，那么這個(gè)等數(shù)或這個(gè)等數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)。數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)。a73例例1 1、用更相減損術(shù)求、用更相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù). .解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，減小數(shù)，并輾轉(zhuǎn)相減， 即：即：986335; 633528; 35287;

48、28721; 21714; 1477.所以，所以，9898與與6363的最大公約數(shù)是的最大公約數(shù)是7 7。a74二者算理相似，有異曲同工之妙二者算理相似，有異曲同工之妙1 1、都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除、都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。顯。2 2、從結(jié)果表達(dá)形式來(lái)看，輾轉(zhuǎn)相除法表達(dá)結(jié)果、從結(jié)果表達(dá)形式來(lái)看，輾轉(zhuǎn)相除法表達(dá)結(jié)果是以相除余數(shù)

49、為是以相除余數(shù)為0 0那么得到，而更相減損術(shù)那么那么得到，而更相減損術(shù)那么以減數(shù)與差相等而得到差為以減數(shù)與差相等而得到差為0 0輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別a75秦九韶算法秦九韶算法a76問(wèn)題問(wèn)題1設(shè)計(jì)求多項(xiàng)式設(shè)計(jì)求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時(shí)的值的算法時(shí)的值的算法,并寫出程序并寫出程序.x=5f=2*x5-5*x4-4*x3+3*x2-6*x+7PRINT fEND程序程序點(diǎn)評(píng)點(diǎn)評(píng):上述算法一共做了上述算法一共做了15次乘法運(yùn)算次乘法運(yùn)算,5次加法運(yùn)算次加法運(yùn)算.優(yōu)優(yōu)點(diǎn)是簡(jiǎn)單點(diǎn)是簡(jiǎn)單,易懂易懂;缺點(diǎn)是不通用缺點(diǎn)是不通用,不能

50、解決任意多項(xiàng)多求值不能解決任意多項(xiàng)多求值問(wèn)題問(wèn)題,而且計(jì)算效率不高而且計(jì)算效率不高.a77 這析計(jì)算上述多項(xiàng)式的值這析計(jì)算上述多項(xiàng)式的值,一共需要一共需要9次乘次乘法運(yùn)算法運(yùn)算,5次加法運(yùn)算次加法運(yùn)算.問(wèn)題問(wèn)題2有沒(méi)有更高效的算法有沒(méi)有更高效的算法?分析分析:計(jì)算計(jì)算x的冪時(shí)的冪時(shí),可以利用前面的計(jì)算結(jié)可以利用前面的計(jì)算結(jié)果果,以減少計(jì)算量以減少計(jì)算量,即先計(jì)算即先計(jì)算x2,然后依次計(jì)算然后依次計(jì)算222,(),()xx xxxxxxx的值的值.第二種做法與第一種做法相比第二種做法與第一種做法相比,乘法的運(yùn)算次數(shù)乘法的運(yùn)算次數(shù)減少了減少了,因而能提高運(yùn)算效率因而能提高運(yùn)算效率.而且對(duì)于計(jì)算機(jī)來(lái)

51、說(shuō)而且對(duì)于計(jì)算機(jī)來(lái)說(shuō),做做一次乘法所需的運(yùn)算時(shí)間比做一次加法要長(zhǎng)得多一次乘法所需的運(yùn)算時(shí)間比做一次加法要長(zhǎng)得多,因此因此第二種做法能更快地得到結(jié)果第二種做法能更快地得到結(jié)果.a78問(wèn)題問(wèn)題3能否探索更好的算法能否探索更好的算法,來(lái)解決任意多來(lái)解決任意多項(xiàng)式的求值問(wèn)題項(xiàng)式的求值問(wèn)題?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+7v0=2v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=2

52、15+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677這種求多項(xiàng)式值的方法就叫這種求多項(xiàng)式值的方法就叫秦九韶算法秦九韶算法.a79f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我們可以改寫成如下形式我們可以改寫成如下形式:求多項(xiàng)式的值時(shí)求多項(xiàng)式的值時(shí),首先計(jì)算最內(nèi)層括號(hào)內(nèi)一首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值次多項(xiàng)式的值,即即 v1=anx+an-1,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即即一般地一般地,對(duì)于一個(gè)對(duì)于一個(gè)n次多項(xiàng)式次多項(xiàng)式v2=v1x+an-2, v3=v2x+an-3, ,vn=v

53、n-1x+a0.這樣這樣,求求n次多項(xiàng)式次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n個(gè)個(gè)一次多項(xiàng)式的值一次多項(xiàng)式的值.這種算法稱為這種算法稱為秦九韶算法秦九韶算法.f(x)=(anx+an-1)x+an-2)x+a1)x+a0.秦九韶算法秦九韶算法a80點(diǎn)評(píng)點(diǎn)評(píng):秦九韶算法是求一元多項(xiàng)式的秦九韶算法是求一元多項(xiàng)式的值的一種方法值的一種方法.它的特點(diǎn)是它的特點(diǎn)是:把求一個(gè)把求一個(gè)n次多項(xiàng)式的值次多項(xiàng)式的值轉(zhuǎn)化為求轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值個(gè)一次多項(xiàng)式的值,通過(guò)這種轉(zhuǎn)通過(guò)這種轉(zhuǎn)化化,把運(yùn)算的次數(shù)由至多把運(yùn)算的次數(shù)由至多n(n+1)/2次乘法運(yùn)次乘法運(yùn)算和算和n次加法運(yùn)算次加法運(yùn)算,減少為減少為n

54、次乘法運(yùn)算和次乘法運(yùn)算和n次加法運(yùn)算次加法運(yùn)算,大大提高了運(yùn)算效率大大提高了運(yùn)算效率.a81v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.觀察上述秦九韶算法中的觀察上述秦九韶算法中的n個(gè)一次式個(gè)一次式,可見可見vk的計(jì)算要用到的計(jì)算要用到vk-1的值的值. 假設(shè)令假設(shè)令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n)這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟驟,因此可用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)因此可用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn).a82問(wèn)題問(wèn)題畫出程序框圖畫出程序框圖,表示用秦九韶算法求表示用秦九韶算法求5次多項(xiàng)

55、次多項(xiàng)式式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0當(dāng)當(dāng)x=x0 (x0是是任意實(shí)數(shù)任意實(shí)數(shù))時(shí)的值的過(guò)程時(shí)的值的過(guò)程,然后寫出程序然后寫出程序.算法步驟如下：算法步驟如下：第一步，輸入多項(xiàng)式次數(shù)第一步，輸入多項(xiàng)式次數(shù)n n、最高次項(xiàng)的系數(shù)、最高次項(xiàng)的系數(shù)anan和和x x的值的值. .第二步，將第二步，將v v的值初始化為的值初始化為anan，將，將i i的值初始化為的值初始化為n-1.n-1.第三步，輸入第三步，輸入i i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)ai.ai.第四步，第四步，v=vx+aiv=vx+ai，i=i-1.i=i-1.第五步，判斷第五步，判斷i i是否大于或等于是否

56、大于或等于0 0，假設(shè)是，那么返回第三，假設(shè)是，那么返回第三步；否那么，輸出多項(xiàng)式的值步；否那么，輸出多項(xiàng)式的值v.v.a83否否程序框圖程序框圖開始開始輸入輸入n,an,x的值的值i0?i=n-1v=anv=vx+aii=i-1輸出輸出v結(jié)束結(jié)束是是INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i=0 PRINT “i=”; IINPUT “ai=”; a v=v*x+a i=i-1WENDPRINT vEND輸入輸入aia84進(jìn)位制進(jìn)位制a85 問(wèn)題問(wèn)題11我們常見的數(shù)字都是十進(jìn)制的我們常見的數(shù)字都是十進(jìn)制的, ,但是并不是生但是并不

57、是生活中的每一種數(shù)字都是十進(jìn)制的活中的每一種數(shù)字都是十進(jìn)制的. .比方時(shí)間和角度的比方時(shí)間和角度的單位用六十進(jìn)位制單位用六十進(jìn)位制, ,電子計(jì)算機(jī)用的是二進(jìn)制電子計(jì)算機(jī)用的是二進(jìn)制. .那么什那么什么是進(jìn)位制么是進(jìn)位制? ?不同的進(jìn)位制之間又有什么聯(lián)系呢不同的進(jìn)位制之間又有什么聯(lián)系呢? ?進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算的方便而約定的一種進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算的方便而約定的一種記數(shù)系統(tǒng)，約定滿二進(jìn)一記數(shù)系統(tǒng)，約定滿二進(jìn)一, ,就是二進(jìn)制就是二進(jìn)制; ;滿十進(jìn)一滿十進(jìn)一, ,就就是十進(jìn)制是十進(jìn)制; ;滿十六進(jìn)一滿十六進(jìn)一, ,就是十六進(jìn)制就是十六進(jìn)制; ;等等等等. . “滿幾進(jìn)一滿幾進(jìn)一,就是幾

58、進(jìn)制就是幾進(jìn)制,幾進(jìn)制的基數(shù)就是幾幾進(jìn)制的基數(shù)就是幾.可使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)可使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù). .基數(shù)基數(shù)都是大于都是大于1 1的整數(shù)的整數(shù). . a86例如：二進(jìn)制可使用的數(shù)字有例如：二進(jìn)制可使用的數(shù)字有0和和1,基數(shù)是基數(shù)是2; 十進(jìn)制可使用的數(shù)字有十進(jìn)制可使用的數(shù)字有0,1,2,8,9等十個(gè)數(shù)字等十個(gè)數(shù)字,基基數(shù)是數(shù)是10; 十六進(jìn)制可使用的數(shù)字或符號(hào)有十六進(jìn)制可使用的數(shù)字或符號(hào)有09等等10個(gè)數(shù)字個(gè)數(shù)字以及以及AF等等6個(gè)字母?jìng)€(gè)字母(規(guī)定字母規(guī)定字母AF對(duì)應(yīng)對(duì)應(yīng)1015),十六進(jìn)十六進(jìn)制的基數(shù)是制的基數(shù)是16.注意注意: :為了區(qū)分不同的進(jìn)位制為了區(qū)分不同的進(jìn)位制, ,常在數(shù)字的右下常在數(shù)字的右下腳標(biāo)明基數(shù)腳標(biāo)明基數(shù),. ,. 如如111001111001(2)(2)表示二進(jìn)制數(shù)表示二進(jìn)制數(shù),34,34(5)(5)表示表示5 5進(jìn)制數(shù)進(jìn)制數(shù). .十進(jìn)制數(shù)一般不標(biāo)注基數(shù)十進(jìn)制數(shù)一般不標(biāo)注基數(shù).a87問(wèn)題問(wèn)題2十進(jìn)制數(shù)十進(jìn)制數(shù)3721中的中的3表示表示3個(gè)千個(gè)千,7表示表示7個(gè)百個(gè)百,2表示表示2個(gè)十個(gè)十,1表示表示1個(gè)一個(gè)一,從而它可以寫成下面的形式從而它可以寫成下面的形式:3721=3103+7102+2101+