高中信息科技(選學模塊)的復習提綱算法與程序設計

1、優(yōu)秀學習資料歡迎下載高中信息科技（選學模塊）的復習提綱算法與程序設計1.1 使用計算機解決問題的一般過程（課本P35）1 .用計算機解決問題的步驟：分析問題設計算法 編寫程序 運行程序 問題解決分析問題：明確要計算機做什么設計算法：尋找到解決問題的途徑和方法，并把方法步驟化。編寫程序：選定編程語言，編制出相應的計算機程序。運行程序：讓計算機一步一步地執(zhí)行算法，以獲得問題所需的計算結果。2 .計算機程序：指示計算機如何去解決問題或完成任務的一組可執(zhí)行的指令。（了解）計算機科學克勞斯沃思指出：算法+數(shù)結構=程序3 .程序設計：尋求解決問題的方法，并將其實現(xiàn)步驟編寫成計算機可以執(zhí)行的程序的過程。4

2、.指令：用來規(guī)定計算機操作的命令。一條指令要求計算機執(zhí)行一個動作。5 .指令集：計算機的所有指令組成了計算機的指令集。6 .典型的計算機指令：輸入、輸出、數(shù)學運算、邏輯判斷、控制轉移指令7 . 一個程序由兩部分組成：指令部分和數(shù)據(jù)部分。指令部分是由一系列指令構成，描述解決這個問題的計算過 程。數(shù)據(jù)部分是用來存儲計算所需的原始數(shù)據(jù)、計算的中間結果或最終結果。8 .設計程序需要考慮的兩點：1.數(shù)據(jù)的存儲 2.計算的過程（不僅須指出動作，還須指出動作的次序）1.2 算法的概念（課本P6）1. （了解）算法的由來：由9世紀阿拉伯數(shù)學家花拉子密的名字；派生而來的，這位數(shù)學家一生發(fā)現(xiàn)了許多求解算術問題的方

3、法，并編寫了一本名為復原和化簡的規(guī)則的書。這本書后來翻譯成拉丁文，書名被簡化成 現(xiàn)在人們所熟悉的 代數(shù)學2. 算法的定義：解決問題的具體方法和步驟。即，在有限步驟內求解某一問題所使用的具有精確定義的一系 列操作規(guī)則。也可以說是：能夠清楚地表達解決問題的方法一步步是“怎樣做”的過程。3. 算法的特點：有窮性：執(zhí)行步驟有限、能夠終止或在合理的時間范圍內完成全部操作。（強調有限和合理間范圍）確定性：必須有確切的含義，不能含糊、模棱兩可?？尚行裕好總€步驟能夠在有限的時間內實際做到。有0個或多個輸入。有一個或多個輸出。1.3 算法的表示方法（課本 P8-9）1. 算法的表示方法：自然語言、流程圖、偽代碼

4、自然語言：通過文字或數(shù)學表達式來描述解決問題的過程。（缺點：容易產生二義性。）主要格式：（1）（2）（3）（4）流程圖：用直觀易懂的、圖形來描述算法的方法。最基本、常用的符號有：處理框匚二I:框中指出要處理的內容，該框有一個入口和一個出口。輸入、輸出框 /:用來表示數(shù)據(jù)的輸入或計算結果的輸出。判斷框c：用來表示條件判斷的情況，菱形框的四個頂點中，通常用上方的頂點表示入口，用另外三個頂點中兩個來表示出口。所以對于判斷框而言是一個入口，兩個出口。連接框o：用于連接因畫不下而斷開的流程線。流程線指出流程控制方向，即運作的次序。開始、結束符 GD：用來表示算法的開始或結束。一個算法只能有一個開始處，只

5、能有一個結束處。(書上說一個算法只能有一個開始處，但可以有多個結束處。這樣的說法是錯誤的。要更正)流程圖表示偽代碼：介于自然語言和計算機程序語言之間的一種算法描述，也是專業(yè)軟件開發(fā)人員描述算法的一種常用方法。輸入：read ()輸出：write () , print ()賦值：1.3.2 變量與表達式與2.3.1數(shù)組(變量與常量的概念參見學科要求P46,課本P9)常量：指在程序執(zhí)行過程中事先設置、其值不發(fā)生改變的量，即一個具體的數(shù)值。變量：指在程序運行過程中，取值可以改變的量，一般用字母表示。在計算機內部變量對應了一定的存儲單元。變量命名的基本規(guī)則1 .只能由字母、數(shù)字和下劃線三類字符組成，但

