文章目錄：

一：基本概念

1.算法與程序

1.1 算法?

1.2 程序

2.編譯預處理

3.面向對象技術

4.程序設計方法

5.SOP標志作業流程

6.工具

6.1 自然語言

6.2 流程圖

6.3 N/S圖

6.4 偽代碼

6.5 計算機語言

二：程序設計 基礎

1.常數

2.變量

3.運算符

4.表達式

5.函數

6.循環

6.1 順序結構

6.2 選擇結構

6.3 循環結構

6.3.1 當型和直到型?

6.3.2 循環四要素

6.3.3 循環的分析

三：程序設計 算法

1.數值

1.1 迭代

1.2 數論

1.2.1 取數

1.2.2 進制轉換

1.2.3 素數

2.非數值

2.1 枚舉

2.2 數組

2.2.1 基礎

2.2.2 CEUD

2.2.3 進階

2.3 字符串

3.優化

3.1 算法的性能

3.2 算法的優化

---

可參考：VB(Visual Basic)程序設計教案、C編程語言、C++程序設計教案、Python程序設計教案、Java編程語言、數據結構

一：基本概念

1.算法與程序

1.1 算法?

算法的基本概念概念算法就是解決問題的?法和步驟，解決問題的過程就是算法實現的過程在數學中，算法（Algorithm）通常是指按照?定規則解決某?類問題的明確和有限的步驟算法是解決?類問題的?法，可以理解為由基本運算及規定的運算符順序所構成的完整和有限的解題步驟分類根據處理的數據是數值數據還是?數值數據，可以分為數值計算算法和?數值計算算法兩?類數值計算算法?于科學計算，其特點是少量的輸?、輸出，復雜的運算，例如求?次?程的近似根、求函數的定積分、求圓周率等?數值計算算法?于數據管理，其特點是?量的輸?、輸出，簡單的算術運算和?量的邏輯運算，例如對數據的排序、查找等算法說明算法決定程序，是程序設計的核?算法通常?于解決?類問題而不是專?針對某?個具體的問題?種問題通常有很多種不同的解決辦法（算法），采?不同的算法效率不同算法的兩?要素操作：包括算術運算、關系運算、邏輯運算等運算符，以及?于實現數據傳送的操作，包括輸?、輸出、賦值等結構：即控制結構，包括順序結構、選擇結構和循環結構三種基本結構算法的五?特性：著名計算機科學家Donald E.Knuth把算法的性質歸納為5點有窮性 ?叫有限性，即算法在執?有窮個計算步驟后必須終?確定性 ?叫??義性，即每?個計算步驟必須是精確地定義，要執?的每?個動作都是清晰的、?歧義的可?性 ?叫能?性，即算法中的運算都是基本運算，原則上可以由?們?紙和筆在有限的、合理的時間內精確地完成輸? ?個算法有0個或多個輸?，作為算法開始執?前的初始值，或初始狀態輸出 ?個算法有1個或多個輸出，即算法必須有輸出

1.2 程序

