算法初步小結(jié)與復(fù)習(xí)(絕對(duì)精品)完整版

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

2、將將 代入代入, ,得得 6 7 y 寫一寫寫一寫 解方程組解方程組 323 24 xy x y 寫出寫出的步驟的步驟 寫出解第二個(gè)方程組的算法：寫出解第二個(gè)方程組的算法： 第一步第一步, , 第二步第二步, , 第三步第三步, , 2 11 22 11 2 ()a ba bya ca c 解，得 2 11 2 2 11 2 a ca c y a ba b 將代入得 2 a 1 a 得 323 24 xy x y 1 22 1 2 11 2 bcb c x a bab 變一變變一變 111 222 a x b y c a x b y c 1 22 1 (0)a ba b 在數(shù)學(xué)上，通常是按照一

3、定規(guī)則在數(shù)學(xué)上，通常是按照一定規(guī)則 解決某一類問題的明確有限的步驟解決某一類問題的明確有限的步驟。 算法的定義： 例例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.因此,

4、7是質(zhì)數(shù). (2)設(shè)計(jì)一個(gè)算法設(shè)計(jì)一個(gè)算法,判斷判斷35是否為質(zhì)數(shù)是否為質(zhì)數(shù). 算法: 第一步第一步, ,用2除35,得到余數(shù)1.因?yàn)橛鄶?shù)不為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ù). 探究 你能寫出”判斷整數(shù)n(n2) 是否為質(zhì)數(shù)”的算法嗎? 第一步第一步, ,給定大于2的整數(shù)n. 第二步第二步, ,令i=2. 第三步第三步, , 用i除n,得到