6、第一個字符必須是字母。變量名不能為程序設計語言中的 保留字(關鍵詞)。2 .字母大小寫都可以，變量名長度適當。3 .變量名與實際意義相符變量的特點：變量的值“取之不盡，一沖就丟”。變量賦值的格式：變量-表達式將賦值號右邊常量的值或變量的值存放到左邊變量名對應的存儲單元中，成為左邊變量的值。表達式：指用運算符將常量、變量連接起來有意義的式子。課本P59-60 算術表達式：用 算術運算符將常量、變量連接起來有意義的式子。課本 P59基本運算運算符優(yōu)先級范例攪達式范例表達式的 值乘嘉A125X55取加-2a日的相反教乘法n33*2 57.5實數(shù)除法/33/21.5整教除法4I求余數(shù)Mod58 mod

7、 5-7 mod 33-1加法+6a*bm與b的和醴-6a-b3與6的差 字符表達式：用字符運算符 將常量、變量連接起來有意義的式子。（優(yōu)先級數(shù)值大于算術表達式，也就是先做算術表達式，再做字符表達式）+:只能是兩個字符串間連接如，“123” + “589” = "123589”&:可以是字符串與另一種類型的數(shù)據(jù)相連接如，“123" &589= "123589”（優(yōu)先級數(shù)值大于算術表達式，也就是先做算術表達式，再做字符表達式）如，2X 3 & 23”=623注意在VB中使用附號時，一定要在&的前面和后面加上空格。 關系表達式：用關系運

8、算符將常量、變量連接起來有意義的式子。（課本P59）基本運算運算符優(yōu)先級范例表達式范例表達式 的值相等71990 mod 4=0Fa 1 se不相等<>7'aba'O'abd"T rue小干<75<10T rue大干>710>100Fa 1 se小干等于<=710<=20T rue大于等于>=710>=20Fa 1 se字符大小比較的實質是其對應以 ASCII碼大大小。因此字母排列在前的小，排列在后的大，例如：“a">“b",”m“>“g" 對于多個字母組成的

9、字符串比較大小，則是首先比較首字母，只有在首字母相同的情況下，才比較第2個字母的大小，依此類推。例如： "abc">"abb","dog"<"dogs"。P33.使用關系運算符和邏輯 邏輯表達式（課本 P60）基本運算運算符優(yōu)先級范例表達式范例表達式 的值非not8Not ；3>2)Fa 1 se與And9And <?5<=10DT rue或Or10<25>10fl> orFa 1 se注意：VB中使用算術運算符運算的結果是數(shù)值；使用字符運算符運算的結果是字符串;運算

