《高中數(shù)學(xué) 第2章 算法初步章末歸納總結(jié)課件 北師大版必修3.ppt》由會員分享，可在線閱讀，更多相關(guān)《高中數(shù)學(xué) 第2章 算法初步章末歸納總結(jié)課件 北師大版必修3.ppt（69頁珍藏版）》請在裝配圖網(wǎng)上搜索。

成才之路 · 數(shù)學(xué),路漫漫其修遠兮 吾將上下而求索,北師大版 · 必修3,算法初步,第二章,章末歸納總結(jié),第二章,1．算法初步 (1)算法的定義：在解決某些問題時，需要設(shè)計出一系列可操作或可計算的步驟，通過實施這些步驟解決問題，通常把這些步驟稱為解決這類問題的算法． (2)算法的特征：有窮性、確定性、順序性、不唯一性、普適性． (3)算法的三種描述方法：自然語言、流程圖、程序語言．,2．排序問題 (1)排序：根據(jù)某種要求把被查詢的對象用數(shù)字(或者符號)表示出來，并把數(shù)字按大小排列． (2)有序列直接插入順序：將新數(shù)據(jù)與原有序列中的數(shù)據(jù)從右到左依次進行比較，直到發(fā)現(xiàn)某一數(shù)據(jù)小于等于新數(shù)據(jù)，把新數(shù)據(jù)插入到此數(shù)據(jù)的右邊，若新數(shù)據(jù)小于原有序列中所有數(shù)據(jù)，則把新數(shù)據(jù)插入到原有序列的最左邊．,(3)折半插入排序：對于一個有序列，先將新數(shù)據(jù)與該有序列中的“中間位置”的數(shù)據(jù)進行比較. 如果新數(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ù)進行這種比較直到確定新數(shù)據(jù)的位置．,3．算法的三種基本結(jié)構(gòu) (1)順序結(jié)構(gòu)：按照步驟依次執(zhí)行的一個算法，稱為具有順序結(jié)構(gòu)的算法，或者稱為算法的順序結(jié)構(gòu)．如下圖表示的是順序結(jié)構(gòu)的示意圖．,,(2)選擇結(jié)構(gòu)：在一個算法中，先根據(jù)條件判斷，再決定執(zhí)行后面的步驟的結(jié)構(gòu)稱為選擇結(jié)構(gòu)．常見的選擇結(jié)構(gòu)如下圖所示． 它常常用在一些大小比較、正負判斷、分段函數(shù)求值等問題的算法設(shè)計中．,,(3)循環(huán)結(jié)構(gòu)：在算法中，從某處開始，按照一定的條件反復(fù)執(zhí)行步驟的結(jié)構(gòu)為循環(huán)結(jié)構(gòu)． 反復(fù)執(zhí)行的步驟稱為循環(huán)體，控制著循環(huán)的開始和結(jié)束的變量稱為循環(huán)變量，決定是否繼續(xù)執(zhí)行循環(huán)體的判斷條件稱為循環(huán)的終止條件． 循環(huán)結(jié)構(gòu)的算法框圖的基本模式如下圖所示．,循環(huán)結(jié)構(gòu)常常用在一些有規(guī)律的科學(xué)計算中，如：累加求和，累乘求積，多次輸入等．,,4．基本算法語句 基本算法語句包括輸入語句、輸出語句、賦值語句、條件語句和循環(huán)語句． (1)賦值語句：在算法中用來賦給某一變量值的語句叫作賦值語句，其一般格式是：變量＝表達式． (2)條件語句：在算法中處理選擇結(jié)構(gòu)的語句叫作條件語句，條件語句有簡單If語句和復(fù)合If語句．,簡單If語句： If 條件 Then 語句1 Else 語句有2 End If,復(fù)合If語句： If 條件1 Then 語句1 Else If 條件2 Then 語句2 Else 語句3 End If End If,設(shè)計具體數(shù)學(xué)問題的算法，實際上就是尋求一類問題的算法，它可以通過計算機來完成．設(shè)計算法的關(guān)鍵是把過程分解成若干個明確的步驟，然后用計算機能接受的“語言”準確地描述出來．設(shè)計算法時要注意：(1)應(yīng)當先建立過程模型，也就是找到解決問題的方案，再把它細化為一個連續(xù)的步驟，從而設(shè)計出算法；(2)算法的順序性和普遍性，步驟的順序不能顛倒，設(shè)計出的算法需具有解決一類問題的功能．,用自然語言設(shè)計算法,算法的設(shè)計主要包括數(shù)值性問題的算法和非數(shù)值性問題的算法． 對于數(shù)值性問題，如解方程(或方程組)，解不等式(或不等式組)，數(shù)的累加、累乘等一類問題的描述，一般可通過構(gòu)建相應(yīng)的數(shù)學(xué)模型借助數(shù)學(xué)計算方法，將解題過程條理化，分成幾個順序明確的步驟即可寫出算法，對于非數(shù)值性問題，如排序、查找、變量替換、文字處理等，需要先建立過程模型，再通過模型進行算法設(shè)計與描述．,算法設(shè)計與一般意義上的解決問題不同，它是對一類問題的一般解法的抽象與概括，它要借助一般的問題解決方法，又要包含這類問題的所有可能情形，它往往是把問題的解法劃分為若干個可執(zhí)行的步驟，有時甚至是重復(fù)多次，但最終都必須在有限個步驟之內(nèi)完成．,[規(guī)律總結(jié)] 該算法步驟的設(shè)計依據(jù)了解析幾何中求線段垂直平分線的一般方法.,解法二：算法步驟如下： 1．t＝2； 2．i＝4； 3．t＝t*i； 4．i＝i＋2； 5．如果i不大于12，返回重新執(zhí)行第三步，否則輸出t的值就是所求的結(jié)果．,[點評] 從這兩個算法中可以發(fā)現(xiàn)，解法一雖然正確，但比較繁瑣，當連乘的數(shù)較多時，此種算法就顯得更加冗長了，解法二不僅形式上顯得簡練，而且具有通用性和靈活性，對于多個有規(guī)律的數(shù)據(jù)運算尤為合適.,1.算法流程圖是用規(guī)定的框圖和流程線來準確、直觀、形象地表示算法的圖形，畫框圖之前可以通過對問題的分析，建立相應(yīng)的數(shù)學(xué)模型或過程模型，設(shè)計出合理有效的算法，然后分析算法的邏輯結(jié)構(gòu)，根據(jù)邏輯結(jié)構(gòu)畫出相應(yīng)的算法流程圖. 2．如果設(shè)計的算法框圖較為復(fù)雜，就要采取“逐步求精”的思想，先將問題中的簡單部分明確出來，再逐步對復(fù)雜部分進行細化，然后一步一步向前推進．,算法流程圖及其畫法,[規(guī)范解答] 算法流程圖如圖所示.,,“特快專遞”是目前人們經(jīng)常使用的異地郵寄信函或托運物品的一種快捷方式．某快遞公司對甲、乙兩地之間物品的托運費的規(guī)定如下：若托運物品的質(zhì)量x不超過50千克，則按每千克0.53元收取托運費；若托運物品的質(zhì)量超過50千克，則超出部分按每千克0.85元收取托運費．試畫出計算托運費用的算法流程圖．,解決同一個問題，可以有多種算法，那么就有多種算法流程圖和程序，因此高考試題中通常不會考查畫算法框圖或編寫程序．由于學(xué)習(xí)本章的目的是體會算法的思想，所以已知算法流程圖或程序，判斷其結(jié)果是高考考查本章知識的主要形式，這也是課程標準和考試說明對本章的要求．其判斷方法是具體運行所給的算法流程圖或程序，即可得到算法的結(jié)果．,如何判斷算法的結(jié)果,,[規(guī)范解答] 該算法流程圖的運行過程是： i＝2 S＝0 S＝0＋2 i＝2＋2＝4 i＝4≥100，不成立 S＝0＋2＋4 i＝4＋2＝6 i＝6≥100，不成立,S＝0＋2＋4＋6 i＝6＋2＝8 … i＝100≥100成立 則輸出S＝2＋4＋6＋…＋98.由此看，該算法框圖的功能是計算2＋4＋6＋…＋98，可以設(shè)S＝2＋4＋6＋…＋98， 則有S＝98＋96＋94＋…＋2.,上面兩個等式相加得 2S＝(2＋98)＋(4＋96)＋(6＋94)＋…＋(98＋2) ＝100＋100＋100＋…＋100＝100×49＝4 900. 則有2＋4＋6＋…＋100＝2 450. [答案] A,[規(guī)律總結(jié)] 本題易錯選為B，其原因是錯誤判斷該算法流程圖的功能是計算2＋4＋6＋…＋98＋100，其避免方法是判斷循環(huán)結(jié)構(gòu)終止時各個字母的值時，利用逆推法．比如本題中，循環(huán)體終止的條件是i≥100成立即當i剛開始等于100時，就終止循環(huán)．此時剛執(zhí)行完循環(huán)體，所以在計算2＋4＋6＋…＋I后，執(zhí)行了i＝i＋2，由此賦值號“＝”左邊的i等于100，右邊的i等于98，所以該算法框圖的功能是計算2＋4＋6＋…＋98.,執(zhí)行下圖所示的算法流程圖，若輸入x＝4，則輸出y的值為________．,,已知一個算法流程圖，要求將其設(shè)空的某個關(guān)鍵步驟補充完整；或已知一個流程圖，要求我們判斷其功能或求輸出結(jié)果是一種重要題型．解決這類問題需要理清所要實現(xiàn)的算法的結(jié)構(gòu)特點及流程規(guī)則，讀懂算法流程圖．,完善框圖所缺的條件,,[規(guī)范解答] 本題考查了流程圖． 該程序依次如下運行： 初值：S＝1，k＝1 ①k＝2，S＝4 ②k＝3，S＝11 ③k＝4，S＝26 ④k＝5，S＝57 最后輸出S＝57，∴判斷框中應(yīng)填k4? [答案] A,在陽光體育活動中，全校學(xué)生積極參加室外跑步．高三(1)班每個學(xué)生上個月跑步的路程從大到小排列依次是a1，a2，a3，…，a50(任意i＝1,2，…，49，aiai＋1)，如圖是計算該班上個月跑步路程前10名學(xué)生的平均路程的算法框圖．則圖中判斷框①和處理②內(nèi)應(yīng)分別填寫( ),,[答案] C [解析] 注意到判斷框中應(yīng)是保證恰好是10名學(xué)生，再注意到走出判斷框的結(jié)果將是10個數(shù)的和，于是選C.,自然語言表述的算法和算法流程圖是程序設(shè)計的基礎(chǔ)，算法流程圖側(cè)重于直觀性，而程序則傾向于計算機執(zhí)行的實用性．,程序語句的考查,編寫程序的基本方法是“自上而下，逐步求精”，即首先把一個復(fù)雜的大問題分解成若干個相對獨立的小問題，如果小問題仍較復(fù)雜，則可以把這些小問題再繼續(xù)分解成若干個子問題，這樣不斷分解，便可使得小問題或子問題簡單到能夠直接用程序的三種基本結(jié)構(gòu)表達為止，然后，對應(yīng)每一個小問題或子問題編寫出一個功能上相對獨立的程序模塊來，每個模塊各個擊破，最后再統(tǒng)一組裝，問題便可得到解決．,[答案] (1)x≤1 (2)y＝x＋1 4 [規(guī)律總結(jié)] 已知分段函數(shù)的解析式求函數(shù)值的問題，在計算函數(shù)值之前必須先判斷x的范圍，因而編寫程序必須應(yīng)用條件語句書寫，要根據(jù)題目不同的條件選用合適的條件語句．,下列程序運行后的輸出結(jié)果為( ) i＝1 Do i＝i＋2 S=3+2*i i=i+1 Loop While i8 輸出S.,A．17 B．19 C．21 D．23 [答案] C [解析] 這是用Do Loop語句編寫的程序，按Do Loop語句的運行程序可知最后一次執(zhí)行循環(huán)體時S＝2×(7＋2)＋3＝21.,一、選擇題 1．(2014·重慶文，5)執(zhí)行如圖所示的程序框圖，則輸出s的值( ),,A．10 B．17 C．19 D．36 [答案] C [解析] 本題考查算法的循環(huán)結(jié)構(gòu)和層層分析法． k＝2，S＝2；k＝3，S＝5；k＝5，S＝10；k＝9，S＝19，k＝17時，結(jié)束循環(huán)，此時S＝19. 注意k與S循環(huán)時相匹配的取值．,2．(2014·北京文，4)執(zhí)行如圖所示的程序框圖，輸出的S值為( ),,A．1 B．3 C．7 D．15 [答案] C [解析] 本題考查了程序框圖的有關(guān)概念． S1：k＝0，S＝0，S2：S＝20＝1，k＝1，S3：S＝1＋21＝3，k＝2，S4：S＝3＋22＝7，k＝3，S5：輸出S＝7.,3．如圖，該流程圖是求函數(shù)f(x)＝x2－3x＋5，當x∈ {0,3,6,9，…，60}時函數(shù)值的一個流程圖，則①處應(yīng)填( ),,A．x＝x＋3 B．x＝3x C．3x＝x D．x＋3＝x [答案] A [解析] 給出的數(shù)為0,3,6,9，…，60，后一個數(shù)比前一個數(shù)大3.,4．執(zhí)行下面語句的過程中，執(zhí)行循環(huán)體的次數(shù)是( ) i＝1 Do i＝i＋1 i＝i*i Loop While i10 輸出i. A．2 B．0 C．3 D．1 [答案] A,[解析] 算法語句的執(zhí)行過程是 第一次執(zhí)行循環(huán)體： i＝1 i＝1＋1＝2 i＝2×2＝4 i＝410成立,第二次執(zhí)行循環(huán)體： i＝4 i＝4＋1＝5 i＝5×5＝20 i＝2510不成立 退出循環(huán)，共執(zhí)行循環(huán)體2次．,二、填空題 5．閱讀下面的算法語句，如果輸入x＝－2，則輸出結(jié)果為________． 輸入x； If x0 Then y=2*x-3,Else y =0 End If End If 輸出y. [答案] －5,6．如果執(zhí)行如圖所示的程序框圖，輸入x＝4.5，則輸出的數(shù)i＝________. [答案] 4,[解析] 本題考查程序框圖，循環(huán)結(jié)構(gòu)等算法知識． i＝1，x＝4.5－1＝3.5，i＝2，x＝3.5－1＝2.5，i＝3，x＝2.5－1＝1.5，i＝4，x＝1.5－1＝0.5， ∵0.51，∴輸出i＝4.,三、解答題 7．給出30個數(shù)：1,2,4,7，…，其規(guī)律是：第1個數(shù)是1，第2個數(shù)比第1個數(shù)大1，第3個數(shù)比第2個數(shù)大2，第4個數(shù)比第3個數(shù)大3，依此類推，要計算第30個數(shù)的大?。F(xiàn)在已給出了該問題算法的流程圖，如下圖所示． (1)請在圖中判斷框①處和執(zhí)行框②處填上合適的語句，使之能完成該題算法功能； (2)根據(jù)流程圖寫出程序．,[解析] (1)①中應(yīng)填寫“i30？”，②中應(yīng)填寫“P＝i”． (2)程序如下： P＝1 S＝0 i＝1 Do S＝S＋P P＝i i＝i＋1 Loop While i30 輸出 S,,