算法初步知識點及習(xí)習(xí)題

1、 算 法算法是高中數(shù)學(xué)課程中的新增內(nèi)容，是中國數(shù)學(xué)課程內(nèi)容的一個新特色“算法”過程是指機械式地按照某種確定的步驟行事，通過一系列小的簡單計算操作完成復(fù)雜計算的過程算法的學(xué)習(xí)內(nèi)容大致可分為三個步驟：用自然語言描述算法；精確刻畫算法(程序框圖)；計算機實現(xiàn)執(zhí)行算法(程序語言的描述過程)算法思想貫穿高中數(shù)學(xué)課程的相關(guān)部分【知識要點】1算法：算法可以理解為由基本運算及規(guī)定的運算順序所構(gòu)成的完整的解題步驟，或者看成按照要求設(shè)計好的有限的確切的計算序列，并且這樣的步驟或序列能夠解決一類問題現(xiàn)代意義上的“算法”通常是指可以用計算機來解決的某一類問題的程序或步驟2程序框圖程序框圖：用一些通用的符號構(gòu)成一張圖來

2、表示算法，這種圖稱為程序框圖(程序框圖又稱流程圖，是一種用程序框、流程線及文字說明來表示算法的圖形)用框圖表示算法步驟的一些常用的圖形符號：程序框名稱功能終端框(起止框)表示一個算法的起始和結(jié)束輸入、輸出框表示一個算法輸入和輸出的信息處理框(執(zhí)行框)賦值、計算判斷框判斷某一條件是否成立，成立時在出口處標(biāo)明“是”，不成立時標(biāo)明“否”流程線(指向線)指引流程圖的方向連接點連接另一頁或另一部分的框圖程序框圖的三種基本邏輯結(jié)構(gòu)：順序結(jié)構(gòu)：描述的是最簡單的算法結(jié)構(gòu)，語句與語句之間、框與框之間按從上到下的順序進行(如圖91)圖91條件分支結(jié)構(gòu)：依據(jù)指定條件選擇執(zhí)行不同指令的控制結(jié)構(gòu)(如圖92)圖92循環(huán)結(jié)

3、構(gòu)：根據(jù)指定條件決定是否重復(fù)執(zhí)行一條或多條指令的控制結(jié)構(gòu)(如圖93)圖933幾種基本算法語句任何一個程序設(shè)計語言中，都包含五種基本的算法語句，即輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句輸入語句和輸出語句分別用來實現(xiàn)算法的輸入信息、輸出結(jié)果的功能；賦值語句是用來表明賦給某一個變量一個具體的確定值的語句；條件語句是處理條件分支邏輯結(jié)構(gòu)的算法語句；循環(huán)語句是用來處理算法中的循環(huán)結(jié)構(gòu)的語句4中國古代算法案例：更相減損之術(shù)、輾轉(zhuǎn)相除法：求兩個正數(shù)的最大公因數(shù)的方法輾轉(zhuǎn)相除法算法步驟：第一步：用兩數(shù)中較大數(shù)除以較小數(shù)，求商和余數(shù)第二步：用除數(shù)除以余數(shù)第三步：重復(fù)第二步，直到余數(shù)為0第四步，得出兩數(shù)

4、的最大公約數(shù)，即余數(shù)0之前的余數(shù)更相減損術(shù)算法步驟：第一步：用較大數(shù)減去較小數(shù)，得到差第二步：比較減數(shù)與差的大小，再用較大數(shù)減去較小數(shù)第三步：重復(fù)第二步，直到差與減數(shù)相等為止第四步：相等數(shù)即為最大公約數(shù)割圓術(shù)：用正多邊形的面積逐漸逼近圓面積的算法求圓周率p秦九韶算法：求一元多項式的值的一種方法，遞推關(guān)系為【復(fù)習(xí)要求】1了解算法的含義，了解算法的思想2理解程序框圖的三種基本邏輯結(jié)構(gòu)：順序結(jié)構(gòu)、條件分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)3理解幾種基本算法語句輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句的含義【例題分析】例1 如圖(圖94)所示，將一系列指令用框圖的形式表示，箭頭指向下一步的操作請按照框圖回答問題：

5、圖94(1)這個框圖表示了怎樣的算法(2)輸出的數(shù)是多少【分析】由框圖中的文字及圖形符號表示的操作內(nèi)容可知：此算法是“求1到50的和”，由此可以算出輸出的數(shù)解：(1)此框圖表示的算法為：求12350的和；(2)易知所求和為1275【評析】程序框圖主要包括三部分：表示相應(yīng)操作的框，帶箭頭的流程線和框外必要的說明讀框圖時要從這三個方面研究，流程線反映了命令執(zhí)行的先后順序，主要看箭頭方向，框及內(nèi)外的文字說明表明了操作內(nèi)容常用這種方式考察對算法的理解和應(yīng)用例2 (1)如圖95所示的是一個算法的程序框圖，已知a13，輸出的結(jié)果為7，則a2的值為_圖95(2)如圖96所示的是某個函數(shù)求值的程序框圖，則滿足

