2014屆高考數學北師大版一輪復習講義課件101算法與程序框圖_第1頁
2014屆高考數學北師大版一輪復習講義課件101算法與程序框圖_第2頁
2014屆高考數學北師大版一輪復習講義課件101算法與程序框圖_第3頁
2014屆高考數學北師大版一輪復習講義課件101算法與程序框圖_第4頁
2014屆高考數學北師大版一輪復習講義課件101算法與程序框圖_第5頁
已閱讀5頁,還剩66頁未讀 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、考考 點點 串串 串串 講講 1算法算法 (1)算法的概念算法的概念 在解決某些問題時,需要設計出一系列可操作或可計算的步驟,在解決某些問題時,需要設計出一系列可操作或可計算的步驟,通過實施這些步驟解決問題,通過實施這些步驟解決問題, 通常把這些步驟稱為解決這些問題的算通常把這些步驟稱為解決這些問題的算法通俗的說,算法就是計算機解題的過程法通俗的說,算法就是計算機解題的過程 如做四則運算要先乘除后加減,如做四則運算要先乘除后加減, 從里往外去括號,從里往外去括號,豎式筆算等都豎式筆算等都是算法;又如買電視機,包括選好電視,開發票,付款,取貨,運送是算法;又如買電視機,包括選好電視,開發票,付款

2、,取貨,運送回家等步驟,這些步驟構成買電視機的算法;回家等步驟,這些步驟構成買電視機的算法; 一首歌的樂譜,可以稱一首歌的樂譜,可以稱之為該歌曲的算法;空調的使用說明書是空調使用的算法等等之為該歌曲的算法;空調的使用說明書是空調使用的算法等等 說明:說明:上述描述不是嚴格定義的算法,上述描述不是嚴格定義的算法, 但是反映了算法的基本但是反映了算法的基本思想思想(程序化思想程序化思想)現在,算法通常可以編寫成計算機程序,讓計算現在,算法通常可以編寫成計算機程序,讓計算機執行并解決問題機執行并解決問題 算法的三種描述方法:自然語言、算法框圖、程序語言算法的三種描述方法:自然語言、算法框圖、程序語言

3、 (2)算法的特征算法的特征 有窮性:算法的步驟必須是有限的,如果不是有限的,這個有窮性:算法的步驟必須是有限的,如果不是有限的,這個問題就解決不了,那也就不能成為一個算法問題就解決不了,那也就不能成為一個算法 確定性:確定性:算法中的每一個語句執行之后的結果必須是確定的,算法中的每一個語句執行之后的結果必須是確定的,即算法的步驟需清晰、準確即算法的步驟需清晰、準確 順序性:算法的步驟是有順序的,不能隨意調換順序性:算法的步驟是有順序的,不能隨意調換 不唯一性:一個問題的算法并不是唯一的,同一個問題可能不唯一性:一個問題的算法并不是唯一的,同一個問題可能存在著多種算法:如教材中例存在著多種算法

4、:如教材中例4韓信點兵、例韓信點兵、例5稱銀元的問題都有稱銀元的問題都有多種算法多種算法 普適性:算法應該可以解決一類類似的問題,不止是一個問普適性:算法應該可以解決一類類似的問題,不止是一個問題例如教材中例題例如教材中例5稱銀元的問題,把銀元換成某種同一型號的零稱銀元的問題,把銀元換成某種同一型號的零件也適用件也適用 (3)算法中的算法中的“平臺思想平臺思想” “平臺思想平臺思想”是算法設計中的一個最基本的思想,也是數學中是算法設計中的一個最基本的思想,也是數學中思考問題的一個重要思想所謂思考問題的一個重要思想所謂“平臺思想平臺思想”就是利用已知的數學就是利用已知的數學問題的解決辦法問題的解

5、決辦法(即以此為即以此為“平臺平臺”)來解決新問題來解決新問題 例如,教材的幾個例題中查找、求根的算法,這些算法是建立例如,教材的幾個例題中查找、求根的算法,這些算法是建立在二分法的在二分法的“平臺平臺”之上的;求最大公約數的算法建立在對自然數之上的;求最大公約數的算法建立在對自然數進行素因數分解的進行素因數分解的“平臺平臺”之上等等,因此我們要首先學好數學的之上等等,因此我們要首先學好數學的基本思想和基礎知識,然后才能寫出好的算法基本思想和基礎知識,然后才能寫出好的算法 2排序排序 (1)排序的定義排序的定義 為了便于查詢和檢索,我們常常根據某種要求把被查詢的對象為了便于查詢和檢索,我們常常

6、根據某種要求把被查詢的對象用數字用數字(或者符號或者符號)表示出來,并把數字按大小排列,這是信息處理表示出來,并把數字按大小排列,這是信息處理中一項基本的工作,通常稱為排序中一項基本的工作,通常稱為排序 按從小到大按從小到大(或從大到小或從大到小)的順序排列的數據列稱為有序列,有的順序排列的數據列稱為有序列,有序列通常用序列通常用a1,a2,an來表示將一個新數據插入有序列中,來表示將一個新數據插入有序列中,常用的排序算法有直接插入排序法和折半插入排序法常用的排序算法有直接插入排序法和折半插入排序法 (2)直接插入排序法直接插入排序法 有序列插入排序就是找到要插入的數據在已知序列中的位置,有序