5、余數(shù)r. 第四步第四步, ,判斷”r=0”是否成立.若是,則n不是質(zhì)數(shù), 結(jié)束算法;否則,將i的值增加1,仍用i表示. 第五步第五步, , 判斷”i(n-1)”是否成立.若是,則n是質(zhì)數(shù), 結(jié)束算法;否則,返回第三步. 算法的基本特點(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、邏輯性、邏輯

6、性 算法中從開始的算法中從開始的“第一步第一步”到到“最后一步最后一步”之間之間 做到做到 環(huán)環(huán)相扣，分工明確，環(huán)環(huán)相扣，分工明確，“前一步前一步”是是“后一步后一步” 的前提，的前提，“后一步后一步”是是“前一步前一步”的繼續(xù)。的繼續(xù)。 算法算法1 1： 第二步第二步：計(jì)算：計(jì)算1011015050； 第三步第三步：寫出運(yùn)算結(jié)果：寫出運(yùn)算結(jié)果 算法算法2 2：第一步第一步：?。喝=100n=100； 第二步第二步：計(jì)算：計(jì)算 (1) 2 n n 第三步第三步：寫出運(yùn)算結(jié)果：寫出運(yùn)算結(jié)果 寫出求寫出求1+2+3+ +1001+2+3+ +100的一個(gè)算法的一個(gè)算法 (1+100)+(2+99

7、)+ +(50+51)(1+100)+(2+99)+ +(50+51)； 第一步第一步：將原式變形為：將原式變形為 你會(huì)了嗎？你會(huì)了嗎？ 2.2.任意給定一個(gè)正實(shí)數(shù)任意給定一個(gè)正實(shí)數(shù), ,設(shè)計(jì)一個(gè)算法求以這個(gè)設(shè)計(jì)一個(gè)算法求以這個(gè) 數(shù)為半徑的圓的面積數(shù)為半徑的圓的面積. . 第一步第一步:輸入任意一個(gè)正實(shí)數(shù)輸入任意一個(gè)正實(shí)數(shù)r0； 第二步第二步:計(jì)算圓的面積計(jì)算圓的面積: S=r2; 第三步第三步:輸出圓的面積輸出圓的面積S. 程序框圖程序框圖 程序框圖又稱流程圖，是一種用程程序框圖又稱流程圖，是一種用程 序框、流程線及文字說明來表示算法序框、流程線及文字說明來表示算法 的圖形。的圖形。 在程序

8、框圖中，一個(gè)或幾個(gè)程序框的組合表示算在程序框圖中，一個(gè)或幾個(gè)程序框的組合表示算 法中的一個(gè)步驟；帶有方向箭頭的流程線將程序框法中的一個(gè)步驟；帶有方向箭頭的流程線將程序框 連接起來，表示算法步驟的執(zhí)行順序。連接起來，表示算法步驟的執(zhí)行順序。 圖形符號(hào)圖形符號(hào)名稱名稱功能功能 終端框（起止終端框（起止 框）框） 表示一個(gè)算法的起始和結(jié)束表示一個(gè)算法的起始和結(jié)束 輸入、輸出框輸入、輸出框 表示一個(gè)算法輸入和輸出的信息表示一個(gè)算法輸入和輸出的信息 處理框處理框 賦值、計(jì)算賦值、計(jì)算 判斷框判斷框 判斷某一條件是否成立，成立時(shí)在判斷某一條件是否成立，成立時(shí)在 出口處標(biāo)明出口處標(biāo)明“是是”或或“Y”；不成

9、立時(shí)；不成立時(shí) 標(biāo)明標(biāo)明“否否”或或“N”。 流程線流程線 連接程序框連接程序框 連接點(diǎn)連接點(diǎn) 連接程序框圖的兩部分連接程序框圖的兩部分 例例 用程序框圖表示用程序框圖表示“判判 斷整數(shù)斷整數(shù)n n（n2n2）是否為質(zhì)）是否為質(zhì) 數(shù)數(shù)”的算法的算法 開始開始 輸入輸入n i=2 求求n除以除以i的余數(shù)的余數(shù)r i的值增加的值增加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 說明說明:i表示從表示從2(

10、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ù)存在. （1 1）使用標(biāo)準(zhǔn)的圖形符號(hào)。）使用標(biāo)準(zhǔn)的圖形符號(hào)。 （2 2）框圖一般按從上到下，從左到右的方向畫。）框圖一般按從上到下，從左到右的方向畫。 （3 3）除判斷框外，大多數(shù)流程圖符號(hào)只有一個(gè)）除判斷框外，大多數(shù)流程圖符號(hào)只有一個(gè) 進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框具有超過一個(gè)退出進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框具有超過一個(gè)

11、退出 點(diǎn)的唯一符號(hào)。點(diǎn)的唯一符號(hào)。 （4 4）判斷框分兩大類，一類判斷框）判斷框分兩大類，一類判斷框“是是”與與“否否” 兩分支的判斷，而且又且僅有兩個(gè)結(jié)果；另一類是兩分支的判斷，而且又且僅有兩個(gè)結(jié)果；另一類是 多分支判斷，有幾種不同的結(jié)果。多分支判斷，有幾種不同的結(jié)果。 （5 5）在圖形符號(hào)內(nèi)描述的語言要非常簡(jiǎn)練清楚。）在圖形符號(hào)內(nèi)描述的語言要非常簡(jiǎn)練清楚。 開始開始 輸入輸入n i=2 求求n除以除以i的余數(shù)的余數(shù)r i=i+1 in或或r=0? n不是質(zhì)數(shù)不是質(zhì)數(shù) 結(jié)束結(jié)束 是是 否否 是是 n是質(zhì)數(shù)是質(zhì)數(shù) 否否 r=0? 順序結(jié)構(gòu)順序結(jié)構(gòu) 用程序框圖來表示算法，有用程序框圖來表示算法，

12、有 三種不同的基本邏輯結(jié)構(gòu)：三種不同的基本邏輯結(jié)構(gòu)： 條件結(jié)構(gòu)條件結(jié)構(gòu) 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 三種基本結(jié)構(gòu)（三種基本結(jié)構(gòu)（表示一個(gè)良好算法的基本單元） 順序結(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) A B P AB 成立成立不成立不成立 成立成立 A P 不成立不成立 A P 成立成立 不成立不成立 While（當(dāng)型）循環(huán)）循環(huán) Until（直到型）循環(huán)）循環(huán) 順序結(jié)構(gòu)順序結(jié)構(gòu) 順序結(jié)構(gòu)是由若干個(gè)依次執(zhí)行的步驟組順序結(jié)構(gòu)是由若干個(gè)依次執(zhí)行的步驟組 成的。這是任何一個(gè)算法都離不開的基本結(jié)成的。這是任何一個(gè)算法都離不開的基本結(jié) 構(gòu)構(gòu) A B 例1 已知一個(gè)三角形的三邊邊長(zhǎng)分別為a

13、、b、c，利用 海倫-秦九韶公式設(shè)計(jì)一個(gè)算法，求出它的面積，畫出 它的程序框圖. 第一步：輸入三角形三條邊的邊長(zhǎng) a，b，c； 第二步：計(jì)算 ； 第三步：計(jì)算 ； 第四步：輸出s。 ()/ 2pabc ()()()Sp papbpc 算法分析：算法分析： 開始 輸入a，b，c 輸出S 結(jié)束 () / 2pabc ()()()Sp papbpc 程序框圖程序框圖 習(xí)題1 設(shè)計(jì)一算法：輸入圓的半徑,輸出圓的面積，并畫出流程圖 算法分析： 第一步：輸入圓的半徑輸入圓的半徑 第二步：利用公式利用公式“圓的面圓的面 積積=圓周率圓周率（半徑的平方）（半徑的平方）” 計(jì)算圓的面積；計(jì)算圓的面積； 第三步：

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

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

16、的處某一處理步驟的情況，這就是循環(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)體的條件中。 例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=0 i=i+1 sum=sum+1 1.21.2 基本算法語句基本算法語

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

18、的輸入語句和輸出語句分別用來實(shí)現(xiàn)算法的 輸入信息，輸出結(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+30 PRINT x PRINT y END 程序程序: : -輸入語句輸入語句 -賦值語句賦值語句 -打印

19、語句打印語句 -打印語句打印語句 -表示結(jié)束表示結(jié)束 輸出語句輸出語句 輸出語句輸出語句 一一. .輸入語句輸入語句 INPUT INPUT “提示內(nèi)容提示內(nèi)容”；變量；變量 輸入語句的一般格式輸入語句的一般格式 說明說明: : (1)(1)輸入語句的作用是實(shí)現(xiàn)算法的輸入信息功能；輸入語句的作用是實(shí)現(xiàn)算法的輸入信息功能； (2)“(2)“提示內(nèi)容提示內(nèi)容”提示用戶輸入什么樣的信息，提示用戶輸入什么樣的信息， 變量是指程序在運(yùn)行時(shí)其值是可以變化的量；變量是指程序在運(yùn)行時(shí)其值是可以變化的量； (3)(3)輸入語句要求輸入的值輸入語句要求輸入的值只能是具體的常數(shù)只能是具體的常數(shù)， 不能是函數(shù)、變量或

20、表達(dá)式；不能是函數(shù)、變量或表達(dá)式； (4)(4)提示內(nèi)容與變量之間用分號(hào)提示內(nèi)容與變量之間用分號(hào)“；”隔開，隔開， 若輸入多個(gè)變量，變量與變量之間用逗號(hào)若輸入多個(gè)變量，變量與變量之間用逗號(hào)“，”隔開隔開. . 例如例如, ,輸入一個(gè)學(xué)生數(shù)學(xué)輸入一個(gè)學(xué)生數(shù)學(xué), ,語文語文, ,英語三門課的成績(jī)英語三門課的成績(jī), , 可以寫成：可以寫成： INPUT “數(shù)學(xué)，語文，英語數(shù)學(xué)，語文，英語”；a，b，c 注意注意: : INPUTINPUT語句不但可以給單個(gè)變量賦值語句不但可以給單個(gè)變量賦值, ,還可以還可以 給多個(gè)變量賦值給多個(gè)變量賦值, ,其格式為：其格式為： INPUT INPUT “提示內(nèi)容提

21、示內(nèi)容1 1，提示內(nèi)容，提示內(nèi)容2 2，提示內(nèi)容，提示內(nèi)容3 3，”；變量；變量1 1，變量，變量2 2，變量，變量3 3， 練一練練一練:請(qǐng)你用輸入語句表達(dá)課本請(qǐng)你用輸入語句表達(dá)課本P5和和P9 頁程序框圖中輸入框中的內(nèi)容頁程序框圖中輸入框中的內(nèi)容. P7頁頁: INPUT “n=”; n P9頁頁: INPUT a, b, c 二二. .輸出語句輸出語句 PRINT “提示內(nèi)容提示內(nèi)容”；表達(dá)式；表達(dá)式 說明說明: : (1)“(1)“提示內(nèi)容提示內(nèi)容”提示用戶輸出什么樣的信息提示用戶輸出什么樣的信息, ,表表 達(dá)式是指程序要輸出的數(shù)據(jù)；達(dá)式是指程序要輸出的數(shù)據(jù)； 輸出常量，變量的值和字符

22、串等系統(tǒng)信息。輸出常量，變量的值和字符串等系統(tǒng)信息。 輸出數(shù)值計(jì)算的結(jié)果。輸出數(shù)值計(jì)算的結(jié)果。 (2)(2)輸出語句的用途：輸出語句的用途： 輸出語句的一般格式輸出語句的一般格式 (3)同輸入語句一樣，表達(dá)式前也可以有同輸入語句一樣，表達(dá)式前也可以有“提示內(nèi)提示內(nèi) 容容”. 思考思考: :在課本在課本P7P7頁圖頁圖1.1-21.1-2程序框圖中的輸程序框圖中的輸 出框的內(nèi)容怎樣用輸出語句來表達(dá)？出框的內(nèi)容怎樣用輸出語句來表達(dá)？ 參考答案：參考答案： 輸出框：輸出框： PRINT “PRINT “n is a prime number .” .” PRINT “ PRINT “n is not

23、 a prime number.”.” 如如P9頁的輸出框頁的輸出框 可以轉(zhuǎn)化為輸出語句可以轉(zhuǎn)化為輸出語句: 輸出輸出S PRINT “S=”; S 三三. .賦值語句賦值語句 (1)賦值語句的一般格式賦值語句的一般格式: 變量表達(dá)式變量表達(dá)式 (2)(2)賦值語句的作用賦值語句的作用是是: :先計(jì)算出賦值號(hào)右邊表達(dá)先計(jì)算出賦值號(hào)右邊表達(dá) 式的值式的值, ,然后把這個(gè)值賦給左邊的變量然后把這個(gè)值賦給左邊的變量, ,使該變量的使該變量的 值等于表達(dá)式的值。值等于表達(dá)式的值。 (3)(3)賦值語句中的賦值語句中的“”稱作賦值號(hào)稱作賦值號(hào), ,與數(shù)學(xué)中的等與數(shù)學(xué)中的等 號(hào)的意義是不同的號(hào)的意義是不同

24、的. .賦值號(hào)的左右兩邊不能對(duì)換賦值號(hào)的左右兩邊不能對(duì)換. . (4)(4)賦值語句左邊只能是變量名字而不是表達(dá)式賦值語句左邊只能是變量名字而不是表達(dá)式, , 如如:2=x:2=x是錯(cuò)誤的是錯(cuò)誤的; ;右邊表達(dá)式可以是一個(gè)數(shù)據(jù)、右邊表達(dá)式可以是一個(gè)數(shù)據(jù)、 常量或算式；不能利用賦值語句進(jìn)行代數(shù)式的常量或算式；不能利用賦值語句進(jìn)行代數(shù)式的 演算。（如化簡(jiǎn)、因式分解、解方程等）演算。（如化簡(jiǎn)、因式分解、解方程等） （5 5）對(duì)于一個(gè)變量可以多次賦值。）對(duì)于一個(gè)變量可以多次賦值。 【例題解析例題解析】 例例2 2：編寫程序，計(jì)算一個(gè)學(xué)生數(shù)學(xué)、語文、：編寫程序，計(jì)算一個(gè)學(xué)生數(shù)學(xué)、語文、 英語三門課的平均

25、成績(jī)。英語三門課的平均成績(jī)。 分析分析：先寫出算法，畫出程序框圖，再進(jìn)行編程。：先寫出算法，畫出程序框圖，再進(jìn)行編程。 結(jié)束結(jié)束 開始開始 輸入輸入a,b,c 輸出輸出y 3 3 abc y 程序框圖程序框圖 INPUT “Maths,Chinese,English”；a,b,c y=(a+b+c)/3 PRINT “y=”；y END 程序程序: : 例例3 3：給一個(gè)變量重復(fù)賦值。：給一個(gè)變量重復(fù)賦值。 程序程序: : A=10 A=A+15 PRINT A END A的輸出的輸出 值是多少值是多少? 分析分析:此程序給變量此程序給變量A賦了兩次值賦了兩次值.A 的初值為的初值為10,第二

26、次賦值后第二次賦值后,初值被初值被“覆覆 蓋蓋”,A的值變?yōu)榈闹底優(yōu)?5,因此輸出值是因此輸出值是25. 變式引申變式引申 : :在此程序的基礎(chǔ)上，設(shè)計(jì)一個(gè)程序，在此程序的基礎(chǔ)上，設(shè)計(jì)一個(gè)程序， 要求最后要求最后A A的輸出值是的輸出值是30.30. A=10 A=A+15 PRINT A A=A+5 PRINT A END 程序程序: : 例例3 3：給一個(gè)變量重復(fù)賦值。：給一個(gè)變量重復(fù)賦值。 程序程序: :A=10 A=A+15 PRINT A END 例例4 4交換兩個(gè)變量交換兩個(gè)變量A A和和B B的值的值, ,并輸出交換前后并輸出交換前后 的值。的值。 分析：分析：引入一個(gè)引入一個(gè)中

27、間變量中間變量X X, ,將將A A的值賦予的值賦予X,X,又將又將B B 的值賦予的值賦予A A，再將，再將X X的值賦予的值賦予B B，從而達(dá)到交換，從而達(dá)到交換A A， B B的值的值. .（比如交換裝滿水的兩個(gè)水桶里的水需要（比如交換裝滿水的兩個(gè)水桶里的水需要 再找一個(gè)空桶）再找一個(gè)空桶） INPUT A INPUT B PRINT A，B X=A A=B B=X PRINT A，B END 程序程序: : 問題問題:能否用下列賦值能否用下列賦值 語句交換語句交換A,B的值的值? A=B B=A 不能不能! 練習(xí)練習(xí)1 1: :編寫一個(gè)程序編寫一個(gè)程序, ,要求輸入一個(gè)圓的半徑要求輸入

28、一個(gè)圓的半徑, , 便能輸出該圓的周長(zhǎng)和面積便能輸出該圓的周長(zhǎng)和面積. .（ 取取3.143.14） 分析分析: :設(shè)圓的半徑為設(shè)圓的半徑為R,R,則圓的周長(zhǎng)則圓的周長(zhǎng)C=2R,C=2R,面積面積 S=RS=R2 2, ,可以利用順序結(jié)構(gòu)中的可以利用順序結(jié)構(gòu)中的INPUTINPUT語句語句,PRINT,PRINT 語句和賦值語句設(shè)計(jì)程序。語句和賦值語句設(shè)計(jì)程序。 INPUT “R=”；R C=2*3.14*R S=3.14*R2 PRINT “ “C=”；C PRINT “ “S=S=”； S END 算法中的條件結(jié)構(gòu)是由條件語句來表達(dá)的算法中的條件結(jié)構(gòu)是由條件語句來表達(dá)的, , 條件語句是處

29、理?xiàng)l件分支邏輯結(jié)構(gòu)的算法語句條件語句是處理?xiàng)l件分支邏輯結(jié)構(gòu)的算法語句 . . 條件語句的一般格式條件語句的一般格式 滿足條件？滿足條件？ 語句語句 是是 否否 只含一個(gè)只含一個(gè)“分支分支”的條件結(jié)構(gòu)的條件結(jié)構(gòu)寫成條件語句為寫成條件語句為 IFIF 條件條件 THENTHEN 語句體語句體 END IFEND IF 當(dāng)計(jì)算機(jī)執(zhí)行這種形式的條件語句時(shí)，首先對(duì)當(dāng)計(jì)算機(jī)執(zhí)行這種形式的條件語句時(shí)，首先對(duì) IFIF后的條件進(jìn)行判斷，如果條件符合，就執(zhí)行后的條件進(jìn)行判斷，如果條件符合，就執(zhí)行 THENTHEN后的語句體，否則執(zhí)行后的語句體，否則執(zhí)行END IFEND IF之后的語句之后的語句. . 滿足條件

