知識講解_《算法初步》全章復(fù)習(xí)與鞏固_基礎(chǔ)

1、算法初步全章復(fù)習(xí)與鞏固編稿：丁會(huì)敏 審稿：王靜偉 【學(xué)習(xí)目標(biāo)】1.了解算法的含義，了解算法的思想；2. 重點(diǎn)理解程序框圖的三種基本邏輯結(jié)構(gòu)：順序結(jié)構(gòu)、條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu)；3. 重點(diǎn)理解幾種基本算法語句輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句的含義；4會(huì)用輾轉(zhuǎn)相除法和更相減損術(shù)求最大公約數(shù)?！局R網(wǎng)絡(luò)】【要點(diǎn)梳理】要點(diǎn)一：算法的概念1、算法的定義：廣義的算法是指完成某項(xiàng)工作的方法和步驟，那么我們可以說洗衣機(jī)的使用說明書是操作洗衣機(jī)的算法，菜譜是做菜的算法等等.在數(shù)學(xué)中，現(xiàn)代意義的算法是指可以用計(jì)算機(jī)來解決的某一類問題的程序和步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完成

2、.2、算法的特征：（1）確定性：算法的每一步都應(yīng)當(dāng)做到準(zhǔn)確無誤、“不重不漏”.“不重”是指不是可有可無的、甚至無用的步驟，“不漏”是指缺少哪一步都無法完成任務(wù).（2）邏輯性：算法從開始的“第一步”直到“最后一步”之間做到環(huán)環(huán)相扣，分工明確，“前一步”是“后一步”的前提，“后一步”是“前一步”的繼續(xù).（3）有窮性：算法要有明確的開始和結(jié)束，當(dāng)?shù)竭_(dá)終止步驟時(shí)所要解決的問題必須有明確的結(jié)果，也就是說必須在有限步內(nèi)完成任務(wù)，不能無限制的持續(xù)進(jìn)行.（4）不唯一性：求解某一個(gè)問題的算法不一定是唯一的，對于一個(gè)問題可以有不同的算法3、設(shè)計(jì)算法的步驟 算法與一般意義上的解決問題的方法不同，它是針對一類問題的一

3、般解法的抽象和概括，在設(shè)計(jì)算法時(shí)，要注意算法的特性，即概括性、邏輯性、有窮性、普遍性等一般用算法解決問題的過程可大致分為三步： (1)明確問題的性質(zhì)，分析題意 (2)建立問題的描述模型 (3)設(shè)計(jì)明確的算法要點(diǎn)二：程序框圖及其畫法 1. 程序框圖的概念：程序框圖又稱流程圖，是最常用的一種表示法，它是描述計(jì)算機(jī)一步一步完成任務(wù)的圖表，直觀地描述程序執(zhí)行的控制流程，最便于初學(xué)者掌握。2.程序框圖常用符號：圖形符號名稱含義開始/結(jié)束框用于表示算法的開始與結(jié)束輸入/輸出框用于表示數(shù)據(jù)的輸入或結(jié)果的輸出處理框描述基本的操作功能，如“賦值”操作、數(shù)學(xué)運(yùn)算等判斷框判斷某一條件是否成立，成立時(shí)在出口處標(biāo)明“是

4、”或“Y”；不成立時(shí)標(biāo)明“否”或“N”流程線表示流程的路徑和方向連接點(diǎn)用于連接另一頁或另一部分的框圖注釋框框中內(nèi)容是對某部分流程圖做的解釋說明3.畫程序框圖的規(guī)則：(1)使用標(biāo)準(zhǔn)的框圖的符號；(2)框圖一般按從上到下、從左到右的方向畫；(3)除判斷框圖外，大多數(shù)框圖符號只有一個(gè)進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框是具有超過一個(gè)退出點(diǎn)的唯一符號；(4)一種判斷框是“是”與“不是”兩分支的判斷，而且有且僅有兩個(gè)結(jié)果；另一種是多分支判斷，有幾種不同的結(jié)果；(5)在圖形符號內(nèi)描述的語言要非常簡練清楚。4、算法的三種基本邏輯結(jié)構(gòu)(1)順序結(jié)構(gòu)順序結(jié)構(gòu)是最簡單的算法結(jié)構(gòu)，語句與語句之間，框與框之間是按從上到下的順序