6、該程序的函數(shù)解析式為_圖96(3)如圖97所示的是求某個數(shù)列和的程序框圖，此程序輸出的結(jié)果為_圖97【分析】這三個小題的重點在于讀懂框圖(1)只含有順序結(jié)構(gòu)，(2)含有條件分支結(jié)構(gòu)，表明函數(shù)的定義域為R，當(dāng)x0時，遵從解析式f(x)3x1，否則(即當(dāng)x0時)，遵從解析式f(x)25x；(3)中有兩個循環(huán)變量S、I，S是累加變量，I是計數(shù)變量；另外還要判斷I的奇偶性，以此決定是加還是減解：(1)；(2)；(3)S1222324299210025050【評析】題(1)，只含有順序結(jié)構(gòu)，所表示的算法比較簡單，只需按照框圖箭頭方向依次讀出即可題(2)含有條件分支結(jié)構(gòu)，這是一個與分段函數(shù)有關(guān)的算法，框圖

7、中含有判斷框讀包含有判斷框的框圖時，要特別重視判斷框內(nèi)的條件和框外的文字說明，對應(yīng)的下一步操作會依條件不同而改變題(3)含有循環(huán)結(jié)構(gòu)，當(dāng)解決一些有規(guī)律的科學(xué)計算問題，尤其是累加和累乘時，往往可以利用循環(huán)結(jié)構(gòu)來實現(xiàn)算法循環(huán)結(jié)構(gòu)有兩種，讀包含有循環(huán)結(jié)構(gòu)的框圖時，除關(guān)注判斷框內(nèi)外的說明外，一般要從開始依順序做幾次循環(huán)，觀察變量的變化規(guī)律來幫助讀懂算法的含義例3 (1)已知平面上的一點P0(x0，y0)和直線l：AxByC0，求點P0到直線l的距離d，并畫出程序框圖(2)用條件分支結(jié)構(gòu)寫“已知三個數(shù)a、b、c，找出其中最大數(shù)”的算法及框圖(3)寫出求的和的算法，畫出程序框圖，并寫出相應(yīng)程序(選做)【分

8、析】正確分析“算理”，才能選擇恰當(dāng)?shù)乃惴ńY(jié)構(gòu)，有條理的表達算法(1)在已知點到直線距離公式的前提下，適合用順序結(jié)構(gòu)表示；(2)涉及比大小，必須用到條件分支結(jié)構(gòu)；(3)中分母有規(guī)律的遞增，可以引入累加變量S和計數(shù)變量i，且SS1/i是反復(fù)進行的，可以用循環(huán)結(jié)構(gòu)表示解：(1)算法及框圖為：S1 輸入x0，y0；A，B，C；S2 計算mA2B2；S3 計算nAx0By0C；S4 計算；S5 輸出d；(2)算法及框圖為：S1 輸入a，b，c；S2 令xa；S3 若bx，則令xb；否則，執(zhí)行S4；S4 若cx，則令xc；否則，執(zhí)行S5；S5 輸出x；(3)算法及框圖為：S1 輸入i1，S0；S2 當(dāng)in

9、時，ii1；否則執(zhí)行S3；S3 輸出S；程序如下；S0For i1:1:nSS1/iii1endprint(io(2)，S)【評析】書寫算法時，一步一步的程序化步驟，即“算則”固然重要，但這些步驟的依據(jù)，即“算理”有著更基本的作用，“算理，是“算則”的基礎(chǔ)，“算則”是“算理”的表現(xiàn)這三道小題由于算理不同，所蘊含的算法結(jié)構(gòu)也不同通過實例，模仿、操作、探索，經(jīng)歷通過設(shè)計程序框圖表達解決問題的過程，可以更好的理解幾種基本算法語句輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句，體會和理解算法的含義，了解算法語言的基本構(gòu)成本例中涉及的“利用公式求點到直線的距離”、“實數(shù)排序求最值問題”、“求數(shù)列的和或

10、積的問題”，還包括“二分法求函數(shù)零點”、“質(zhì)數(shù)的判定”，“求p的近似值”等等，都是算法的典型案例，學(xué)習(xí)時要給予充分的重視一般算法的表示方法并不唯一不同的算法語言的書寫形式是有差別的本書所采用的是Scilab語言，學(xué)習(xí)時要了解賦值語句、輸入輸出語句、if語句、while和for語句的基本含義及表達方式，能夠讀懂語句表示的算法過程例4 (1)用輾轉(zhuǎn)相除法計算56和264的最大公約數(shù)時，需要做的除法次數(shù)是_(2)用更相減損術(shù)求56和98的最大公約數(shù)時，操作如下：(98，56)(56，42)(42，14)(28，14)(14，14)，由此可知兩數(shù)的最大公約數(shù)為_(3)用秦九韶算法求得多項式f(x)x6