程序的基本概念①程序是計算機為完成某?任務所必須執?的?系列指令的集合包含?量重復性的、事務性的操作的任務適合編程解決，創造性的任務不適合編程解決計算機系統能完成各種?作的核?是程序，而程序的核?是算法，編寫程序的過程稱為程序設計，設計算法是程序設計的關鍵②?個程序包含兩??的內容：對數據的描述和對操作的描述著名計算機科學家沃思（Nikiklaus Wirth）提出的經典公式：程序 = 數據結構 + 算法數據結構指定待處理數據的數據類型和數組的組織形式，算法描述對數據進?操作的?法和步驟③?個完整的程序除了以上兩個必備要素之外，還應當采??定的程序設計?法進?設計，并?某種計算機語?來表?因此，也可表述為：程序 = 數據結構 + 算法 + 程序設計?法 + 語??具和環境程序設計的流程步驟分析問題在開始解決問題之初，?先要弄清楚所求解問題相關領域的基本知識分析題意，搞清楚問題的含義，要解決的問題的?標，問題的已知條件、已知數據以及應該得到什么樣的結果數學建模 建?計算機可實現的計算模型，也就是把實際問題轉化為數學問題，直到得到求解問題的公式算法設計 算法是求解問題的?法和步驟，算法設計即設計從給定的輸?到期望的輸出的處理步驟編寫程序 選擇某種程序設計語?，按照設計的算法和選擇的語?的語法規則編寫程序測試運?設計測試數據（測試?例），盡可能多地找出程序中的錯誤測試以程序通過編譯，沒有語法上的錯誤為前提說明①算機求解問題的過程可以?致分成兩步：抽象和?動化在計算機科學中，抽象是簡化復雜的現實問題的最佳途徑，包含形式化和數學建模兩個要素形式化是指采?嚴格的數學語?描述清楚問題的條件、?標以及達到?標的過程的數學?法數學建模是以數學的?法來求解問題和描述系統?為的?種形式化?法計算機通過程序實現?動化，程序的核?是算法，?動化分兩步：設計算法和編寫程序②問題的復雜程度決定了程序的復雜程度分析問題時，?般需要和提出問題的?進?討論，搞清楚程序的功能，這個過程稱為需求分析③如果時間緊迫，可以選擇開發效率?或??熟悉的語?，例如Visual Basic語?如果要求在多種平臺上使?，可以選擇移植性好的語?，例如Java語?如果對程序響應要求?，可與選擇運?效率?的語?，例如C語?④證明程序的正確性是極為困難的，?較實?的?法就是測試測試的?的是找出錯誤，調試的?的是解決錯誤

2.編譯預處理

概念：編譯預處理即在編譯之前對源程序進?的處理，源程序 → [預處理] → [編譯] → ?標代碼包括?件包含 在?個源?件中插?另?個源?件的全部內容，例如“#include <stdio.h>”常量替換 ?叫宏定義，即將程序中所有宏名替換成宏定義（#define）中的內容條件編譯 在編譯前，按照條件篩選出源程序中的部分代碼，再進?編譯

3.面向對象技術

對象概念對象是類的實例化對象是現實世界中可以獨?存在、可以區分的實體，也可以是?些概念上的實體對象可以?對象名、屬性和?法來描述描述對象名：每個對象區別于其它對象的名字，具有唯?性屬性：??組狀態（屬性值）來描述的對象的靜態特征，即對象擁有的數據?法：對屬性的各種操作，每?個操作決定對象的?種功能或?為消息消息是對象之間相互請求和相互協作的?段，是激活某個對象執?其中某個功能的“源”對象之間的相互作?通過消息傳遞來實現，即對象之間的聯系是通過消息傳遞的事件事件就是?些能夠激活對象功能的動作，不同的事件往往引發對象不同的動作??按鍵、移動?標、單擊?標、打開?件、關閉?件等都是發?在計算機上的事件事件驅動在傳統的?向過程的應?程序中，程序執?的先后次序由設計?員編寫的代碼決定，???法改變程序的執?流程在?向對象的程序設計中，程序是由若?個規模較小的事件過程組成，特定事件的發?將引發對象執?相應的事件過程程序的執?由事件的發?驅動，編寫好的?段程序并不總是能夠被執?，只有當對應的某?事件發?才執?這段程序特征封裝將對象的屬性和?法封裝成?個整體，使對數據的操作只可通過該對象本?的?法來進?封裝是?種信息隱蔽技術，A對象不能直接操作B對象的數據，只能通過B對象提供的?法來實現繼承使?已存在的類作為基礎建?新類的技術，新的類可以增加新的屬性或新的?法，也可以直接使??類的屬性和?法繼承是?種代碼復?技術多態同?消息被不同對象接收時，可以解釋為不同的含義即相同的操作可作?于多種類型的對象，并能獲得不同的結果

4.程序設計方法