5、進(jìn)行的.它是由若干個(gè)依次執(zhí)行的步驟組成的，它是任何一個(gè)算法都離不開的一種基本算法結(jié)構(gòu).見示意圖和實(shí)例： 順序結(jié)構(gòu)在程序框圖中的體現(xiàn)就是用流程線將程序框自上而下地連接起來，按順序執(zhí)行算法步驟.如在示意圖中，A框和B框是依次執(zhí)行的，只有在執(zhí)行完A框指定的操作后，才能接著執(zhí)行B框所指定的操作.(2)條件結(jié)構(gòu)如下面圖示中虛線框內(nèi)是一個(gè)條件結(jié)構(gòu)，此結(jié)構(gòu)中含有一個(gè)判斷框，算法執(zhí)行到此判斷給定的條件P是否成立，選擇不同的執(zhí)行框(A框、B框).無論P(yáng)條件是否成立，只能執(zhí)行A框或B框之一，不可能既執(zhí)行A框又執(zhí)行B框，也不可能A框、B框都不執(zhí)行.A框或B框中可以有一個(gè)是空的，即不執(zhí)行任何操作.見示意圖要點(diǎn)詮釋：條

6、件結(jié)構(gòu)中的條件要準(zhǔn)確，不能含混不清，要清楚在什么情況下需要作怎樣的判斷，用什么條件來區(qū)分(3)循環(huán)結(jié)構(gòu)在一些算法中要求重復(fù)執(zhí)行同一操作的結(jié)構(gòu)稱為循環(huán)結(jié)構(gòu).即從算法某處開始，按照一定條件重復(fù)執(zhí)行某一處理過程.重復(fù)執(zhí)行的處理步驟稱為循環(huán)體.循環(huán)結(jié)構(gòu)有兩種形式：當(dāng)型循環(huán)結(jié)構(gòu)和直到型循環(huán)結(jié)構(gòu).當(dāng)型循環(huán)結(jié)構(gòu)，如左下圖所示，它的功能是當(dāng)給定的條件P成立時(shí)，執(zhí)行A框，A框執(zhí)行完畢后，返回來再判斷條件P是否成立，如果仍然成立，返回來再執(zhí)行A框，如此反復(fù)執(zhí)行A框，直到某一次返回來判斷條件P不成立時(shí)為止，此時(shí)不再執(zhí)行A框，離開循環(huán)結(jié)構(gòu)，繼續(xù)執(zhí)行下面的框圖.直到型循環(huán)結(jié)構(gòu)，如右下圖所示，它的功能是先執(zhí)行重復(fù)執(zhí)行的A

7、框，然后判斷給定的條件P是否成立，如果P仍然不成立，則返回來繼續(xù)執(zhí)行A框，再判斷條件P是否成立，依次重復(fù)操作，直到某一次給定的判斷條件P成立為止，此時(shí)不再返回來執(zhí)行A框，離開循環(huán)結(jié)構(gòu)，繼續(xù)執(zhí)行下面的框圖.見示意圖要點(diǎn)詮釋：循環(huán)結(jié)構(gòu)中使用什么樣的條件控制循環(huán)的開始和結(jié)束，要清楚滿足某個(gè)條件的變量的次數(shù)與循環(huán)次數(shù)的聯(lián)系與區(qū)別.5設(shè)計(jì)程序框圖的注意事項(xiàng)程序框圖是用規(guī)定的圖形和連接線來準(zhǔn)確、直觀、形象地表示算法的圖形，畫程序框圖之前應(yīng)先根據(jù)問題設(shè)計(jì)出合理有效的算法，然后分析算法的邏輯結(jié)構(gòu)，最后根據(jù)邏輯結(jié)構(gòu)畫出相應(yīng)的程序框圖 在畫程序框圖時(shí)，應(yīng)注意圖形的準(zhǔn)確性，連接線指向方向要正確 在利用判斷框設(shè)計(jì)循環(huán)

8、結(jié)構(gòu)時(shí)，對循環(huán)變量要先賦值，同時(shí)注意推出的條件，不能形成死循環(huán)要點(diǎn)三：用基本算法語句編寫程序1輸入語句在程序中的INPUT語句就是輸入語句.這個(gè)語句的一般格式是：INPUT “提示內(nèi)容”；變量其中，“提示內(nèi)容”一般是提示用戶輸入什么樣的信息.INPUT語句不但可以給單個(gè)變量賦值，還可以給多個(gè)變量賦值，其格式為：INPUT “提示內(nèi)容1，提示內(nèi)容2，提示內(nèi)容3，”；變量1，變量2，變量3，功能：可對程序中的變量賦值要點(diǎn)詮釋：“提示內(nèi)容”提示用戶輸入什么樣的信息，必須加雙引號，提示內(nèi)容“原原本本”的在計(jì)算機(jī)屏幕上顯示，提示內(nèi)容與變量之間要用分號隔開；變量是指程序在運(yùn)行時(shí)其值是可以變化的量；一個(gè)語句

