1、成才之路 數(shù)學(xué),路漫漫其修遠(yuǎn)兮 吾將上下而求索,北師大版 必修3,算法初步,第二章,本章歸納總結(jié),第二章,1算法初步 (1)算法的定義：在解決某些問(wèn)題時(shí)，需要設(shè)計(jì)出一系列可操作或可計(jì)算的步驟，通過(guò)實(shí)施這些步驟解決問(wèn)題，通常把這些步驟稱為解決這類問(wèn)題的算法 (2)算法的特征：有窮性、確定性、順序性、不唯一性、普適性 (3)算法的三種描述方法：自然語(yǔ)言、流程圖、程序語(yǔ)言,2排序問(wèn)題 (1)排序：根據(jù)某種要求把被查詢的對(duì)象用數(shù)字(或者符號(hào))表示出來(lái)，并把數(shù)字按大小排列 (2)有序列直接插入順序：將新數(shù)據(jù)與原有序列中的數(shù)據(jù)從右到左依次進(jìn)行比較，直到發(fā)現(xiàn)某一數(shù)據(jù)小于等于新數(shù)據(jù)，把新數(shù)據(jù)插入到此數(shù)據(jù)的右邊

2、，若新數(shù)據(jù)小于原有序列中所有數(shù)據(jù)，則把新數(shù)據(jù)插入到原有序列的最左邊,(3)折半插入排序：對(duì)于一個(gè)有序列，先將新數(shù)據(jù)與該有序列中的“中間位置”的數(shù)據(jù)進(jìn)行比較. 如果新數(shù)據(jù)小于“中間位置”的數(shù)據(jù)，則新數(shù)據(jù)插入的位置應(yīng)該在最靠左邊的一半；如果新數(shù)據(jù)等于“中間位置”的數(shù)據(jù)，則將新數(shù)據(jù)插入到“中間位置”的數(shù)據(jù)的右邊；如果新數(shù)據(jù)大于“中間位置”的數(shù)據(jù)，則新數(shù)據(jù)插入的位置應(yīng)該在靠右邊的一半反復(fù)進(jìn)行這種比較直到確定新數(shù)據(jù)的位置,3算法的三種基本結(jié)構(gòu) (1)順序結(jié)構(gòu)：按照步驟依次執(zhí)行的一個(gè)算法，稱為具有順序結(jié)構(gòu)的算法，或者稱為算法的順序結(jié)構(gòu)如下圖表示的是順序結(jié)構(gòu)的示意圖,簡(jiǎn)單If語(yǔ)句： If條件Then 語(yǔ)句1

3、 Else 語(yǔ)句2 End If 復(fù)合If語(yǔ)句： If條件1Then,語(yǔ)句1 Else If條件2Then 語(yǔ)句2 Else 語(yǔ)句3 End If End If,設(shè)計(jì)具體數(shù)學(xué)問(wèn)題的算法，實(shí)際上就是尋求一類問(wèn)題的算法，它可以通過(guò)計(jì)算機(jī)來(lái)完成設(shè)計(jì)算法的關(guān)鍵是把過(guò)程分解成若干個(gè)明確的步驟，然后用計(jì)算機(jī)能接受的“語(yǔ)言”準(zhǔn)確地描述出來(lái)設(shè)計(jì)算法時(shí)要注意：(1)應(yīng)當(dāng)先建立過(guò)程模型，也就是找到解決問(wèn)題的方案，再把它細(xì)化為一個(gè)連續(xù)的步驟，從而設(shè)計(jì)出算法；(2)算法的順序性和普遍性，步驟的順序不能顛倒，設(shè)計(jì)出的算法需具有解決一類問(wèn)題的功能,用自然語(yǔ)言設(shè)計(jì)算法,算法的設(shè)計(jì)主要包括數(shù)值性問(wèn)題的算法和非數(shù)值性問(wèn)題的算法