7、列插入排序就是找到要插入的數據在已知序列中的位置,然后把它插入進去,組成新的序列然后把它插入進去,組成新的序列 對于一個有序列:對于一個有序列:a1a2a3an,欲將新數據欲將新數據A插入到有插入到有序列中,形成新的有序列,其做法是:將數據序列中,形成新的有序列,其做法是:將數據A與原有序列中的數與原有序列中的數據從右到左依次進行比較,直到發現某一數據據從右到左依次進行比較,直到發現某一數據ai使得使得aiA,把,把A插入到插入到ai的右邊;如果數據的右邊;如果數據A小于原有序列中的所有數據,則將小于原有序列中的所有數據,則將A插入到原序列的最左邊上面的排序算法通常稱為有序列直接插入插入到原序

8、列的最左邊上面的排序算法通常稱為有序列直接插入排序的算法排序的算法 (3)折半插入排序法折半插入排序法 對于一個有序列,先將新數據與該有序列中對于一個有序列,先將新數據與該有序列中“中間位置中間位置”的數據的數據進行比較,若有序列有進行比較,若有序列有2n1個數據,則個數據,則“中間位置中間位置”的數據指的是的數據指的是第第n1個數,若有序列有個數,若有序列有2n個數據,則個數據,則“中間位置中間位置”的數據指的是的數據指的是第第n個數如果新數據小于個數如果新數據小于“中間位置中間位置”的數據,則新數據插入的位的數據,則新數據插入的位置應該在靠左邊的一半;如果新數據等于置應該在靠左邊的一半;如

9、果新數據等于“中間位置中間位置”的數據,則將的數據,則將新數據插入到新數據插入到“中間位置中間位置”的數據的右邊;如果新數據大于的數據的右邊;如果新數據大于“中間位中間位置置”的數據,則新數據插入的位置應該在靠右邊的一半也就是說,的數據,則新數據插入的位置應該在靠右邊的一半也就是說,一次比較就排除了數據列中一半的位置反復進行這種比較,直到確一次比較就排除了數據列中一半的位置反復進行這種比較,直到確定新數據的位置這種插入排序方法我們稱為折半插入排序方法定新數據的位置這種插入排序方法我們稱為折半插入排序方法 說明:說明:折半插入排序方法中應用了二分法的思想,減少了多次無折半插入排序方法中應用了二分

10、法的思想,減少了多次無用的比較,相比較直接插入排序法能夠減少一些資源浪費用的比較,相比較直接插入排序法能夠減少一些資源浪費 由此我們可以看出,同一個問題,可以有多種算法只是有的算由此我們可以看出,同一個問題,可以有多種算法只是有的算法比較省時、簡便,有的算法比較費時、復雜,但它們都能夠按照順法比較省時、簡便,有的算法比較費時、復雜,但它們都能夠按照順序解決問題這就是算法的多樣性序解決問題這就是算法的多樣性 (4)無序列插入排序無序列插入排序 對一組無序的數據列進行排序時,通常將這組無序的數據列的對一組無序的數據列進行排序時,通常將這組無序的數據列的第一個數據看成一個有序列,將第二個數據插入到這

11、個有序列中,第一個數據看成一個有序列,將第二個數據插入到這個有序列中,得到一個新的有序列;然后,將第三個數據插入到由前面兩個數據得到一個新的有序列;然后,將第三個數據插入到由前面兩個數據組成的有序列中,又得到一個新的有序列組成的有序列中,又得到一個新的有序列,按照這種方法,直,按照這種方法,直到將最后一個數據插入到有序列中,得到一個最終的有序列這樣到將最后一個數據插入到有序列中,得到一個最終的有序列這樣實質上就是完成了對無序的數據列排序,最后得到的有序列就是對實質上就是完成了對無序的數據列排序,最后得到的有序列就是對無序的數據列排序的結果無序的數據列排序的結果 3關于框圖的知識關于框圖的知識

12、框圖表示算法用到的圖形符號,如下表:框圖表示算法用到的圖形符號,如下表: 圖形符號圖形符號 名稱名稱 符號表示的意義符號表示的意義 表示一個算法的開始表示一個算法的開始起、止框起、止框 和結束,是任何框圖和結束,是任何框圖必不可少的必不可少的 表示一個算法輸入和表示一個算法輸入和輸入、輸輸入、輸輸出的信息,可用在輸出的信息,可用在 出框出框 算算 法法 中中 任任 何何 需需 要要 輸輸入、輸出的位置入、輸出的位置 賦值、計算算法中處理數賦值、計算算法中處理數據需要的算式、公式等,它據需要的算式、公式等,它處理框處理框 們分別寫在不同的用以處理們分別寫在不同的用以處理 數據的處理框內數據的處理

13、框內 判斷某一條件是否成立,成判斷某一條件是否成立,成判斷框判斷框 立時出口處標明立時出口處標明“是是”;不;不成立時標明成立時標明“否否” 連接程序框,表示算法進行連接程序框,表示算法進行流程線流程線 的方向以及先后順序的方向以及先后順序 作框圖的規則及注意點:作框圖的規則及注意點: (1)每一種框圖符號都有自己的意義,不能混用,符號一定要規每一種框圖符號都有自己的意義,不能混用,符號一定要規范起始框只有一條流出線,終止框只有一條流入線,輸入、輸出范起始框只有一條流出線,終止框只有一條流入線,輸入、輸出框和處理框只有一條流入線和一條流出線判斷框有一條流入線和框和處理框只有一條流入線和一條流出

14、線判斷框有一條流入線和兩條流出線兩條流出線 (2)框圖是按從上而下、從左而右的順序來畫的算法的一個步框圖是按從上而下、從左而右的順序來畫的算法的一個步驟到另一個步驟,要用流程線連接,流程線要帶箭頭,表明流程執驟到另一個步驟,要用流程線連接,流程線要帶箭頭,表明流程執行的次序行的次序 (3)起、止框是任何框圖不可少的,表明算法的開始或結束起、止框是任何框圖不可少的,表明算法的開始或結束 (4)算法中要處理的數據,一般分別寫在不同的處理框內算法中要處理的數據,一般分別寫在不同的處理框內 (5)當算法遇到需要判斷的情況時,判斷條件寫在判斷框內當算法遇到需要判斷的情況時,判斷條件寫在判斷框內 (6)框