30、？滿足條件？ 語句語句1 1語句語句2 2 是是 否否 含兩個(gè)含兩個(gè)“分支分支”的條件結(jié)構(gòu)的條件結(jié)構(gòu) 寫成條件語句為寫成條件語句為 IFIF 條件條件 THENTHEN 語句體語句體1 1 ELSEELSE 語句體語句體2 2 END IFEND IF 當(dāng)計(jì)算機(jī)執(zhí)行上述語句時(shí)，首先對(duì)當(dāng)計(jì)算機(jī)執(zhí)行上述語句時(shí)，首先對(duì)IFIF后的后的 條件進(jìn)行判斷，如果條件符合，就執(zhí)行條件進(jìn)行判斷，如果條件符合，就執(zhí)行THENTHEN后后 的語句體的語句體1 1，否則執(zhí)行，否則執(zhí)行ELSEELSE后的語句體后的語句體2. 2. 條件語句的作用條件語句的作用 在程序執(zhí)行過程中，根據(jù)判斷在程序執(zhí)行過程中，根據(jù)判斷 是否

31、滿足約定的條件而決定是否需是否滿足約定的條件而決定是否需 要轉(zhuǎn)換到何處去。需要計(jì)算機(jī)按條要轉(zhuǎn)換到何處去。需要計(jì)算機(jī)按條 件進(jìn)行分析、比較、判斷，并按判件進(jìn)行分析、比較、判斷，并按判 斷后的不同情況進(jìn)行不同的處理。斷后的不同情況進(jìn)行不同的處理。 1、編寫一個(gè)程序，求任意實(shí)數(shù)的絕對(duì)值。、編寫一個(gè)程序，求任意實(shí)數(shù)的絕對(duì)值。 INPUT “x=”；x IF x0 THEN y=-x ELSE y=x END IF PRINT “x=”；y END 程序如下：程序如下：程序框圖：程序框圖： 開始開始 輸入輸入 x y=-x y=x 輸出輸出 y 結(jié)束結(jié)束 x0時(shí)時(shí),一元二次方程有兩個(gè)不等的實(shí)數(shù)根一元二次