9、可以給多個(gè)變量賦值，中間用“，”分隔，但最后的變量的后面不需要；要求輸入的數(shù)據(jù)必須是常量，而不能是函數(shù)、變量或表達(dá)式；無計(jì)算功能.例如，輸入一個(gè)學(xué)生數(shù)學(xué)，語文，英語三門課的成績，可以寫成：INPUT “數(shù)學(xué)，語文，英語”；a，b，c2輸出語句在程序中的PRINT語句是輸出語句.它的一般格式是：PRINT “提示內(nèi)容”；表達(dá)式同輸入語句一樣，表達(dá)式前也可以有“提示內(nèi)容”.功能：可輸出表達(dá)式的值，計(jì)算. 要點(diǎn)詮釋：“提示內(nèi)容”提示用戶輸出什么樣的信息，提示內(nèi)容必須加雙引號，提示內(nèi)容要用分號和表達(dá)式分開；表達(dá)式是指程序要輸出的數(shù)據(jù)，可以是變量、計(jì)算公式或系統(tǒng)信息；一個(gè)語句可以輸出多個(gè)表達(dá)式，不同的表

10、達(dá)式之間可用“，”分隔；有計(jì)算功能，可以輸出常量、變量或表達(dá)式的值以及字符.3賦值語句用來表明賦給某一個(gè)變量一個(gè)具體的確定值的語句.它的一般格式是：變量=表達(dá)式賦值語句中的“=”叫做賦值號.功能：先計(jì)算出賦值號右邊表達(dá)式的值，然后把這個(gè)值賦給賦值號左邊的變量，使該變量的值等于表達(dá)式的值.要點(diǎn)詮釋：賦值號的左右兩邊不能對換，如“A=B”“B=A”的含義運(yùn)行結(jié)果是不同的；格式中右邊“表達(dá)式”可以是一個(gè)數(shù)據(jù)、常量和算式，如果“表達(dá)式”是一個(gè)算式時(shí)，賦值語句的作用是先計(jì)算出“=”右邊表達(dá)式的值，然后將該值賦給“=”左邊的變量；賦值號左邊只能是變量名字，而不能是表達(dá)式，如：2=X是錯(cuò)誤的；不能利用賦值語

11、句進(jìn)行代數(shù)式的演算(如化簡、因式分解等)；對于一個(gè)變量可以多次賦值；有計(jì)算功能；賦值號與數(shù)學(xué)中的等號的意義是不同的.賦值號左邊的變量如果原來沒有值，則執(zhí)行賦值語句后，獲得一個(gè)值，如果已有值，則執(zhí)行該語句后，以賦值號右邊表達(dá)式的值代替該變量的原值，即將“原值”沖掉.4條件語句算法中的條件結(jié)構(gòu)是由條件語句來表達(dá)的，是處理?xiàng)l件分支邏輯結(jié)構(gòu)的算法語句.它的一般格式是：(IF-THEN-ELSE格式)滿足條件？語句1語句2是否IF 條件 THEN語句1ELSE語句2END IF當(dāng)計(jì)算機(jī)執(zhí)行上述語句時(shí)，首先對IF后的條件進(jìn)行判斷，如果條件符合，就執(zhí)行THEN后的語句1，否則執(zhí)行ELSE后的語句2.其對應(yīng)的

12、程序框圖為：(如上右圖)在某些情況下，也可以只使用IF-THEN語句：(即IF-THEN格式)滿足條件？語句是否IF 條件 THEN語句END IF計(jì)算機(jī)執(zhí)行這種形式的條件語句時(shí)，也是首先對IF后的條件進(jìn)行判斷，如果條件符合，就執(zhí)行THEN后的語句，如果條件不符合，則直接結(jié)束該條件語句，轉(zhuǎn)而執(zhí)行其他語句.其對應(yīng)的程序框圖為：(如上右圖)要點(diǎn)詮釋：條件語句的作用：在程序執(zhí)行過程中，根據(jù)判斷是否滿足約定的條件而決定是否需要轉(zhuǎn)換到何處去.需要計(jì)算機(jī)按條件進(jìn)行分析、比較、判斷，并按判斷后的不同情況進(jìn)行不同的處理.5循環(huán)語句算法中的循環(huán)結(jié)構(gòu)是由循環(huán)語句來實(shí)現(xiàn)的.對應(yīng)于程序框圖中的兩種循環(huán)結(jié)構(gòu)，一般程序設(shè)