15、圖符號框內的文字表述要簡潔、精練框圖符號框內的文字表述要簡潔、精練 (7)一般情況下,我們先用自然語言編寫算法,然后再畫框圖一般情況下,我們先用自然語言編寫算法,然后再畫框圖 4順序結構順序結構 按照步驟依次執行的一個算法,稱為具有順序結構的算法,或按照步驟依次執行的一個算法,稱為具有順序結構的算法,或者稱為算法的順序結構者稱為算法的順序結構 由于圖具有直觀、清楚,便于檢查和交流的特點,所以為了使由于圖具有直觀、清楚,便于檢查和交流的特點,所以為了使算法結構更加清晰,可借助圖來幫助描述算法,這種描述算法的圖算法結構更加清晰,可借助圖來幫助描述算法,這種描述算法的圖稱為框圖順序結構的框圖如圖所示

16、稱為框圖順序結構的框圖如圖所示 順序結構是最簡單的算法結構,語句與語句之間是按從上到下順序結構是最簡單的算法結構,語句與語句之間是按從上到下的順序進行的,它由若干個依次處理的步驟組成,它是任何算法都的順序進行的,它由若干個依次處理的步驟組成,它是任何算法都離不開的一種算法結構離不開的一種算法結構 5選擇結構選擇結構 在一個算法中,通常會遇到一些條件的判斷,算法的流程根據在一個算法中,通常會遇到一些條件的判斷,算法的流程根據條件是否成立有不同的流向,這種先根據條件進行判斷,再決定執條件是否成立有不同的流向,這種先根據條件進行判斷,再決定執行哪一種操作的結構稱為選擇結構行哪一種操作的結構稱為選擇結

17、構 選擇結構的框圖如圖選擇結構的框圖如圖(1)所示,在此結構中含有一個判斷框,所示,在此結構中含有一個判斷框, 算算法執行到此判斷框給定的條件時,根據條件是否成立,選擇不同的法執行到此判斷框給定的條件時,根據條件是否成立,選擇不同的執行框執行框(步驟甲或步驟乙步驟甲或步驟乙)無論條件是否成立,只能執行步驟甲或無論條件是否成立,只能執行步驟甲或步驟乙,不能既執行步驟甲又執行步驟乙,也不能步驟甲和步驟乙步驟乙,不能既執行步驟甲又執行步驟乙,也不能步驟甲和步驟乙都不執行步驟甲和步驟乙中可以有一個是空的,如圖都不執行步驟甲和步驟乙中可以有一個是空的,如圖(2)所示所示 6循環結構循環結構 (1)循環結

18、構的概念循環結構的概念 在算法中,從某處開始,按照一定的條件反復執行某些步驟的在算法中,從某處開始,按照一定的條件反復執行某些步驟的結構稱為循環結構結構稱為循環結構 反復執行的步驟稱為循環體,反復執行的步驟稱為循環體,控制著循環的開始和結束的變量,控制著循環的開始和結束的變量,稱為循環變量,決定是否繼續執行循環體的判斷條件,稱為循環的稱為循環變量,決定是否繼續執行循環體的判斷條件,稱為循環的終止條件終止條件 (2)循環結構的設計過程循環結構的設計過程 設計循環結構之前需要確定的三件事:設計循環結構之前需要確定的三件事: 確定循環變量和初始條件:確定循環變量和初始條件: 確定算法中反復執行的部分

19、,即循環體;確定算法中反復執行的部分,即循環體; 確定循環的終止條件確定循環的終止條件 循環結構的算法框圖的基本模式如圖所示循環結構的算法框圖的基本模式如圖所示 此模式的執行過程是:先執行一次循環體,再對循環的終止條此模式的執行過程是:先執行一次循環體,再對循環的終止條件進行判斷,如果條件不滿足,就繼續執行循環體,當滿足條件時件進行判斷,如果條件不滿足,就繼續執行循環體,當滿足條件時終止循環終止循環 說明:說明:如圖所示是循環結構的另外一種常用模式,此模式的執如圖所示是循環結構的另外一種常用模式,此模式的執行過程是:先對條件進行判斷,如果條件不滿足,執行一次循環體,行過程是:先對條件進行判斷,

20、如果條件不滿足,執行一次循環體,再對條件進行判斷,如果不滿足就繼續執行循環體,直到滿足條件再對條件進行判斷,如果不滿足就繼續執行循環體,直到滿足條件時終止循環時終止循環 (3)計數變量與累加計數變量與累加(積積)變量變量 在循環結構中通常都有一個計數變量和一個累加在循環結構中通常都有一個計數變量和一個累加(積積)變量變量 計數計數變量用于記錄循環次數,變量用于記錄循環次數,累加累加(積積)變量用于輸出結果變量用于輸出結果計數變量和累計數變量和累加加(積積)變量一般是同步執行的,累加變量一般是同步執行的,累加(積積)一次,計數一次循環結構一次,計數一次循環結構中幾個常用的變量:中幾個常用的變量:

21、 計數器,即計數變量,用來記錄某個事件發生的次數,如計數器,即計數變量,用來記錄某個事件發生的次數,如ii1,nn1. 累加器,即累加變量,用來計算數據之和,如累加器,即累加變量,用來計算數據之和,如sumsumi. 累積器,即累積變量,用來計算數據之積,如累積器,即累積變量,用來計算數據之積,如pp*i. 對于這些變量,在程序開始,一般要先賦初始值,可根據實際對于這些變量,在程序開始,一般要先賦初始值,可根據實際問題合理選擇初始值,一般情況下,計數器可設初始值為問題合理選擇初始值,一般情況下,計數器可設初始值為0或或1,累加器為累加器為0,累積器為,累積器為1. 7三種基本結構的關系及它們的

22、特點三種基本結構的關系及它們的特點 (1)三種基本結構的關系三種基本結構的關系 順序結構、選擇結構和循環結構是算法框圖的基本結構順序結構、選擇結構和循環結構是算法框圖的基本結構 順序結構是最基本的也是最簡單的控制結構;順序結構是最基本的也是最簡單的控制結構; 選擇結構則是需要通過先判斷,再決定執行哪個步驟的控制選擇結構則是需要通過先判斷,再決定執行哪個步驟的控制結構;結構; 循環結構則是需要反復執行某些步驟的控制結構,循環結構循環結構則是需要反復執行某些步驟的控制結構,循環結構要在某個條件下終止循環,這就需用選擇結構來判斷,因此循環結要在某個條件下終止循環,這就需用選擇結構來判斷,因此循環結構

23、一定包含選擇結構另外,循環結構也一定包含順序結構構一定包含選擇結構另外,循環結構也一定包含順序結構 (2)三種基本結構的共同特點三種基本結構的共同特點 只有一個入口;只有一個入口; 只有一個出口;只有一個出口; 注意:注意:一個判斷框有兩個出口,一個判斷框有兩個出口,而一個選擇結構只有一個出口,而一個選擇結構只有一個出口,不要將判斷框的出口和選擇結構的出口混為一談不要將判斷框的出口和選擇結構的出口混為一談 結構內的每一部分都有機會被執行到,也就是說對每一個框結構內的每一部分都有機會被執行到,也就是說對每一個框來說都應當有一條從入口到出口的路徑通過它如圖所示中的來說都應當有一條從入口到出口的路徑

24、通過它如圖所示中的A,沒有一條從入口到出口的路徑通過它,是不符合要求的算法框圖沒有一條從入口到出口的路徑通過它,是不符合要求的算法框圖 結構內不存在死循環,即無終止的循環,如圖所示就是一個結構內不存在死循環,即無終止的循環,如圖所示就是一個死循環,程序不能結束,也不能解決任何問題死循環,程序不能結束,也不能解決任何問題 8算法框圖的畫法算法框圖的畫法 框圖是算法的一種表示形式,框圖是算法的一種表示形式, 具有直觀形象、具有直觀形象、結構清晰和簡潔明了結構清晰和簡潔明了的特點,的特點, 但難點是怎樣才能熟練而準確地畫出框圖,但難點是怎樣才能熟練而準確地畫出框圖, 為此教你為此教你“抓特征,抓特征

25、,明規則,依步驟明規則,依步驟”九字訣,讓你即刻擁有畫框圖的基本功九字訣,讓你即刻擁有畫框圖的基本功 (1)抓特征抓特征 組成任何一個框圖的三要素是組成任何一個框圖的三要素是“四框四框”、“一線一線”加加“文字說文字說明明”,所以首先要抓住它們各自的特征與意義,所以首先要抓住它們各自的特征與意義 “四框四框”的特征與意義:的特征與意義: ()起止框的特征是圓角矩形,表示算法的開始和結束,是任何框起止框的特征是圓角矩形,表示算法的開始和結束,是任何框圖不可缺少的內容;圖不可缺少的內容; ()輸入、輸出框的特征是平行四邊形,表示算法中輸入和輸出的輸入、輸出框的特征是平行四邊形,表示算法中輸入和輸出

26、的信息,可放在任何需輸入、輸出的位置;信息,可放在任何需輸入、輸出的位置; ()處理框的特征是方角矩形,表示賦值和計算等,算法中要處理處理框的特征是方角矩形,表示賦值和計算等,算法中要處理的數據或計算可分別寫在不同的處理框內;的數據或計算可分別寫在不同的處理框內; ()判斷框的特征是菱形,用在當算法要求對兩個不同的結果進行判斷框的特征是菱形,用在當算法要求對兩個不同的結果進行判斷時判斷時 “一線一線”的特征與意義的特征與意義: 流程線的特征是帶有方向箭頭的線,流程線的特征是帶有方向箭頭的線,用以連接圖框,直觀地表示算法的流程任意兩個圖框之間都存在用以連接圖框,直觀地表示算法的流程任意兩個圖框之

27、間都存在流程線流程線 “文字文字”的特征與意義的特征與意義 :在圖框內加以說明的文字、在圖框內加以說明的文字、 算式等,算式等,也是每個框圖不可缺少的內容也是每個框圖不可缺少的內容 (2)明規則明規則 框圖的畫法規則是:框圖的畫法規則是: 用標準,即使用標準的圖框符號;用標準,即使用標準的圖框符號; 按順序,即框圖一般從上到下、從左到右的順序畫;按順序,即框圖一般從上到下、從左到右的順序畫; 看出入,看出入,即大多數圖框的圖形符號只有一個入口和一個出口,即大多數圖框的圖形符號只有一個入口和一個出口,判斷框是唯一具有超過一個出口的符號且要在出口處標明判斷框是唯一具有超過一個出口的符號且要在出口處