概念?前最常?的是結構化程序設計?法和?向對象的程序設計?法程序設計的?法在很?程度上影響到程序設計的成敗和程序的質量程序的可靠性（魯棒性）、易讀性、?效性和可維護性是衡量程序質量的重要特性結構化程序設計概念結構化程序設計的概念最早由荷蘭科學家E.W.Dijkstra提出在軟件設計和實現過程中，提倡采?“?頂向下、逐步細化”的模塊化程序設計原則在代碼編寫時，強調采?單?口、單出口的3種基本控制結構，避免使?goto語句優點結構簡單清晰，可讀性好，模塊化強，符合?們解決復雜問題的普遍規律在軟件重?性、軟件維護等??有所進步，可以顯著提?軟件開發的效率在應?程序的開發種發揮了重要作?缺點難以適應?型軟件的設計，程序和數據分開存儲，在開發中容易出錯，難以維護程序可重?性差，即使?對?問題，數據類型的變化或處理?法的改變都將導致重新設計?向對象程序設計概念20世紀80年代時提出，以滿?現代化軟件開發的要求??向對象的?法解決問題，不再將問題分解為過程，而是將問題分解為對象?前，“對象+消息”的?向對象的程序設計模式有取代“數據結構+算法”的?向過程的設計模式的趨向過程?向對象分析(OOA)Object Oriented Analyzing，是?種軟件開發過程分析的?法學把軟件開發過程中的每?樣東西都想象成類，OOA主要關?怎樣導出系統需要的類?向對象設計(OOD) Object Oriented Designing，該階段的焦點是OOA階段確定的類如何實現功能的問題?向對象實現(OOP)Object Oriented Programming，即采?某種?向對象語?具體實現OOD的設計常?的?向對象的程序設計語?有C++/C#、Java、Visual Basic、Python等說明?向對象的程序設計并不是要拋棄結構化程序設計?法，而是站在更?、更抽象的層次上解決問題當所要解決的問題被分解為低級代碼模塊時，仍需要結構化編程的?法和技巧?向對象程序設計分解?問題為小問題時采取的思路于結構化?法不同區別結構化的分解突出過程，強調代碼的功能是如何得以完成?向對象的分解突出真實世界和抽象的對象，涉及哪個對象的功能，便由哪個對象??去處理不同對象之間通過消息或事件發?聯系，對象依據接收到的消息或事件進??作優點符合?們習慣的思維?法，便于分析復雜而多變化的問題易于軟件的維護和功能的增減可重?性好，能?繼承的?式尖端程序開發所?的時間與可視化技術相結合，改善了?作界?

5.SOP標志作業流程

畫流程圖 代碼生成流程圖 流程圖自動運行?

Standard Operating Procedure，SOP，標準作業流程程序設計有?個標準化的流程，按照?唐總結的流程，可以確保每?位考?都能寫出程序，?少能搭建起程序的基本框架

6.工具

算法的表??法有很多，常?的有?然語?、程序流程圖、N/S圖、偽代碼和計算機程序設計語?等

6.1 自然語言

??們使?的語?，即?然語?來描述算法通俗易懂，但存在如下缺陷① 易產?歧義，即存在?義性，往往需要根據上下?才能確切判別含義，不太嚴格② 語句?較繁瑣、冗?，并且很難清楚地表達算法的邏輯流程，尤其對描述含有選擇和循環結構的算法時，不太?便和直觀

6.2 流程圖

流程圖是描述算法的常??具，采??些圖框、線條以及?字說明來形象、直觀地描述算法處理過程

6.3 N/S圖

N/S圖是?種簡化的流程圖，去掉了流程圖中的流程線，全部算法寫在?個矩形框內N/S圖表?算法直觀、形象，且?流程圖緊湊易畫，實際應?中也經常采?

6.4 偽代碼

由于繪制流程圖較為費時，?然語?易產?歧義和難以清楚表達算法的邏輯流程等缺陷，可以選擇使?偽代碼描述算法偽代碼（Pseudo-Code）使?介于?然語?和計算機程序設計語?之間的?字和符號來描述算法，有如下簡單約定偽代碼中的約定① 每個算法?begin開始，以end結束，若僅表?部分實現代碼可省略② 每?條指令占??，指令后不跟任何符號③ “//”標志表?注釋的開始，?直到?尾④ 算法的輸?輸出以“input/print”后加參數表的形式表?⑤ ?“←”表?賦值⑥ ?縮進表?代碼塊結構，包括while和for循環、if分?判斷等，塊中多條語句??對“{}”括起來⑦ 數組形式為“數組名[下界...上界]”，數組元素為“數組名[序號]”⑧ ?些函數調?或者處理簡單任務可以??句?然語?代替    