4、 對(duì)于數(shù)值性問(wèn)題，如解方程(或方程組)，解不等式(或不等式組)，數(shù)的累加、累乘等一類問(wèn)題的描述，一般可通過(guò)構(gòu)建相應(yīng)的數(shù)學(xué)模型借助數(shù)學(xué)計(jì)算方法，將解題過(guò)程條理化，分成幾個(gè)順序明確的步驟即可寫出算法，對(duì)于非數(shù)值性問(wèn)題，如排序、查找、變量替換、文字處理等，需要先建立過(guò)程模型，再通過(guò)模型進(jìn)行算法設(shè)計(jì)與描述,算法設(shè)計(jì)與一般意義上的解決問(wèn)題不同，它是對(duì)一類問(wèn)題的一般解法的抽象與概括，它要借助一般的問(wèn)題解決方法，又要包含這類問(wèn)題的所有可能情形，它往往是把問(wèn)題的解法劃分為若干個(gè)可執(zhí)行的步驟，有時(shí)甚至是重復(fù)多次，但最終都必須在有限個(gè)步驟之內(nèi)完成,解法二：算法步驟如下： 1t2； 2i4； 3tt*i； 4ii2

5、； 5如果i不大于12，返回重新執(zhí)行第三步，否則輸出t的值就是所求的結(jié)果 點(diǎn)評(píng)從這兩個(gè)算法中可以發(fā)現(xiàn)，解法一雖然正確，但比較繁瑣，當(dāng)連乘的數(shù)較多時(shí)，此種算法就顯得更加冗長(zhǎng)了，解法二不僅形式上顯得簡(jiǎn)練，而且具有通用性和靈活性，對(duì)于多個(gè)有規(guī)律的數(shù)據(jù)運(yùn)算尤為合適.,1.算法流程圖是用規(guī)定的框圖和流程線來(lái)準(zhǔn)確、直觀、形象地表示算法的圖形，畫(huà)框圖之前可以通過(guò)對(duì)問(wèn)題的分析，建立相應(yīng)的數(shù)學(xué)模型或過(guò)程模型，設(shè)計(jì)出合理有效的算法，然后分析算法的邏輯結(jié)構(gòu)，根據(jù)邏輯結(jié)構(gòu)畫(huà)出相應(yīng)的算法流程圖. 2如果設(shè)計(jì)的算法框圖較為復(fù)雜，就要采取“逐步求精”的思想，先將問(wèn)題中的簡(jiǎn)單部分明確出來(lái)，再逐步對(duì)復(fù)雜部分進(jìn)行細(xì)化，然后一步一

6、步向前推進(jìn),算法流程圖及其畫(huà)法,規(guī)范解答算法流程圖如圖所示.,解決同一個(gè)問(wèn)題，可以有多種算法，那么就有多種算法流程圖和程序，因此高考試題中通常不會(huì)考查畫(huà)算法框圖或編寫程序由于學(xué)習(xí)本章的目的是體會(huì)算法的思想，所以已知算法流程圖或程序，判斷其結(jié)果是高考考查本章知識(shí)的主要形式，這也是課程標(biāo)準(zhǔn)和考試說(shuō)明對(duì)本章的要求其判斷方法是具體運(yùn)行所給的算法流程圖或程序，即可得到算法的結(jié)果,如何判斷算法的結(jié)果,已知一個(gè)算法流程圖，要求將其設(shè)空的某個(gè)關(guān)鍵步驟補(bǔ)充完整；或已知一個(gè)流程圖，要求我們判斷其功能或求輸出結(jié)果是一種重要題型解決這類問(wèn)題需要理清所要實(shí)現(xiàn)的算法的結(jié)構(gòu)特點(diǎn)及流程規(guī)則，讀懂算法流程圖,完善框圖所缺的條件

7、,規(guī)范解答本題考查了流程圖 該程序依次如下運(yùn)行： 初值：S1，k1 k2，S4 k3，S11 k4，S26 k5，S57 最后輸出S57，判斷框中應(yīng)填k4? 答案A,答案C 解析注意到判斷框中應(yīng)是保證恰好是10名學(xué)生，再注意到走出判斷框的結(jié)果將是10個(gè)數(shù)的和，于是選C.,自然語(yǔ)言表述的算法和算法流程圖是程序設(shè)計(jì)的基礎(chǔ)，算法流程圖側(cè)重于直觀性，而程序則傾向于計(jì)算機(jī)執(zhí)行的實(shí)用性 編寫程序的基本方法是“自上而下，逐步求精”，即首先把一個(gè)復(fù)雜的大問(wèn)題分解成若干個(gè)相對(duì)獨(dú)立的小問(wèn)題，如果小問(wèn)題仍較復(fù)雜，則可以把這些小問(wèn)題再繼續(xù)分解成若干個(gè)子問(wèn)題，這樣不斷分解，便可使得小問(wèn)題或子問(wèn)題簡(jiǎn)單到能夠直接用程序的三