28、標明“是是”或或“否否”; 明循環,明循環,即循環結構要注意變量的初始值及循環的終止條件;即循環結構要注意變量的初始值及循環的終止條件; 辨流向,即流程線的箭頭表示執行的方向,不可缺少;辨流向,即流程線的箭頭表示執行的方向,不可缺少; 簡說明,即在圖框內的描述語言要簡練清晰簡說明,即在圖框內的描述語言要簡練清晰 (3)依步驟依步驟 畫框圖的總體步驟是:畫框圖的總體步驟是: 第一步,設計算法,因為算法的設計是畫框圖的基礎,所以在第一步,設計算法,因為算法的設計是畫框圖的基礎,所以在畫框圖前,首先寫出相應的算法步驟,并分析算法需要哪種基本結畫框圖前,首先寫出相應的算法步驟,并分析算法需要哪種基本結

29、構構(順序結構、選擇結構、循環結構順序結構、選擇結構、循環結構); 第二步,把算法步驟轉化為對應的框圖,在這種轉化過程中往第二步,把算法步驟轉化為對應的框圖,在這種轉化過程中往往需要考慮很多細節,是一個將算法往需要考慮很多細節,是一個將算法“細化細化”的過程的過程 9流程圖與結構圖流程圖與結構圖 (1)工序流程圖工序流程圖 工序流程圖可以按照從左到右,也可以按照從上到下的順序工序流程圖可以按照從左到右,也可以按照從上到下的順序來畫,圖形用矩形棱形表示,再用流程線相連,流程線是有向線,來畫,圖形用矩形棱形表示,再用流程線相連,流程線是有向線,表示工序進展的方向表示工序進展的方向 工序流程圖描述加

30、工工序之間的動態過程,這就與實際生活工序流程圖描述加工工序之間的動態過程,這就與實際生活聯系密切,因此,對一些行業術語、流程程序要有初步的了解聯系密切,因此,對一些行業術語、流程程序要有初步的了解 在畫工序流程圖時,不能出現幾道工序首尾相連的圈圖或循在畫工序流程圖時,不能出現幾道工序首尾相連的圈圖或循環回路環回路 (2)結構圖結構圖 結構圖一般由構成系統的若干要素和表達各要素之間關系的連結構圖一般由構成系統的若干要素和表達各要素之間關系的連線線(或方向箭頭或方向箭頭)構成,構成,連線通常是從上到下或從左到右的方向,連線通常是從上到下或從左到右的方向, 一般一般呈樹形狀的結構,在結構圖中也經常出

31、現一些呈樹形狀的結構,在結構圖中也經常出現一些“環環”形結構,這種形結構,這種情形常在表達邏輯先后關系時出現情形常在表達邏輯先后關系時出現 繪制結構圖時步驟如下:繪制結構圖時步驟如下: 對所畫的結構圖的每一部分有一個深刻的理解,從頭到尾抓對所畫的結構圖的每一部分有一個深刻的理解,從頭到尾抓住主要脈絡進行分解住主要脈絡進行分解 將每一部分進行歸納與提煉,形成一個個點并逐一寫在矩形將每一部分進行歸納與提煉,形成一個個點并逐一寫在矩形框內框內 按其邏輯順序將它們排列起來,并用線相連結按其邏輯順序將它們排列起來,并用線相連結 (3)在畫結構圖時,一般情況下在畫結構圖時,一般情況下“下位下位”要素比要素

32、比“上位上位”要素更要素更為具體,為具體,“上位上位”要素比要素比“下位下位”要素更為抽象要素更為抽象“下位下位”要素越要素越多,結構圖越復雜所以,畫結構圖時,應該根據具體需要確定復多,結構圖越復雜所以,畫結構圖時,應該根據具體需要確定復雜程度,簡潔的結構圖有時能更好地反映主體要素之間的關系和系雜程度,簡潔的結構圖有時能更好地反映主體要素之間的關系和系統的整體特點統的整體特點. 典典 例例 對對 對對 碰碰 題型一題型一 算法的設計算法的設計 ? ? ?x2y1 例例1.對于方程組對于方程組? ?,試設計一個算法,求,試設計一個算法,求x、y? ? ?2xy1 的值的值 分析分析 解二元一次方

33、程組的主要方法是消元,可加減消元或代解二元一次方程組的主要方法是消元,可加減消元或代入消元入消元 解析解析 算法步驟如下:算法步驟如下: (1)(2),得,得5y3 ; 3(2)解解得得y ; 51(3)將將代入代入整理得整理得x ; 5? ?x1? ?5(4)方程組的解為方程組的解為? ? 3? ?y.? ?5 點評點評 對于一般的二元一次方程組對于一般的二元一次方程組 ? ? ?a1xb1yc1 ? ?(a1b2a2b10), ? ? ?a2xb2yc2 a2b1a2a2c1(1)()得到得到(b2)yc2 ; a1a1a1 a1c2a2c1(2)解解得得y ; a1b2a2b1b2c1b

34、1c2(3)將將代入代入整理得到整理得到x; a1b2a2b1(4)輸出輸出x,y 變式遷移變式遷移1 100個和尚吃個和尚吃100個饅頭,大和尚個饅頭,大和尚1人吃人吃3個,小和尚個,小和尚3人吃人吃1個試設計一個算法,求大、小和尚各多少個?個試設計一個算法,求大、小和尚各多少個? 解析解析 本題可以看作二元一次方程組的求解問題,我們直接套本題可以看作二元一次方程組的求解問題,我們直接套用典例用典例3中總結的公式設有中總結的公式設有x個大和尚,個大和尚,y個小和尚算法步驟個小和尚算法步驟如下:如下: y? ? ?3x 100 3(1)先列方程組先列方程組? ?; ? ? ?xy100 8(2

35、)3得得y200 ; 3(3)解解得得y75 ; (4)將將代入代入得得x25; (5)大、小和尚分別有大、小和尚分別有25個、個、75個個. 題型二題型二 有序列的排序有序列的排序 例例2.分別用直接插入排序法和折半插入排序法將數據分別用直接插入排序法和折半插入排序法將數據56插入插入到有序列到有序列1,8,12,36,49,57,68,79中,寫出相應的算法中,寫出相應的算法 分析分析 根據兩種排序法的思想分別代入比較可得根據兩種排序法的思想分別代入比較可得 解析解析 直接插入排序算法:直接插入排序算法: (1)56與與79比較,比較,5679,56應在應在79的左邊;的左邊; (2)56