32、方程有兩個(gè)不等的實(shí)數(shù)根. (2)當(dāng)當(dāng)=0時(shí)時(shí),一元二次方程有兩個(gè)相等的實(shí)數(shù)根一元二次方程有兩個(gè)相等的實(shí)數(shù)根. 12 2 b xx a (3)當(dāng)當(dāng)=0 THENIF d=0 THEN p=-b/(2*a) q=SQR(d)/(2*a) IF d=0 THEN PRINT “One real root:”；p ELSE x1=p+q x2=p-q PRINT “Two real roots:“；x1,x2 END IF ELSEELSE PRINT “No real root! !” END IF ENDEND 例例7 7：編寫程序，使得任意輸入的：編寫程序，使得任意輸入的3 3個(gè)整個(gè)整 數(shù)按從大

33、到小的順序輸出。數(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比較，并把小者賦給比較，并把小者賦給b b，大者，大者 賦給賦給a.a. 第三步：將第三步：將a a與與c c比較比較. . 并把小者賦給并把小者賦給c c，大者，大者 賦給賦給a a，此時(shí)，此

34、時(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. 【程序程序】 INPUT “a，b，c =”;a，b，c IF ba THEN t=a a=b b=t END IF IF ca THEN t=a a=c c=t END IF IF cb THEN t=b b=c c=t END IF END IF PRINT a，b，c ENDEND 算法中的

35、循環(huán)結(jié)構(gòu)是由循環(huán)語句來實(shí)現(xiàn)的算法中的循環(huán)結(jié)構(gòu)是由循環(huán)語句來實(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ì)語言中也有當(dāng)型（程序設(shè)計(jì)語言中也有當(dāng)型（WHILEWHILE型）和直到型型）和直到型 （UNTILUNTIL型）兩種語

36、句結(jié)構(gòu)。型）兩種語句結(jié)構(gòu)。 即即WHILEWHILE語句和語句和UNTILUNTIL語句。語句。 (1)WHILE(1)WHILE語句的一般格式是語句的一般格式是: : WHILE WHILE 條件條件 循環(huán)體循環(huán)體 WENDWEND 其中循環(huán)體是由計(jì)算機(jī)反復(fù)執(zhí)行的一組語句其中循環(huán)體是由計(jì)算機(jī)反復(fù)執(zhí)行的一組語句 構(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í)候 WENDWEND朝朝方向方向 行走行走 (1)WHILE(1)WHILE語句的一般格式是語句的一般格式

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

38、著執(zhí)行 WENDWEND之后的語句之后的語句. . 滿足條件？滿足條件？ 循環(huán)體循環(huán)體 是是 否否 當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu) (2)UNTIL(2)UNTIL語句的一般格式是語句的一般格式是: : 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)結(jié)構(gòu)對(duì)應(yīng)的程序框圖, ,說說說說 計(jì)算機(jī)是按怎樣的