10、符運算的結果是邏輯值，即：要么是 False,要么是True。VB中常用數(shù)學函數(shù)（課本 P84）函數(shù)名函數(shù)的功能說明應用舉例函數(shù)返回 值Ab呂3求x的絕對值Abs(-3. 1)3.11 nt (y)求不大于乂的最大整數(shù)1 nt (3. 1)1 nt _(-3, 1 )3-4Sqr(x)求乂的算術平方根Sqr'.4)Sqr(6)22 44948Exp (xi求自然底數(shù)電的，次方Exp（2）1. 3S9056Log iy)求以電為底的K的對數(shù)Log（3）1 098612S i n (浦求乂的正弦函數(shù)值Sin (3 141S9/2)0. 9999099Cos求'的余強函數(shù)值Cos(3

11、. 14159/3)0.4999999Tan (kI求X的正切函數(shù)值Tan(3 14159/4)0.9999099重點掌握前三個。需要理解課本 P84中：ab的表示exp（log（a）*b）和log ab的表示log （b） /log （a）VB中常用類型轉換函數(shù)和字符串函數(shù)P85函數(shù)名函數(shù)的功能說明應用舉例函數(shù)返回值Asc(x)字符轉換為ASCII碼值Asc( A”)65Chr(x)ASCII碼值轉換為字符Chr(65)A”Val(x)數(shù)字字符串轉換為數(shù)值Val( -1234”)-1234Str(x)數(shù)值轉換為字符串Str(-1234)-1234 ”Len(x)計算字符串的長度Len( he

12、llo")5Mid(x,n,k)從字符串x中的第n個字符起截取 長度為k的子串Mid( hello ”,3,3)llo”Fix(x)截掉數(shù)據(jù)的小數(shù)部分Fix(3.1415926)3計數(shù)器：（課本P10,學科要求P58）在算法執(zhí)行過程中，用來記錄某種事件發(fā)生次數(shù)的變量。一般用法：在算法準備階段中，應預置初值為0。即c=0在算法執(zhí)行過程中，每當指定的事件發(fā)生時，計數(shù)器計數(shù)，即把事件已發(fā)生的次數(shù)（計數(shù)器中的值）加1后，結果仍然送回計數(shù)器中。即 c=c+1.累加器：（課本P11,學科要求P59） 用來生成并存儲數(shù)據(jù)累加的變量。一般用法：在求和開始前的準備階段中，應預置初值0,即sum=0在算

13、法執(zhí)行過程中，每遇到一個符合要求的數(shù)據(jù)時，把這個數(shù)據(jù)累加到累加器中，即計算累加器與數(shù)據(jù)之和，并把結果重新存儲到累加器中。即 sum=sum+a累乘與累加的操作相似。（學科要求P59）一般用法是：在求積開始前的準備階段中，應預置初值1,即s=1算法執(zhí)行過程中，每遇到一個符合要求的數(shù)據(jù)時，把這個數(shù)據(jù)累乘到累乘器中，即計算累乘器與數(shù)據(jù)之積，并把結果重新存儲到累乘器中。即 s=s*d.循環(huán)變量：用于控制循環(huán)的變量。數(shù)組（學科要求 P79-80,課本P27）特殊、有用的變量。規(guī)模為n的數(shù)組變量是由n個普通變量組成的，通常把組成數(shù)組的變量稱為數(shù)組元素，一個數(shù)組變量中的所有元素擁有一個共同的名稱，通過下標（

14、一個從1n范圍內的整數(shù)值）指出數(shù)組變量中的特定元素。實際上，下標指出了一個數(shù)組元素在數(shù)組變量中的位置。通常用數(shù)組變量來存儲一批類型、作用相同的數(shù)據(jù)。1.3.3 算法的執(zhí)行流程算法中各個處理步驟的執(zhí)行次序和模式。 順序模式（順序結構）特點：執(zhí)行完一個處理步驟（step1 ）后，順序執(zhí)行下一個處理步驟step2一個入口，一個出口選擇模式（分支結構）特點:對某種懵況e進行判斷，當結果為真時，執(zhí)行處理步驟step1 ,否則執(zhí)行處理步驟step2。雙分支結構單分支結構stepl一個入口VB個人口VBIf條件ThenStepl（即條件為真時的語句）ElseStep2（即條件為假的語句）End IfIf條件

15、ThenStepl（即條件為真時的語句）End If一個出口注意：在這個結構中通過 Els就已說明了是條件成立 的情況，所以就不需要再 對條件進行判斷了。工一個出口注意：若結構圖中出現(xiàn)的 是：當條件為假時執(zhí)行語 句，那么在寫VB時，需要 把條件換成相反意思。重復模式（循環(huán)結構）對某個條件進行判斷，當結果為真時，執(zhí)行一些語句，然后再次判斷這個條件，當結果仍為真時，再次 執(zhí)行一些語句，并繼續(xù)判斷條件。總是重復上述過程，直到情況判斷的結果為假。直到型循環(huán)結構當型循環(huán)結構:VB:Do while循環(huán)條件循環(huán)體（即當循環(huán) 條件為真時執(zhí)行）Loop后續(xù)步驟（即，當循環(huán) 條件為假時，也就是出 口連接著的步驟

16、，寫在 這里）VB :（把結構改成當型 循環(huán)結構）循環(huán)體（第一遍）Do while此結構圖中循環(huán)條件相反意思循環(huán)體（即當循環(huán) 條件為真時執(zhí)行）LoopVB :（直到型循環(huán)結 構語句）Do循環(huán)體（即當循環(huán)條件 為假時執(zhí)行）Loop Until 此結構圖中循環(huán)條件1）先判斷，后執(zhí)行循環(huán)體2）循環(huán)體執(zhí)行的循環(huán)次數(shù) 可能是0次或多次注意：若結構圖中出現(xiàn) 的是：當條件為假時執(zhí) 行循環(huán)體，那么在寫 VB時，需要把循環(huán)條 件換成相反意思。1）先執(zhí)行循環(huán)體，后 判斷2）循環(huán)體執(zhí)行的循環(huán) 次數(shù)至少是1次或多次每個算法都是這三種模式（結構）的任意組合。控制循環(huán)的幾種常用方法（學科要求P57）1）計數(shù)法：一般用于在

17、循環(huán)次數(shù)確定的情況下。采用一個變量，通過對該變量的計數(shù)來控制循環(huán)的次數(shù)。 當達到要求的循環(huán)次數(shù)后適時地退出循環(huán)，這樣的變量稱為循環(huán)變量。循環(huán)變量的初值、終值和步長的設 定與循環(huán)次數(shù)相關。 有時，循環(huán)變量還參與其他運算。通常使用計數(shù)器來記錄循環(huán)體執(zhí)行次數(shù)并控制循環(huán)執(zhí)行情況。2）標志法：對于不確定循環(huán)次數(shù)的算法，往往用設置標志性條件的方法來控制循環(huán)。設置標志性條件的方法通常有：以循環(huán)體中某個或幾個變量滿足規(guī)定條件作為循環(huán)結束的標志;優(yōu)秀學習資料歡迎下載以輸入某個特殊的數(shù)據(jù)作為結束循環(huán)的標志。循環(huán)結構中容易出現(xiàn)的問題（學科要求P57-58）死循環(huán)；隨意改變循環(huán)體中各操作的執(zhí)行次序。分析循環(huán)結構的算法

18、的運行結果（學科要求P56）列表法；功能分析法。三種模式的應用。（學科要求P59-73）基本算法實例2.1解析算法（課本P18,學科要求P79）用解析的方法找出表示問題的前提條件與結果之間關系的數(shù)學表達式，并通過表達式的計算來實現(xiàn)問題求解。解析算法最關鍵的有兩步（1）確定使用哪種執(zhí)行流程來完成。（解析算法的結構：可能是順序結構（課本例 1）,也可能是順序結構和分支結構的組合（例2）,也可能是順序結構和循環(huán)結構的組合（例3）,也可以是三種結構的任意組合；這完全取決于問題本身。）（2）確定條件與結果之間的表達式。解析法的特點解析法的應用解析法的實現(xiàn)2.2枚舉算法（課本P22,學科要求P75-79）

19、采用一種盲目的搜索方法，在搜索結果的過程中，把各種可能的情況都考慮到，并對所得的結果逐一進行判斷, 過濾掉那些不合要求的，保留那些符合要求的，這種方法叫做枚舉算法。七重否列舉顯束*在列舉過程中，既不能遺漏，也不應該重復?；窘Y構：枚舉算法最關鍵的有三步（1）確定列舉的范圍。（2）確定滿足篩選的條件。（3）確定循環(huán)控制方式和列舉方式枚舉法的特點枚舉法的應用枚舉法的實現(xiàn)注意：枚舉算法的優(yōu)缺點（學科要求P77）:枚舉法充分利用了計算機快速高效的特點，讓計算機將所有可能的解無一例外地進行檢驗，因此列舉正確，枚舉法具有非常高準確性和全面性；也決定了其局限性-效率不高。當算法花費的時間過長時，這樣的枚舉算

20、法是沒有實際意義的。2.4查找（課本P34）一種查詢數(shù)據(jù)或信息的技術，其目標是能以比較少的步驟或較短的時間找到所需的對象。在課本中是指以在程 序的某個數(shù)組變量中存儲的一批數(shù)據(jù)內，尋找出特定的一個數(shù)據(jù)，或者確定在該數(shù)組內無這樣的數(shù)據(jù)，來作為 查找的目的。查找方法很多，除了順序查找、對分查找，還有樹形查找等等。順序查找（課本P34,學科要求P81）用待查關鍵字（查找鍵）和已知的數(shù)據(jù)逐個比較，直到找到與查找鍵值相等的值，即查找成功；或查完全部已 知數(shù)據(jù)，而未找到查找鍵字相等的值，即為查找失敗。順序查找的原理順序查找的算法（課本P35+課堂上對其修改，學科要求 P81）順序查找的實現(xiàn)對分查找（課本P3

21、5,學科要求P81）優(yōu)秀學習資料歡迎下載在有序數(shù)據(jù) 中，采用查找鍵與有序數(shù)據(jù)內處于中間位置的元素進行比較，如果中間位置上的元素的數(shù)值與查找 鍵不同，根據(jù)數(shù)據(jù)元素的有序性，就可以確定應該在數(shù)組的前半部分還是后半部分繼續(xù)進行查找；在新確定的 范圍內，繼續(xù)按上述方法進行查找，直到獲得最終結果。對分查找的原理對分查找的算法（課本P35+課堂上對其修改）對分查找的實現(xiàn)2.3排序（課本P29,學科要求P80）把雜亂無章的數(shù)據(jù)變成有序（遞增/遞減）數(shù)據(jù)的過程。冒泡排序把待排序的n個元素的數(shù)組看成是垂直堆放的一列數(shù)據(jù)。從最下面的一個元素起，自下而上比較相鄰的兩個元素中的數(shù)據(jù)，將數(shù)值最小的數(shù)據(jù)換到上面的一個元素 中。重復這一過程，直到處理完最后兩個元素中的數(shù)據(jù)，稱為一遍加工。當?shù)谝槐榧庸ね瓿蓵r，最小的數(shù)據(jù)已經上升到第一個元素的位置。然后對余下的n-1個元素重復上述處理過程，直至最后進行余下兩個數(shù)據(jù)的比較和交換。冒泡排序的原理冒泡排序的算法（課本P32+課堂上的整理）冒泡排序的實現(xiàn)【選擇排序】是在參加排序的所有數(shù)組元素中找出最?。ɑ蜃畲螅?shù)據(jù)的元素，使它與第一個元素中的數(shù)據(jù)相互交換位 置，然后再在余下的元素中找