13、計(jì)語言中也有當(dāng)型(WHILE型)和直到型(UNTIL型)兩種語句結(jié)構(gòu).即WHILE語句和UNTIL語句.（1）WHILE語句的一般格式是：滿足條件？循環(huán)體是否WHILE 條件循環(huán)體WEND其中循環(huán)體是由計(jì)算機(jī)反復(fù)執(zhí)行的一組語句構(gòu)成的.WHLIE后面的“條件”是用于控制計(jì)算機(jī)執(zhí)行循環(huán)體或跳出循環(huán)體的.當(dāng)計(jì)算機(jī)遇到WHILE語句時(shí)，先判斷條件的真假，如果條件符合，就執(zhí)行WHILE與WEND之間的循環(huán)體；然后再檢查上述條件，如果條件仍符合，再次執(zhí)行循環(huán)體，這個(gè)過程反復(fù)進(jìn)行，直到某一次條件不符合為止.這時(shí)，計(jì)算機(jī)將不執(zhí)行循環(huán)體，直接跳到WEND語句后，接著執(zhí)行WEND之后的語句.因此，當(dāng)型循環(huán)有時(shí)也稱

14、為“前測試型”循環(huán).其對應(yīng)的程序結(jié)構(gòu)框圖為：(如上右圖)（2）UNTIL語句的一般格式是：滿足條件？循環(huán)體是否DO循環(huán)體LOOP UNTIL 條件其對應(yīng)的程序結(jié)構(gòu)框圖為：(如上右圖)直到型循環(huán)又稱為“后測試型”循環(huán)，從UNTIL型循環(huán)結(jié)構(gòu)分析，計(jì)算機(jī)執(zhí)行該語句時(shí)，先執(zhí)行一次循環(huán)體，然后進(jìn)行條件的判斷，如果條件不滿足，繼續(xù)返回執(zhí)行循環(huán)體，然后再進(jìn)行條件的判斷，這個(gè)過程反復(fù)進(jìn)行，直到某一次條件滿足時(shí)，不再執(zhí)行循環(huán)體，跳到LOOP UNTIL語句后執(zhí)行其他語句，是先執(zhí)行循環(huán)體后進(jìn)行條件判斷的循環(huán)語句.要點(diǎn)詮釋當(dāng)型循環(huán)與直到型循環(huán)的區(qū)別當(dāng)型循環(huán)是先判斷后執(zhí)行，直到型循環(huán)是先執(zhí)行后判斷；當(dāng)型循環(huán)用WHI

15、LE語句，直到型循環(huán)用UNTIL語句；對同一算法來說，當(dāng)型循環(huán)和直到型循環(huán)的條件互為反條件基本算法語句包括輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句五種，它們對應(yīng)于算法的三種邏輯結(jié)構(gòu)：順序結(jié)構(gòu)、條件分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，用基本語句編寫程序時(shí)，要注意各種語句的格式要求，特別是條件語句和循環(huán)語句，應(yīng)注意這兩類語句中條件的表述以及循環(huán)語句中有關(guān)變量的取值范圍【典型例題】類型一：算法設(shè)計(jì)例l寫出解方程的一個(gè)算法【解析】 算法一：第一步：將方程左邊因式分解，得； 第二步：由得x-30， 或x+10； 第三步：解得x3，解得x-1算法二：第一步：移項(xiàng)，得； 第二步：式兩邊同時(shí)加1并配方，得； 第三步：

16、式兩邊開方，得； 第四步：解得x3或x-1算法三：第一步：計(jì)算方程的判別式判斷其符號22+43160；第二步：將，代入求根公式，得，得， 【總結(jié)升華】 比較三種算法，算法三更簡單，步驟最少，由此我們只要有公式可以利用，利用公式解決問題是最理想、合算的算法因此在尋求算法的過程中，首先是利用公式，下面我們設(shè)計(jì)一個(gè)求一般的一元二次方程的根的算法如下：第一步：計(jì)算；第二步：若，方程無實(shí)根；第三步：若0，方程的根例2設(shè)計(jì)一個(gè)算法，將高一某班56名同學(xué)中考試成績不及格者的分?jǐn)?shù)打印出來 【解析】 算法步驟如下：S1 令n1S2 如果n56，則轉(zhuǎn)到S7 S3 輸入一個(gè)學(xué)生的成績GS4 將G和60比較，如果G6