39、順序執(zhí)行計(jì)算機(jī)是按怎樣的順序執(zhí)行UNTILUNTIL語句的？語句的？ (2)UNTIL(2)UNTIL語句的一般格式是語句的一般格式是: : 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í)行該語句時(shí)計(jì)算機(jī)執(zhí)行該語句時(shí), ,先先 執(zhí)行一次循環(huán)體執(zhí)行一次循環(huán)體, ,然后進(jìn)行條件的判斷然后進(jìn)行條件的判斷, ,如果條件不如果條件不 滿足滿足, ,繼續(xù)返回執(zhí)行循環(huán)體繼續(xù)返回執(zhí)行循環(huán)體, ,然后再進(jìn)行條件的判斷然后再進(jìn)行條件的判斷,

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

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

42、語型語 句。句。 WHILEWHILE語句語句 開始開始 結(jié)束結(jié)束 i=1 S=0 i=i+1 S=S+i 輸出輸出S i100? 是是 否否 當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu) i=1 S=0 WHLIE i100? 否否 是是 直到型直到型 i=1 S=0 DO S=S+i i=i+1 LOOP UNTIL i100 PRINT S END 開始開始 i=1 S=0 i100? 是是 S=S+i i=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的值的值. . 如何修改如何修改?

43、 ? 輸入輸入n WHILEWHILE語句語句 i=1 S=0 WHLIE i100 PRINT S END S=1 101 S=Si i=i+2 是是 開始開始 結(jié)束結(jié)束 i=1 S=0 i=i+1 S=S+i 輸出輸出S i100? 否否 直到型直到型 S=1 S=Si i=i+2 i101? 算法案例算法案例 1.31.3 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 更相減損術(shù)更相減損術(shù) 1.1.1 1、求兩個(gè)正整數(shù)的最大公約數(shù)、求兩個(gè)正整數(shù)的最大公約數(shù) （1）求）求25和和35的最大公約數(shù)的最大公約數(shù) （2）求）求225和和135的最大公約數(shù)的最大公約數(shù) 2、求、求8251和和6105的最大公約數(shù)的最大公約