6.5 計算機語言

計算機?法識別?然語?、流程圖、偽代碼，這些?法僅為了幫助?們描述、理解算法只有?計算機語?編寫的程序才能被計算機執?（當然還要被編譯成?標程序）?計算機語?描述算法必須嚴格遵循所選擇的編程語?的語法規則

二：程序設計 基礎

1.常數

概念：程序運?的過程中，其值保持不變的數據數值型：可以進?算術運算的數字，例如3.14、1、-3、...字符型：?稱為字符串，由英?字符、中?字符和數字字符組成① 字符串?般使??對雙引號括起來，單個字符可以使??對單引號② 字符的個數 ?稱為字符串的?度，即字符串中包含的字符的個數字符的位置 從左?右，依次編號為1、2、3、...邏輯型?元邏輯，即只有true（邏輯真）和false（邏輯假）兩個值關系成?返回邏輯真，關系不成?返回邏輯假

2.變量

概念：程序運?的過程中，其值可以改變的數據說明① 在程序中，變量 = 可存放數據的容器② 變量只能保存?個數據，后存?的數據會替換現有的數據變量當前保存的數據的類型決定變量的數據類型③ 變量必須初始化，即變量必須先寫后讀操作寫：把?個數保存到變量中，賦值語句中賦值符號左邊的變量和輸?語句中的變量是在執?寫操作讀：讀出變量當前的值，程序中出現的變量不是在執?寫操作就?定是在執?讀操作

3.運算符

概念運算符是完成數據處理的最基本單位不同類型的數據，使?不同類型的運算符進?處理除了not是單?運算符之外，其它所有的運算符都是雙?運算符分類數值運算符+(加)、-(減)、*(乘)、/(除)、^(乘?)、%(取余)數值運算符?于處理數字型的數據，處理的結果也是數值型字符運算符+(連接)，相當于Excel或Access中“&”運算符的功能字符運算符?于處理字符型的數據（?少其中?個是字符型），處理的結果也是字符型關系運算符<(小于)、<=(小于等于)、=(等于)、!=(不等于)、>=(?于等于)、>(?于)關系運算符兩端的數據類型必須相同，處理的結果是邏輯型，邏輯真表?關系成?，邏輯假表?關系不成?邏輯運算符not(?)、and(與)、or(或)邏輯運算符?于處理邏輯型的數據，處理的結果也是邏輯型

4.表達式

概念：表達式是由數據、運算符和函數組成的?個整體，它是程序中完成數據轉換的表達?式分析：分析表達式的關鍵是理解運算符的優先級和結合性優先級：數值運算符 > 字符運算符 > 關系運算符 > 邏輯運算符數值運算符中，乘?(^)的優先級最?，其次是乘(*)、除(/)、求余(%)，最后是加(+)和減(-)所有的關系運算符的優先級都相同邏輯運算符中，邏輯?(not)的優先級最?，其次是邏輯與(and)，最后是邏輯或(or)結合性：當運算符的優先級相同時，決定運算的先后次序的就是結合性右結合 單?運算符(not)是右結合，即從右?左依次運算，例如not not true = not (not true) = not false = true左結合 所有的雙?運算符都是左結合，即從左?右依次運算，例如4/2*3 = (4/2)*3 = 6常見奇偶性     x%2=0 如果返回true，表?x是偶數，否則表?x是奇數整除       x%y=0 如果返回true，表?x能被y整除，否則表?x不能被y整除整數判定    x=floor(x) 如果返回true，表?x是整數，否則表?x不是整數區間x>a and x<b   如果返回true，表?x∈(a,b)區間，否則表?x不在(a,b)區間內x>=a and x<b  如果返回true，表?x∈[a,b)區間，否則表?x不在[a,b)區間內x>a and x<=b  如果返回true，表?x∈(a,b]區間，否則表?x不在(a,b]區間內x>=a and x<=b 如果返回true，表?x∈[a,b]區間，否則表?x不在[a,b]區間內否定原則：需要表?“否定”邏輯時，最好先表達“肯定”的邏輯，然后使?not運算符否定整體例如x能被a和b同時整除 x%a=0 and x%b=0x不能被a和b同時整除 not (x%a=0 and x%b=0)