36、與與68比較,比較,5668,56應在應在68的左邊;的左邊; (3)56與與57比較,比較,5657,56應在應在57的左邊;的左邊; (4)56與與49比較,比較,5649,56應在應在49的右邊的右邊 因此將因此將56插入到插入到49與與57之間,得到一個新的有序列:之間,得到一個新的有序列:1,8,12,36,49,56,57,68,79 折半插入排序算法:折半插入排序算法: (1)將將56與中間位置的數據與中間位置的數據36比較,比較,5636,故,故56應該在應該在36的右邊;的右邊; (2)將將56與剩余數據的中間位置的數據與剩余數據的中間位置的數據57比較,比較,5657, 故

37、故56應該在應該在57的左邊;的左邊; (3)再將再將56與與49比較,比較,5649,故,故56應該在應該在49與與57之間之間 由由 此此 得得 插插 入入 數數 據據56后后 的的 一一 個個 新新 的的 有有 序序 列列 :1,8,12,36,49,56,57,68,79 點評點評 折半插入排序法的關鍵在于中間位置數據的確定,若有折半插入排序法的關鍵在于中間位置數據的確定,若有序列中有偶數個數據時,中間位置的數據是中間兩個數據中靠左邊序列中有偶數個數據時,中間位置的數據是中間兩個數據中靠左邊的數據,只要注意這一點就不難將數據插入到有序列中正確的位置的數據,只要注意這一點就不難將數據插入

38、到有序列中正確的位置. 變式遷移變式遷移2 請利用直接插入排序和折半插入排序的方法分別寫出將數據請利用直接插入排序和折半插入排序的方法分別寫出將數據43,69插入到有序列插入到有序列21,39,46,57,67,73,84,96中的算法中的算法 解析解析 直接插入排序算法:直接插入排序算法: 將將43與與96比較,比較,4396,所以,所以43在在96的左邊;的左邊; 將將43與與84比較,比較,4384,所以,所以43在在84的左的左邊;邊;將將43與與73比較,比較,4373,所以,所以43在在73的左邊;的左邊;將將43與與67比較,比較,4367,所以,所以43在在67的左邊;的左邊;

39、 將將43與與57比較,比較,4357,所以,所以43在在57的左邊;的左邊; 將將43與與46比較,比較,4346,所以,所以43在在46的左邊;的左邊;將將43與與39比較,比較,4339,故,故43在在39與與46之之間間得到一個新的有序列為得到一個新的有序列為21,39,43,46,57,67,73,84,96再將再將69與與排序后的這一數據列中的數據進行比較,利用同樣的方法可得排序排序后的這一數據列中的數據進行比較,利用同樣的方法可得排序之后新的數據列為之后新的數據列為21,39,43,46,57,67,69,73,84,96 折半插入排序算法:共折半插入排序算法:共8個數據,中間位

40、置上的數據是個數據,中間位置上的數據是57,將,將43與與57進行比較,進行比較,4357,43在有序列的左半部分;在有序列的左半部分; 再將余下數據再將余下數據的中間位置上的數據的中間位置上的數據39與與43進行比較,進行比較,3943,43在數據在數據39的右的右邊邊 , 又又4346, 可可 得得43的的 位位 置置 , 即即 新新 的的 有有 序序 列列 為為21,39,43,46,57,67,73,84,96同理,可得同理,可得69的位置,即新的有序列的位置,即新的有序列為為21,39,43,46,57,67,69,73,84,96. 題型三題型三 無序列的排序無序列的排序 例例3.

41、設計一個算法,對無序列設計一個算法,對無序列36,6,12,24,38,46,0進行排序進行排序 分析分析 反復應用有序列插入排序的思想方法,在排序過程中要反復應用有序列插入排序的思想方法,在排序過程中要明確每次比較的數據是哪一個明確每次比較的數據是哪一個 解析解析 算法如下:算法如下: (1)36是有序列,將是有序列,將36與與6比較,因為比較,因為366,故得到有序列,故得到有序列6,36; (2)將將12與與6,36各數據進行比較,因為各數據進行比較,因為126,1236,故得到,故得到有序列有序列6,12,36; (3)將將24與與6,12,36各數據進行比較,因為各數據進行比較,因為

42、2412,2436,故,故得到有序列得到有序列6,12,24,36; (4)將將38與與6,12,24,36各數據進行比較,因為各數據進行比較,因為3836,故得到,故得到有序列有序列6,12,24,36,38; (5)將將46與與6,12,24,36,38各數據進行比較,因為各數據進行比較,因為4638,故得,故得到有序列到有序列6,12,24,36,38,46; (6)將將0與與6,12,24,36,38,46各數據進行比較,因為各數據進行比較,因為06,故得,故得到有序列到有序列0,6,12,24,36,38,46 所以,排序之后的結果為所以,排序之后的結果為0,6,12,24,36,3