44、數(shù) 25（1） 5 5 35 7 所以，所以，25和和35的最大公約數(shù)為的最大公約數(shù)為5 所以，所以，225和和135的最大公約數(shù)為的最大公約數(shù)為533=45 課前復(fù)習(xí) 225（2） 5 45 135 27 3 159 知識(shí)回顧：知識(shí)回顧：先用先用 兩個(gè)數(shù)公有的質(zhì)兩個(gè)數(shù)公有的質(zhì) 因數(shù)連續(xù)去除，因數(shù)連續(xù)去除， 一直除到所得的一直除到所得的 商是互質(zhì)數(shù)為止，商是互質(zhì)數(shù)為止， 然后把所有的除然后把所有的除 數(shù)連乘起來數(shù)連乘起來 3 35 輾轉(zhuǎn)相除法（歐幾里得算法）輾轉(zhuǎn)相除法（歐幾里得算法） 觀察用輾轉(zhuǎn)相除法求觀察用輾轉(zhuǎn)相除法求8251和和6105的最大公約數(shù)的過程的最大公約數(shù)的過程 第一步第一步 用

45、兩數(shù)中較大的數(shù)除以較小的數(shù)，求得用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商商和和余數(shù)余數(shù) 8251=61051+2146 結(jié)論：結(jié)論： 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù)，求的公約數(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ù)。 完整的過程完整的過程 8251=6105