5.函數

概念函數是?個獨?的功能模塊，與運算符?樣，?于完成數據處理偽代碼中并未限定可以使?的函數的功能和類型，?般情況下，這?介紹的函數可以直接使?說明函數調?的?般格式為：函數名(參數1, 參數2, ..., 參數n)函數的功能，就是把輸?數據（參數）轉換成對應的輸出數據（返回值）常?數值函數下取整函數 floor(x) 返回x的整數部分，例如floor(3.999)的結果為3絕對值函數 abs(x) 返回x的絕對值，例如abs(-1)的結果為1平?根函數 sqrt(x) 返回x的平?根，例如sqrt(4)的結果為2最?值函數 max(x,y) 返回x和y中?的那個最小值函數 min(x,y) 返回x和y中小的那個字符函數字符串?度 length_of(x) 返回字符串x的?度，即字符串x中包含的字符的個數，數值型ASCII碼to_ascii(x) 返回單個字符x對應的ASCII碼值，數值型to_character(x) 返回數值x對應的ASCII碼字符，x的值在0~255之間，字符型

6.循環

結構化程序設計的概念最早由荷蘭科學家E.W.Dijkstra提出任何程序都可由三種基本結構，即順序、選擇和循環結構組成，程序具有模塊化特征，每個程序模塊具有唯?的?口和出口

6.1 順序結構

概念：順序結構是最簡單、最常?的?種結構，計算機按照語句出現的先后次序依次執?賦值語句 x ← 表達式：先計算賦值號(←)右邊表達式的值，然后將其保存到賦值號左邊的變量中?增 x ← x + 1 先讀出x的值，加1后，寫回到x交換① t ← x② x ← y③ y ← t輸?語句 input x, y, ...運?時，??輸??組數據，依次保存到變量x、y、... 中輸?與賦值都可以完成對變量的寫操作，使?輸?語句可以由??在程序運?時決定變量的值輸出語句 print x, y, ...運?時，依次將變量x、y、... 中保存的值輸出到屏幕上?個完整的程序必須包含輸出語句，?少有?個輸出

6.2 選擇結構

概念：根據判定的結果（條件成?或不成?），選擇其中?條分?執?，因此?稱為分?結構包括：單分?、雙分?、多分?

6.3 循環結構

6.3.1 當型和直到型?

?

概念：計算機與?處理問題最?的特點，是計算機可以永不疲勞地重復算法所設計的操作，這通過循環結構來實現包括：當型、直到型

6.3.2 循環四要素

????????

6.3.3 循環的分析

說明：分析程序的關鍵就是分析循環，讀懂了循環也就讀懂了程序?法① 始于變量終于變量，即分析循環時，重點在搞清楚變量的值的每?步的變化過程② 從特殊到?般，通過觀察變量值的變化，總結出變量值的?般性的變化規律③ ?定要分析“最后?次滿?循環條件”時，循環的執?過程④ 對于?重循環，固定外層循環變量的值，可以化?重循環為單循環

三：程序設計 算法

1.數值

1.1 迭代