43、8,46 點評點評 用有序列插入排序算法完成無序列排序的問題,基本解用有序列插入排序算法完成無序列排序的問題,基本解決思想非常簡單,即反復使用有序列插入排序算法,使有序列的長決思想非常簡單,即反復使用有序列插入排序算法,使有序列的長度不斷增加,一直到完成整個無序列的有序排列為止度不斷增加,一直到完成整個無序列的有序排列為止. 變式遷移變式遷移3 設計一個算法,對無序列設計一個算法,對無序列12,17,50,18,21,3,6進行排序進行排序 解析解析 算法如下:算法如下: (1)12是有序列,將是有序列,將12與與17進行比較,因為進行比較,因為1217,故得到,故得到有序列有序列12,17;

44、 (2)將將50與與12,17各數據進行比較,因為各數據進行比較,因為5017,故得到有序,故得到有序列列12,17,50; (3)將將18與與12,17,50各數據進行比較,因為各數據進行比較,因為1850,1817,故,故得到有序列得到有序列12,17,18,50; (4)將將21與與12,17,18,50各數據進行比較,因為各數據進行比較,因為2150,2118,故得到有序列故得到有序列12,17,18,21,50; (5)將將3與與12,17,18,21,50各數據進行比較,各數據進行比較,因為因為312,故得到故得到有序列有序列3,12,17,18,21,50; (6)將將6與與3,

45、12,17,18,21,50各數據進行比較,因為各數據進行比較,因為612,63,故得到有序列故得到有序列3,6,12,17,18,21,50 所以排序之后的結果為所以排序之后的結果為3,6,12,17,18,21,50. 題型四題型四 順序結構順序結構 例例4.用尺規作圖,用尺規作圖,確定一條長度為確定一條長度為x的線段滿足關系式的線段滿足關系式x2ab. 分析分析 要使要使x2ab,可借助于圓的相交弦定理,可借助于圓的相交弦定理 解析解析 算法如下:算法如下: (1)作線段作線段ABa; (2)延長延長AB到點到點C,使,使BCb; (3)以以AC為直徑作半圓;為直徑作半圓; (4)過點過

46、點B作作BDAC交半圓于點交半圓于點D,則,則BDx. 算法的框圖如圖所示算法的框圖如圖所示 點評點評 順序結構是按步驟依次執行的一種算法結構這一系順序結構是按步驟依次執行的一種算法結構這一系列步驟就是解決作圖問題的一個算法列步驟就是解決作圖問題的一個算法. 變式遷移變式遷移4 已知點已知點P(x0,y0)和直線和直線l:AxByC0,畫出求點畫出求點P到直線到直線l的距離的距離d的框圖的框圖 解析解析 框圖如圖所示框圖如圖所示 題型五題型五 選擇結構選擇結構 例例5.任意給定任意給定3個正實數,試設計一個算法,判斷分別以這個正實數,試設計一個算法,判斷分別以這3個數為三邊邊長的三角形是否存在

47、,并畫出這個算法的框圖個數為三邊邊長的三角形是否存在,并畫出這個算法的框圖 分析分析 判斷分別以這判斷分別以這3個數為三邊邊長的三角形是否存在,只個數為三邊邊長的三角形是否存在,只需要驗證這需要驗證這3個數中任意個數中任意2個數的和是否大于第個數的和是否大于第3個數即可,這就個數即可,這就需要用到選擇結構需要用到選擇結構 解析解析 框圖如圖所示框圖如圖所示 點評點評 凡必須先根據條件作出判斷,凡必須先根據條件作出判斷,然后再決定執行哪一個步驟然后再決定執行哪一個步驟的問題,在畫框圖時,必須引入判斷框,利用選擇結構來設計算法的問題,在畫框圖時,必須引入判斷框,利用選擇結構來設計算法. 變式遷移變

48、式遷移5 畫出解關于畫出解關于x的不等式的不等式pxq0(p0)的框圖的框圖 解析解析 我們需要討論不等式中各個字母的符號,從而確定不等我們需要討論不等式中各個字母的符號,從而確定不等式的解集,也就是要考慮到解不等式的各種情況框圖如圖所示式的解集,也就是要考慮到解不等式的各種情況框圖如圖所示 題型六題型六 循環結構循環結構 例例6.設計算法求設計算法求S1(12)(123)的前的前10項和,項和, 畫畫出算法框圖出算法框圖 分析分析 循環變量:循環變量:i,每次遞增,每次遞增1,可用式子,可用式子ii1表示;表示; 循環體:第一個和求循環體:第一個和求123用用TTi表示,第二個和表示,第二個

49、和求全部的和用求全部的和用SST表示;表示; 循環的終止條件:循環的終止條件:i9. 解析解析 算法框圖如圖所示算法框圖如圖所示 點評點評 本題求和實質上是求了兩個和,注意循環體的設計方法本題求和實質上是求了兩個和,注意循環體的設計方法TTi,SST連續起來便得到了所求的和連續起來便得到了所求的和. 變式遷移變式遷移6 2222 畫出求畫出求s123100的值的算法框圖的值的算法框圖 解析解析 算法框圖如圖所示算法框圖如圖所示 題型七題型七 框圖的畫法框圖的畫法 例例7.若若135n2010,試設計算法框圖,試設計算法框圖,尋找滿足條尋找滿足條件的最小奇數件的最小奇數n. 解析解析 算法分析:

50、因為涉及累加問題,所以算法含有循環結算法分析:因為涉及累加問題,所以算法含有循環結構,寫出算法步驟如下:構,寫出算法步驟如下: 1S0,i1. 2SSi,ii2. 3判斷判斷S2010是否成立:是否成立: (1)若若S2010,則,則ii2,輸出,輸出i; (2)若若S2010,返回步驟,返回步驟2. 畫法步驟畫法步驟 畫順序結構圖,即起止框及兩個處理框,并分畫順序結構圖,即起止框及兩個處理框,并分別填入循環初始條件別填入循環初始條件(如圖所示如圖所示); 畫循環結構圖,先畫循環體即兩個處理框畫循環結構圖,先畫循環體即兩個處理框(一個累加,一個累加,一個一個計數計數),再畫循環終止條件,再畫循