46、1+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0 例例2 用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求225和和135的最大公約數(shù)的最大公約數(shù) 225=1351+90 135=901+45 90=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ī)律是什么

47、？算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù) S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù) S3：重復(fù)：重復(fù)S1，直到余數(shù)為，直到余數(shù)為0 第一步第一步, ,給定兩個(gè)正數(shù)給定兩個(gè)正數(shù)m m、n n 第二步第二步, ,計(jì)算計(jì)算m m除以除以n n所得到余數(shù)所得到余數(shù)r r 第三步第三步,m=n,m=n；n=rn=r 第四步第四步, ,若若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í)行直到余

48、數(shù)等于0 0停止停止 的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。 否否 開始開始 輸入兩個(gè)正數(shù)輸入兩個(gè)正數(shù)m,n mn? r=m MOD n r0? 輸出輸出n 結(jié)束結(jié)束 m=x m=n n=r 否否 是是 是是 INPUT m,n IF mn THEN x=n n=m m=x END IF r=m MOD n WHILE r0 m=n n=r r=m MOD n WEND PRINT n END x=n n=m 更相減損術(shù)更相減損術(shù) 算理算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少 減多，更相減損，求其等也，以等數(shù)約之。

49、減多，更相減損，求其等也，以等數(shù)約之。 第一步：第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是任意給定兩個(gè)正整數(shù)；判斷他們是否都是 偶數(shù)。若是，則用偶數(shù)。若是，則用2 2約簡(jiǎn)；若不是，則執(zhí)行第二步。約簡(jiǎn)；若不是，則執(zhí)行第二步。 第二步：第二步：以以較大的數(shù)減較小的數(shù)較大的數(shù)減較小的數(shù)，接著把所得的差與，接著把所得的差與 較小的數(shù)比較，并以較小的數(shù)比較，并以大數(shù)減小數(shù)大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直。繼續(xù)這個(gè)操作，直 到所得的到所得的減數(shù)和差相等為止減數(shù)和差相等為止，則這個(gè)等數(shù)或這個(gè)等數(shù)，則這個(gè)等數(shù)或這個(gè)等數(shù) 與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)。與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)。 例例1 1、用

50、更相減損術(shù)求、用更相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù). . 解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)以大數(shù) 減小數(shù)，并輾轉(zhuǎn)相減，減小數(shù)，并輾轉(zhuǎn)相減， 即：即：986335; 633528; 35287; 28721; 21714; 1477. 所以，所以，9898與與6363的最大公約數(shù)是的最大公約數(shù)是7 7。 二者算理相似，有異曲同工之妙二者算理相似，有異曲同工之妙 1 1、都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除、都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除 法以除法為主，更相減損術(shù)以減法為主，計(jì)算法以除法為主，更相減損術(shù)以減法為主，計(jì)算 次數(shù)

51、上輾轉(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é)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果、從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果 是以相除余數(shù)為是以相除余數(shù)為0 0則得到，而更相減損術(shù)則以減則得到，而更相減損術(shù)則以減 數(shù)與差相等而得到（差為數(shù)與差相等而得到（差為0 0） 輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 秦九韶算法秦九韶算法 1.3.2 問題問題1設(shè)計(jì)求多項(xiàng)式設(shè)計(jì)求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7 當(dāng)當(dāng)x=5時(shí)的值的算法

52、時(shí)的值的算法,并寫出程序并寫出程序. x=5 f=2*x5-5*x4-4*x3+3*x2-6*x+7 PRINT f END 程序程序 點(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)是不通用,不能解決任意多項(xiàng)多求不能解決任意多項(xiàng)多求 值問題值問題,而且計(jì)算效率不高而且計(jì)算效率不高. 這析計(jì)算上述多項(xiàng)式的值這析計(jì)算上述多項(xiàng)式的值,一共需要一共需要9次乘次乘 法運(yùn)算法運(yùn)算,5次加法運(yùn)算次加法運(yùn)算. 問題問題2有沒有更高效的算法有沒有更高效的算法? 分析分析:計(jì)算計(jì)算x的冪時(shí)的冪時(shí),可以利用前面的計(jì)算結(jié)可