概念：迭代法?稱遞推法，是利?問題本?所具有的某種遞推關系求解問題的?種?法① 從初值出發，歸納出新值與舊值間直到最后值為?存在的關系② 從而把?個復雜的計算過程轉化為簡單過程的多次重復，每次重復都從舊值的基礎上遞推出新值，并由新值替代舊值計數說明：記錄在循環的過程中，某個條件滿?的次數?法① 在循環開始前，把某個變量的初始值賦值為0，例如“c←0”② 在循環體中，滿?條件時，讓c的值?增1，例如“c←c+1”求和說明：?稱累加和，即n項求和分類① n已知，求s 例如，s=1+2+3+...+n，當n=100時，求s② n未知，求s 例如，s=1+1/2+1/3+...+1/n，直到最后?項小于0.003為?，求s③ s已知，求n 例如，s=1+2+3+...+n，當s等于300時，求n?法① 初始化：循環開始前，把某個變量的初始值賦值為0，例如“s←0”② 找通項：所謂通項就是能代表累加和中每?項的表達式s=1+2+3+...+n，通項為i，i∈[1,n]s=1+1/2+1/3+...+1/n，通項為1/i，i∈[1,n]s=x+x^2/2+x^3/3+...+x^n/n，通項為x^i/i，i∈[1,n]③ 迭代 在循環體中，執?“s←s+通項”④ 常數項：單獨處理常數項，?般可以把常數項作為s的初始值，即“s←常數項”s=1+1+2+3+...+n，通項為i，i∈[1,n]，第?個1為常數項此時，在循環開始前，可以把s的初始值賦值為1，即“s←1”累乘：?稱累乘積，即n項求積，例如求k的階乘：k!=1*2*3*...*k與“求和”的?法相似，兩點區別① 初始化時，把某個變量的初始值賦值為1，例如“k←1”② 在循環體中，執?“k←k*通項”數列概念：?組有規律變化的數據常?等差數列 形如“1、2、3、...”等?數列 形如“1、2、4、8、...”斐波拉契數列 f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)(當n>=3時)?法：找出迭代（遞推）公式，有必要時可借助數組，以簡化迭代關系其它：包括復息利率、輾轉相除、猴?摘桃、?次?程求根等問題

1.2 數論

1.2.1 取數

概念：取出?個正整數的每?位公式：floor(n/m)%10m=1時，取n的個位數m=10時，取n的?位數m=100時，取n的百位數

1.2.2 進制轉換

概念：通常是2、8、10、16進制的整數的相互轉換?法10→R 除R逆序取余R→10 按權展開，乘權求和

1.2.3 素數

概念：素數?叫質數，即只能被1和??整除的正整數注意1不是素數，2是最小的素數，也是唯?的偶素數按定義，當n>=3時，不能被2~n-1中的任何?個數整除的數就是素數事實上，數論學家研究發現，只要n不能被2~sqrt(n)之間的數整除，n就是?個素數

2.非數值

2.1 枚舉

概念枚舉法?稱為窮舉法或試湊法，它是?種?較耗時的算法，需要利?計算機快速運算的特點實際上，橘?分堆、物不知數、韓信點兵、百錢百雞、素數判定、數組和字符串的遍歷等，都是枚舉法的應??法① 采?搜索的?法，根據題?的條件確定解的?致搜索范圍（解空間）② 把解空間內所有可能的情況逐?驗證，直到所有情況驗證完③ 若某個情況符合題?的條件，則為本題的?個答案；若全部情況驗證完后均不符合題?的條件，則問題?解說明① 枚舉法能有效解決問題的關鍵在于確定搜索的范圍和確定解應該滿?的條件② 枚舉法解決問題效率不?，因此，為提?效率，根據解決問題的情況，應該盡量減少內循環層數或每層循環的次數③ 對某類特定問題，在規模較小的情況下，枚舉法往往是?個簡單有效的?法

2.2 數組

2.2.1 基礎

初始化概念：數組是?組有序的變量，在使?前，需要為數組中的每?個變量賦初始值，這個操作稱為“初始化”包括數組已知，則可以直接使?數組，?需進?初始化數組未知，則在遍歷過程中，對數組中的每個變量執?輸?或賦值字符串可以理解為?個字符數組，題?中已知的字符串可以直接當作?個字符數組使?說明①組成數組的變量稱為數組中的數據元素組成數組的變量的個數稱為數組的?度或?小，記為N②數組中變量的位置稱為“下標”數組中的每個變量都可以使?“數組名[下標]”的?式進?引?下標如果從0開始，則數組中每個變量的位置可標記為：0、1、2、...、N-1如果從1開始，則數組中每個變量的位置可標記為：1、2、3、...、N③可以把字符串理解為?個字符數組，下標通常從1開始遍歷假設數組a的?度為N，所謂“遍歷”，即在?個循環中，依次訪問a[1]~a[N]遍歷的?向可以從左?右，也就是從a[1]→a[N](或a[0]→a[N-1])，也可以從右?左，即從a[N]→a[1](或a[N-1]→a[0])所謂“訪問”，即執?對變量的“讀”或“寫”

2.2.2 CEUD