51、環終止條件,即判斷框并判斷即判斷框并判斷S2010,若不成立,若不成立,則流向循環體進行再循環則流向循環體進行再循環(如圖所示如圖所示); 畫處理框并填入畫處理框并填入 “ii2”,輸出框輸出輸出框輸出n以及起止框表示以及起止框表示算法結束算法結束(如圖所示如圖所示 ) 最后,合成整個算法框圖如圖所示最后,合成整個算法框圖如圖所示 點評點評 畫框圖的關鍵是分析算法步驟,因為框圖是算法步驟的畫框圖的關鍵是分析算法步驟,因為框圖是算法步驟的圖形表示,所以算法步驟越明確畫圖就越容易;另外,如分段函數圖形表示,所以算法步驟越明確畫圖就越容易;另外,如分段函數這種需要對條件進行判斷的算法設計中,宜使用選

52、擇結構這種需要對條件進行判斷的算法設計中,宜使用選擇結構. 變式遷移變式遷移7 某商場進行優惠促銷:若購物金額某商場進行優惠促銷:若購物金額x在在500元以上,打元以上,打8折;折;若購物金額若購物金額x在在300元以上,打元以上,打9折;否則,不打折設計算法框折;否則,不打折設計算法框圖,要求輸入購物金額圖,要求輸入購物金額x,輸出實際交款額,輸出實際交款額 解析解析 算法分析:由題意,實際交款額算法分析:由題意,實際交款額y與購物金額與購物金額x之間的之間的? ?x x300? ?函數關系是函數關系是y? ?0.9x,300 x500,因為它需對因為它需對x進行三次判進行三次判? ? ?0

53、.8x, x500斷,所以算法含有兩個選擇結構,寫出算法步驟如下:斷,所以算法含有兩個選擇結構,寫出算法步驟如下: 1輸入購物金額輸入購物金額x. 2若若x300,則,則yx 3若若x300,判斷,判斷x500是否成立:是否成立: (1)若若x500,則,則y0.9x; (3)若若x500,y0.8x. 4輸出輸出y. 畫法步驟:畫順序結構圖,即起止框及輸入框,并用流程線畫法步驟:畫順序結構圖,即起止框及輸入框,并用流程線連接連接(如圖所示如圖所示); 畫選擇結構圖,即畫判斷框并判斷畫選擇結構圖,即畫判斷框并判斷x300,若是,則畫處理,若是,則畫處理框并填入框并填入“yx”,否則流向下一個判

54、斷框,否則流向下一個判斷框(如圖所示如圖所示); 再畫選擇結構圖,即畫判斷框并判斷再畫選擇結構圖,即畫判斷框并判斷x500,若是,則畫處,若是,則畫處理框并填入理框并填入“y0.9x”,否則畫處理框并填入,否則畫處理框并填入“y0.8x”(如圖所如圖所示示); 畫一個總的輸出框并輸出畫一個總的輸出框并輸出y,以及起止框表示算法結束,以及起止框表示算法結束(如圖如圖所示所示) 最后,合成整個算法框圖如圖所示最后,合成整個算法框圖如圖所示 題型八題型八 流程圖流程圖 例例8.某地聯通公司推出某地聯通公司推出10011電話服務,其中話費查詢業務流電話服務,其中話費查詢業務流程如圖所示:程如圖所示:

55、如果某人用手機查詢該機卡上余額,請畫出操作的流程圖如果某人用手機查詢該機卡上余額,請畫出操作的流程圖 解析解析 點評點評 確定工序的順序,選用相應的方案,畫出流程圖確定工序的順序,選用相應的方案,畫出流程圖. 變式遷移變式遷移8 某市環境保護局信訪工作流程如下:某市環境保護局信訪工作流程如下: (1)信訪辦受理來訪,一般信訪填單轉辦;重大信訪報局長批示信訪辦受理來訪,一般信訪填單轉辦;重大信訪報局長批示后轉辦后轉辦 (2)及時轉送有關部門辦理、督辦,如特殊情況未能按期辦理完及時轉送有關部門辦理、督辦,如特殊情況未能按期辦理完畢,批準后可延辦,辦理完畢后反饋畢,批準后可延辦,辦理完畢后反饋 (3

56、)信訪辦理情況反饋后,歸檔備查,定期通報信訪辦理情況反饋后,歸檔備查,定期通報 據上畫出該局信訪工作流程圖據上畫出該局信訪工作流程圖 解析解析 流程圖如圖所示:流程圖如圖所示: 題型九題型九 結構圖結構圖 例例9.某公司局域網設置如下:由服務器連接經理室、市場部、某公司局域網設置如下:由服務器連接經理室、市場部、銷售部、客戶服務部、系統管理員,與外部連接是通過服務器,試銷售部、客戶服務部、系統管理員,與外部連接是通過服務器,試畫出該公司局域網設置結構圖畫出該公司局域網設置結構圖 解析解析 如圖:如圖: 點評點評 在畫結構圖時要注意審題,確定名片定理系統的四個在畫結構圖時要注意審題,確定名片定理系統的四個功能,并對每個功能細分,然后畫出結構圖功能,并對每個功能細分,然后畫出結構圖. 變式遷移變式遷移9 在工商管理學中在工商管理學中MRP(Materia

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論