8、種基本結(jié)構(gòu)表達(dá)為止，然后，對(duì)應(yīng)每一個(gè)小問(wèn)題或子問(wèn)題編寫出一個(gè)功能上相對(duì)獨(dú)立的程序模塊來(lái)，每個(gè)模塊各個(gè)擊破，最后再統(tǒng)一組裝，問(wèn)題便可得到解決,程序語(yǔ)句的考查,規(guī)范解答算法框圖如圖所示：,A17B.19 C21D.23 答案C 解析這是用Do Loop語(yǔ)句編寫的程序，按Do Loop語(yǔ)句的運(yùn)行程序可知最后一次執(zhí)行循環(huán)體時(shí)S2(72)321.,一、選擇題 1執(zhí)行如圖所示的程序框圖，則輸出s的值(),A10B.17 C19D.36 答案C 解析本題考查算法的循環(huán)結(jié)構(gòu)和層層分析法 k2，S2；k3，S5；k5，S10；k9，S19，k17時(shí)，結(jié)束循環(huán)，此時(shí)S19. 注意k與S循環(huán)時(shí)相匹配的取值,2執(zhí)行如

9、圖所示的程序框圖，輸出的S值為(),A1B.3 C7D.15 答案C 解析本題考查了程序框圖的有關(guān)概念 S1：k0，S0，S2：S201，k1，S3：S1213，k2，S4：S3227，k3，S5：輸出S7.,3(2015北京理，3)執(zhí)行如圖所示的程序框圖，輸出的結(jié)果為(),A(2,2)B.(4,0) C(4，4)D.(0，8) 答案B 解析運(yùn)行程序：x1，y1，k0，s110，t112，x0，y2，k011，因?yàn)?3不滿足，s2，t2，x2，y2，k2，因?yàn)?3不滿足，s4，t0，x4，y0，k3，因?yàn)?3滿足，輸出(4,0),4如圖，該流程圖是求函數(shù)f(x)x23x5，當(dāng)x0,3,6,9，

10、60時(shí)函數(shù)值的一個(gè)流程圖，則處應(yīng)填(),Axx3B.x3x C3xxD.x3x 答案A 解析給出的數(shù)為0,3,6,9，60，后一個(gè)數(shù)比前一個(gè)數(shù)大3.,5執(zhí)行下面語(yǔ)句的過(guò)程中，執(zhí)行循環(huán)體的次數(shù)是() i1 Do ii1 ii*i Loop Whilei10 輸出i. A2B.0 C3D.1 答案A,解析算法語(yǔ)句的執(zhí)行過(guò)程是 第一次執(zhí)行循環(huán)體： i1 i112 i224 i410成立 第二次執(zhí)行循環(huán)體： i4 i415 i5525 i2510不成立 退出循環(huán)，共執(zhí)行循環(huán)體2次,二、填空題 6閱讀下面的算法語(yǔ)句，如果輸入x2，則輸出結(jié)果為_(kāi) 輸入x； If x0 Then y2*x3 Else,y0

11、 End If End If 輸出y. 答案5,7如果執(zhí)行如圖所示的程序框圖，輸入x4.5，則輸出的數(shù)i_.,答案4 解析本題考查程序框圖，循環(huán)結(jié)構(gòu)等算法知識(shí) i1，x4.513.5，i2，x3.512.5，i3，x2.511.5，i4，x1.510.5， 0.51，輸出i4.,8執(zhí)行下面的程序框圖，若輸入的x的值為1，則輸出的n的值為_(kāi),答案3 解析由x24x30，解得1x3， 當(dāng)x1時(shí)，滿足1x3， 所以x112，n011； 當(dāng)x2時(shí)，滿足1x3， 所以x213，n112； 當(dāng)x3時(shí)，滿足1x3， 所以x314，n213； 當(dāng)x4時(shí)，不滿足1x3， 所以輸出n3.,三、解答題 9.給出30個(gè)數(shù)：1,2,4,7，其規(guī)律是：第1個(gè)數(shù)是1，第2個(gè)數(shù)比第1個(gè)數(shù)大1，第3個(gè)數(shù)比第2個(gè)數(shù)大2