11、2x53x34x26x5當(dāng)x2時函數(shù)值為_解：(1)所以最大公約數(shù)為8，需做的除法次數(shù)是4；(2)最大公約數(shù)為14；(3)33【評析】書上所涉及的古代基本算法案例包括：更相減損術(shù)與輾轉(zhuǎn)相除法、秦九韶算法、割圓術(shù)輾轉(zhuǎn)相除法與更相減損術(shù)都是求最大公約數(shù)的方法，輾轉(zhuǎn)相除法又叫歐幾里得方法，計算上以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上，前者相對較少，特別是兩個整數(shù)相差較大時區(qū)別尤其明顯；輾轉(zhuǎn)相除法以余數(shù)為0結(jié)束，更相減損術(shù)則以減數(shù)與差相等結(jié)束秦九韶算法的特點是把求n次多項式的值轉(zhuǎn)化為求n個一次多項式的值，運算時只有加法和乘法，而且運算的次數(shù)比較少，求一個n次多項式的值最多需要進行n次加法、n次乘

12、法割圓術(shù)是由中國古代數(shù)學(xué)家劉徽提出的，是當(dāng)時計算圓周率比較先進的算法，“算理”明確，即用圓內(nèi)接正多邊形和外切正多邊形逼近圓周率，重點是確定遞推關(guān)系例5 (09遼寧)某店一個月的收入和支出總共記錄了N個數(shù)據(jù)，其中收入記為正數(shù)，支出記為負(fù)數(shù)該店用下邊的程序框圖計算月總收入S和月凈盈利V那么在圖中空白的判斷框和處理框中，應(yīng)分別填入下列四個選項中的( )AA0，VSTBA0，VSTCA0，VSTDA0，VST【分析】本題要注意三點：ak有正有負(fù)；S為總收入，是所有正數(shù)的和；T為總支出，是所有非正數(shù)的和答案為C【評析】本題結(jié)合實際背景，強調(diào)算法的應(yīng)用價值，是一種比較新的題型，應(yīng)引起關(guān)注練習(xí)9一、選擇題1

13、任何一個算法都必須有的基本結(jié)構(gòu)是( )A順序結(jié)構(gòu)B條件分支結(jié)構(gòu)C循環(huán)結(jié)構(gòu)D以上三個都要有2下面給出對程序框圖的幾種說法：任何一個程序框圖都必須有起止框；判斷框有一個入口，有不止一個出口；對于一個算法來說，判斷框內(nèi)的條件表達方式是唯一的；其中正確的有( )A0個B1個C2個D3個3在算法的邏輯結(jié)構(gòu)中，要求進行邏輯判斷并根據(jù)結(jié)果進行不同處理的是哪種結(jié)構(gòu)( )A順序結(jié)構(gòu)B條件分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)C順序結(jié)構(gòu)和條件分支結(jié)構(gòu)D順序結(jié)構(gòu)和循環(huán)結(jié)構(gòu)4算法：S1 輸入n；S2 判斷n是否是2；若n2，則n滿足條件，若 n2，則執(zhí)行S3；S3 依次從2到n1檢驗?zāi)芊裾齨，若都不能整除，則n滿足條件；滿足上述算法的

14、n是( )A奇數(shù)B偶數(shù)C質(zhì)數(shù)D合數(shù)二、填空題5閱讀下面兩個程序框圖，框圖1輸出的結(jié)果為_；框圖2輸出的結(jié)果為_ 框圖1 框圖26(08廣東)閱讀圖98的程序框圖，若輸入m4，n6，則輸出a_，i_ 圖98 圖997閱讀圖99的程序框圖，若輸入的n是100，則輸出的變量S和T的值依次是_8“x3*5”和“xx1”是某個程序中的先后相鄰兩個語句，下列說法中“x3*5”是將數(shù)值15賦給x，而不是普通運算“x3*515”；“x3*5”可以寫成“3*5x”語句“xx1”在執(zhí)行時，“”右邊x為15，“”左邊x為16；正確的有_三、解答題9分別用輾轉(zhuǎn)相除法和更相減損術(shù)求189和81的最大公約數(shù)10用循環(huán)語句書寫求123n1000的最小自然數(shù)n的算法，畫出程序框圖，并寫出相應(yīng)的程序(選做)11(09寧夏)為了測量兩山頂MN間的距離，飛機沿水平方向在AB兩點進行測量，MN在同一個鉛垂平面內(nèi)(如圖)飛機能夠測量的數(shù)據(jù)有俯角和AB間的距離，請你設(shè)計一個方案，包括：指出需要測量的數(shù)據(jù)(用字母表示，并在圖中標(biāo)出)；用文字和公式寫出計算MN間距離的步驟專題九 算法參考答案練習(xí)9一、選擇題1A 2C 3B 4C二、填空題527，21 612，3 72550，2500 8三、解答題9解：輾轉(zhuǎn)相除法：，所以最大公約數(shù)為27更相減損術(shù)：18981108，