增在數組中的指定位置插??個變量，插?變量后，數組的?度加1插?位置右邊的所有變量需要依次向右移動1位刪在數組中的指定位置刪除?個變量，刪除變量后，數組的?度減1刪除位置右邊的所有變量需要依次向左移動1位改將數組中指定位置的變量的值修改為?標值，不影響數組的?度如果要把數組中的某個值或某些值修改為?標值，可以先使?“查”，找到對應的值后，再修改在遍歷數組的過程中，實現數組元素的兩兩交換，也屬于“改”的范疇查：找到并返回數組中的某個值或某些值在數組中的位置順序查找概念：適?于“?序”數組，查找效率較低，n個數的平均查找次數為(n+1)/2?法：從左?右或從右?左依次遍歷數組，將其中的每?個值取出與?標值?較?分查找概念?叫“折半查找”，要求數組有序，即適?于“有序”數組?分查找是對數據量很?時采?的?種?效查找算法，n個數的平均花費為log2(n)?法① 已知待查找數組的下界low、上界high，數組升序有序② 當high>=low時，計算中間項mid=(low+high)/2下取整若high<low，則說明查找不成功，結束查找③ ?較待查找的關鍵字key與中間項a[mid]，有以下三種情況Ⅰ key>a[mid]，則low←mid+1，即右半部分作為繼續查找的區域，返回②Ⅱ key<a[mid]，則high←mid-1，即前半部分作為繼續查找的區域，返回②Ⅲ key=a[mid]，則查找成功，結束查找

2.2.3 進階

統計：統計數組中滿?條件的對象的個數、和、平均值等最值概念找到數組中的最?值或最小值（或最?值、最小值的位置）在數組中，“位置”?“值”更重要，知道位置可以直接得到對應的值?法：依次?較法循環開始前，m ← 1遍歷數組，i∈[2,N]如果a[m]<a[i]，m←i m表?當前已經?較過的i個數中最?值的位置如果a[m]>a[i]，m←i m表?當前已經?較過的i個數中最小值的位置完成遍歷后，m即為數組中最?值（最小值）的位置，a[m]是最?值（最小值）排序概念把?序的數據整理成有序數據稱為排序，從小到?的順序叫升序，從?到小的順序叫降序排序算法有很多，考試中可能涉及到的是選擇排序和冒泡排序選擇排序概念：每次在?序數中找到最小數（或最?數）的位置，然后存放在?序數的第?個（或最后?個）位置升序每次在?序數中找到最小數的位置，然后與?序數中第?個位置的數交換每次在?序數中找到最?數的位置，然后與?序數中最后?個位置的數交換降序每次在?序數中找到最小數的位置，然后與?序數中最后?個位置的數交換每次在?序數中找到最?數的位置，然后與?序數中第?個位置的數交換步驟從n個數中找出最小數的下標，?輪?較結束，最小數與第?個數交換位置，通過這?輪排序，第1個數已排好在余下的n-1個數中再按①中的?法選出最小數的下標，最小數與第2個數交換位置以此類推，重復步驟②，最后構成遞增序列冒泡排序概念：冒泡排序在每?輪排序時將相鄰兩個數組元素進??較，次序不對時?即交換位置，?輪?較結束時小數上浮，?數沉底升序從前往后依次兩兩?較，?的后移(如果a[j]>a[j+1]，交換a[j]和a[j+1])從后往前依次兩兩?較，小的前移(如果a[j]<a[j-1]，交換a[j]和a[j-1])降序從前往后依次兩兩?較，小的后移(如果a[j]<a[j+1]，交換a[j]和a[j+1])從后往前依次兩兩?較，?的前移(如果a[j]>a[j-1]，交換a[j]和a[j-1])說明冒泡排序和選擇排序每?輪?較都僅僅只確定?個數在數組中的位置，對n個數，需要進?n-1輪?較選擇排序每?輪只交換?次，冒泡排序在每?輪可能交換多次，因此花費的時間略多?點如果在某?輪?較中，沒有發??次交換，就說明數組已經有序了

2.3 字符串