53、以利用前面的計(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ī)來說而且對(duì)于計(jì)算機(jī)來說,做做 一次乘法所需的運(yùn)算時(shí)間比做一次加法要長(zhǎng)得多一次乘法所需的運(yùn)算時(shí)間比做一次加法要長(zhǎng)得多,因因 此第二種做法能更快地得到結(jié)果此第二種做法能更快地得到結(jié)果. 問題問題3能否探索更好的算法能否探索更好的算法,來解決任意多來解決任意多 項(xiàng)式的求值問題項(xiàng)式的求值問題? f(x

54、)=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+7 v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677 這種求多項(xiàng)式值的方法就叫這種求多項(xiàng)式值的方法就叫秦九韶算法秦九韶算法. f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0. 我們可以改寫成如下形式我們

55、可以改寫成如下形式: 求多項(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=vn-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. 秦九韶算法秦九韶

56、算法 點(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)式的值,通過這種轉(zhuǎn)通過這種轉(zhuǎn) 化化,把運(yùn)算的次數(shù)由至多把運(yùn)算的次數(shù)由至多n(n+1)/2次乘法次乘法 運(yùn)算和運(yùn)算和n次加法運(yùn)算次加法運(yùn)算,減少為減少為n次乘法運(yùn)算次乘法運(yùn)算 和和n次加法運(yùn)算次加法運(yùn)算,大大提高了運(yùn)算效率大大提高了運(yùn)算效率. v1=anx+an-1,v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0. 觀察上述秦九韶算法中的觀察上述秦九韶算法中的n

57、個(gè)一次式個(gè)一次式,可見可見 vk的計(jì)算要用到的計(jì)算要用到vk-1的值的值. 若令若令v0=an,得得 v0=an, vK=vK-1x+an-k(k=1,2,n) 這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步 驟驟,因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn). 問題問題畫出程序框圖畫出程序框圖,表示用秦九韶算法求表示用秦九韶算法求5次多項(xiàng)次多項(xiàng) 式式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0當(dāng)當(dāng)x=x0 (x0是是 任意實(shí)數(shù)任意實(shí)數(shù))時(shí)的值的過程時(shí)的值的過程,然后寫出程序然后寫出程序. 算法步驟如下：算法步驟如下： 第一步，輸入多項(xiàng)式次數(shù)第一步，輸入

58、多項(xiàng)式次數(shù)n n、最高次項(xiàng)的系數(shù)、最高次項(xiàng)的系數(shù)an和和x x的值的值. . 第二步，將第二步，將v v的值初始化為的值初始化為an，將，將i i的值初始化為的值初始化為n-1.n-1. 第三步，輸入第三步，輸入i i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)ai. . 第四步，第四步，v=vx+v=vx+ai，i=i-1.i=i-1. 第五步，判斷第五步，判斷i i是否大于或等于是否大于或等于0 0，若是，則返回第三步；，若是，則返回第三步； 否則，輸出多項(xiàng)式的值否則，輸出多項(xiàng)式的值v.v. 否否 程序框圖程序框圖 開始開始 輸入輸入n,an,x的值的值 i0? i=n-1 v=an v=vx+ai i=i-1

59、輸出輸出v 結(jié)束結(jié)束 是是 INPUT “n=”；n INPUT “an=”；a INPUT “x=”；x v=a i=n-1 WHILE i=0 PRINT “i=”; I INPUT “ai=”; a v=v*x+a i=i-1 WEND PRINT v END 輸入輸入ai 進(jìn)位制進(jìn)位制 1.3.3 問題問題11我們常見的數(shù)字都是十進(jìn)制的我們常見的數(shù)字都是十進(jìn)制的, ,但是并不是生但是并不是生 活中的每一種數(shù)字都是十進(jìn)制的活中的每一種數(shù)字都是十進(jìn)制的. .比如時(shí)間和角度的比如時(shí)間和角度的 單位用六十進(jìn)位制單位用六十進(jìn)位制, ,電子計(jì)算機(jī)用的是二進(jìn)制電子計(jì)算機(jī)用的是二進(jìn)制. .那么什那么什

60、 么是進(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)一”,就是幾進(jìn)制就是幾進(jìn)制,幾進(jìn)制的幾進(jìn)制的基數(shù)基數(shù)就是幾就是幾. 可使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)可使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù). .基數(shù)基數(shù) 都是大于都是大于1 1的整數(shù)的整數(shù). . 例如：二進(jìn)制可使用