17、0，則輸出GS5 nn+1 S6 轉(zhuǎn)到S2 S7 結(jié)束【總結(jié)升華】該題中實(shí)際是用到了算法的條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，條件結(jié)構(gòu)用于判斷分?jǐn)?shù)是否小于60；循環(huán)結(jié)構(gòu)用于控制輸入成績的次數(shù)舉一反三：【變式1】 寫出求過點(diǎn)M(-2，-1)、N(2，3)的直線與坐標(biāo)軸圍成的三角形面積的一個(gè)算法 【解析】算法步驟如下：第一步：取，；第二步：得直線方程； 第三步：在第二步的方程中令y0，得y的值m，從而得直線與y軸的交點(diǎn)A(0，m)； 第四步：在第二步的方程中令y0，得x的值n，從而得直線與x軸的交點(diǎn)B(n，0)；第五步：根據(jù)三角形的面積公式求；第六步：輸出運(yùn)算結(jié)果【總結(jié)升華】先由M，N兩點(diǎn)得出直線的方程，再求直線

18、與兩坐標(biāo)軸的交點(diǎn)，求出三角形的兩條直角邊長，再由面積公式計(jì)算類型二：程序框圖及其畫法例3輸出1000以內(nèi)能被3和5整除的所有正整數(shù)，畫出其程序框圖 【解析】 能被3和5整除的正整數(shù)一定能被15整除，由于10001566+10，因此1000以內(nèi)一共有66個(gè)這樣的正整數(shù)引入變量a表示待輸出的數(shù)，則a15n(n1，2，3，66)，n從1變到66，反復(fù)輸出a，就能輸出l000以內(nèi)的所有能被3和5整除的正整數(shù)，算法流程圖如圖所示 【總結(jié)升華】像這樣的算法結(jié)構(gòu)稱為循環(huán)結(jié)構(gòu)，其中反復(fù)執(zhí)行的第部分稱為循環(huán)體 變量n控制著循環(huán)的開始和結(jié)束，稱為循環(huán)變量，第部分就是賦予循環(huán)變量初始值，預(yù)示循環(huán)開始 第部分判斷是否

19、繼續(xù)執(zhí)行循環(huán)體，稱為循環(huán)的終止條件 循環(huán)結(jié)構(gòu)主要用在一些有規(guī)律的重復(fù)計(jì)算的算法中，如累加求和、累乘求積等問題常需要用循環(huán)結(jié)構(gòu)來設(shè)計(jì)算法 在循環(huán)結(jié)構(gòu)中，要注意依據(jù)條件，設(shè)計(jì)合理的計(jì)數(shù)變量、累加變量等，要特別注意循環(huán)結(jié)構(gòu)中條件的表述要恰當(dāng)、精確，以免出現(xiàn)多一次循環(huán)或少一次循環(huán)的情況例4.按下列程序框圖來計(jì)算：(算法)執(zhí)行如圖所示的程序框圖,若輸入的值為8,則輸出的值為_.【思路點(diǎn)撥】本題是循環(huán)型程序框圖，可以依次寫出其前面的循環(huán)，找到規(guī)律，進(jìn)而解答。【答案】8【解析】第一次循環(huán),;第二次循環(huán),;第三次循環(huán),.此時(shí)退出循環(huán),輸出的值為8. 舉一反三：【變式1】指出下列程序框圖的運(yùn)行的結(jié)果（1）圖1的運(yùn)行結(jié)果是 ；（2）圖2的運(yùn)行結(jié)果是； （3）圖3中若輸入,則輸出的結(jié)果是 ；（4）圖4的運(yùn)行結(jié)果是 【答案】（1）；（2）；（3）是負(fù)數(shù)；（4）。【變式2】如圖5的算法功能是； 輸出的結(jié)果為 ；【答案】積為624的相鄰兩個(gè)整數(shù)，24，26【變式3】已知函數(shù)，以下程序框圖(圖6)表示的是給定值，求其相應(yīng)函數(shù)值的算法請將該程序框圖補(bǔ)充完整其中處應(yīng)填，處應(yīng)填 【答案】， 類型三：用基本算法語句編寫程序例5如圖所示，在邊長為4的正方形ABCD的邊上有一點(diǎn)P，沿著折線B-C-D-A由點(diǎn)B(起點(diǎn))向點(diǎn)A(終點(diǎn))運(yùn)動(dòng)設(shè)點(diǎn)P運(yùn)動(dòng)的路程