基礎化整為零：字符串 = 字符數組，對字符串的處理即是對字符數組的處理化零為整：遍歷字符數組，通過字符串的連接運算，可以根據題?的要求，得到?個新的字符串，它通常就是問題的解操作：字符串的所有處理，都可以在化零為整的過程中完成CRUD：將字符串理解為字符數組后，字符串的CRUD（增、刪、改、查）操作就類似于數組的CRUD操作截取：?稱為取?串，即取出字符串中的?部分圖形：?稱為“字符圖形”，?般是輸出多?有規律的字符，組成?個特定的圖形，這樣的圖形稱為字符圖形注意① 可以將字符圖形中的??看作為?個字符串，字符串的末尾帶有?個換?符，由多個這樣的字符串組成?個完整的字符圖形② ?般而?，每??輸出的符號的種類和符號的個數是有規律的，因此，求解圖形問題的關鍵在以下3點Ⅰ 總?數，即字符圖形的總?數，記為“n”Ⅱ ?號，代表字符圖形中的某??，記為“i”，i∈[1,n]Ⅲ 每??中，每種符號的個數與總?數“n”和?號“i”之間的數學關系

3.優化

3.1 算法的性能

概念可以?算法的復雜性來衡量?個算法的效率，也可?它來衡量計算機求解問題的難易程度，包含算法的時間復雜性和空間復雜性算法的時間復雜性越?，算法的執?時間越?，反之越短；算法的空間復雜性越?，算法所需的存儲空間越多，反之越少在算法的復雜性分析中，對時間復雜性的分析考慮得更多時間復雜度概念通常采?“漸進時間復雜度”描述數據量的規模n與算法的執?時間t之間的函數關系時間復雜度為指數階O(2^n)的問題，當n值稍?時就?法計算了，但仍然屬于可計算性范疇時間復雜度為O(2^n)或O(n!)這類算法，?提?計算機的運?速度來擴?其求解規模，可能性是微乎其微的?般來說，通過對算法中循環次數的統計，即可直觀地估計出算法的時間復雜性常?：O(1) < O(logn) < O(nlogn) < O(n^2) < O(n^3) < ... < O(n^k) < O(2^n) < O(n!) < O(n^n)O(1) 常數階：問題的規模n和執?之間沒有關系，例如利?求和公式求等差數列之和O(logn) 對數階：?分查找、輾轉相除法求最?公約數（歐??得法）O(n) 線性階：考試中的多數算法的漸進時間復雜度就是O(n)級的，例如順序查找O(nlogn) 線性對數階：快速排序、歸并排序等O(n^2) 平?階：冒泡排序、選擇排序等O(2^n) 指數階：例如漢諾塔（hanoi）、旅?商（TSP）等空間復雜度概念：通常采?“漸進空間復雜度”來描述數據量的規模m與算法的執?空間需求之間的函數關系常?：O(1) < O(n) < O(n^2)O(1) 常?于不需要使?數組的算法O(n) 常?于使??維數組的算法O(n^2) 常?于使??維數組的算法注意①在很多問題中，時間和空間是?個對??當時間是?個重要因素時，有可能通過增加算法的空間復雜度以減少算法的時間復雜度，即?空間換時間當空間是?個重要因素時，有時也可以?算法的運?時間取換取空間②時間復雜度和空間復雜度之間僅僅具有相對性而不具備必然性也就是說，通過犧牲空間不必然能換取時間，通過犧牲時間也不必然能夠換取空間

3.2 算法的優化

原則：主要針對算法的時間性能進?優化，優化的原則是盡可能減少基本操作的執?次數?法① 減少循環次數，或減少循環中基本操作的執?次數Ⅰ 常數運算放在循環外執?，即把不需要反復執?的操作放在循環外Ⅱ 減少循環的執?次數，例如，把驗證n是否是素數的范圍從2~n-1縮小到2~sqrt(n)，以及在素數的判定或冒泡排序中，使?標志位提前結束循環等Ⅲ 需要多次執?數組的查找操作時，先對數組排序，就可以使?時間復雜度為O(logn)的?分查找代替時間復雜度為O(n)的順序查找② 平衡分?結構的層數，即對于多分?結構，盡可能構造?棵平衡樹③ 記憶化（memoization），把復雜計算的結果存儲起來，以?便多次重復使?，是?種?空間換時間的優化思路