計(jì)算機(jī)二級(jí)access

1、2024/3/29,1,算法,教師：蔣寧 QQ：550352394,,2024/3/29,2,算法,公共基礎(chǔ)知識(shí)在筆試中占30分 10道選擇題+5道填空題 四塊內(nèi)容： 數(shù)據(jù)結(jié)構(gòu)與算法 程序設(shè)計(jì)基礎(chǔ) 軟件工程基礎(chǔ) 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ),,2024/3/29,3,算法,數(shù)據(jù)結(jié)構(gòu)與算法

2、 特點(diǎn)：抽象 偏難 重要 理解 考察重點(diǎn)： 基礎(chǔ)知識(shí) 基本理論 基本運(yùn)算 不要求編程實(shí)現(xiàn),,2024/3/29,4,算法,1-算法2-數(shù)據(jù)結(jié)構(gòu)的基本概念3-線性表及其順序存儲(chǔ)結(jié)構(gòu)4-棧和隊(duì)列5-線性鏈表6-樹與

3、二叉樹7-查找技術(shù)8-排序技術(shù),,2024/3/29,5,算法,計(jì)算機(jī)科學(xué)家沃斯： 數(shù)據(jù)結(jié)構(gòu)＋算法＝程序,,2024/3/29,6,1.算法的基本概念,算法：解題方案的準(zhǔn)確而完整的描述 怎樣來(lái)上課？,,2024/3/29,7,1.算法的基本概念,算法（Algorithm）是對(duì)特定問題求解步驟的一種描述，是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。算法≠程

4、序，程序是對(duì)一個(gè)算法使用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)，是對(duì)算法的精確描述，可以在計(jì)算機(jī)上執(zhí)行。算法≠計(jì)算方法，算法考慮到了多種情況,,2024/3/29,8,1.算法的基本概念,算法（Algorithm）是對(duì)特定問題求解步驟的一種描述，是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。算法≠程序，程序是對(duì)一個(gè)算法使用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)，是對(duì)算法的精確描述，可以在計(jì)算機(jī)上執(zhí)行。算法≠計(jì)算方法，算法考慮到了多種情況,,2024/

5、3/29,9,1.算法的基本概念,算法的基本特征：(1)可行性: 一個(gè)算法是能執(zhí)行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。(2)確定性:算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性。并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出。,,2024/3/29,10,注意事項(xiàng),算法的基本特征：(3)有窮性:一個(gè)算法必須總是(對(duì)任何合法的輸入值)在執(zhí)行有窮步

6、之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成； 例：破解密碼(4) 擁有足夠的情報(bào)： 輸入：一個(gè)算法有零個(gè)或多個(gè)的輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。,,2024/3/29,11,注意事項(xiàng),算法的基本要素：(1)對(duì)數(shù)據(jù)的運(yùn)算和操作: 算術(shù)運(yùn)算 邏輯運(yùn)算 關(guān)系運(yùn)算 數(shù)據(jù)傳輸,,2024/3/29,12,注意事項(xiàng),算法的基本要素：(2) 控制結(jié)構(gòu)：各操作之間的執(zhí)行順

7、序 順序結(jié)構(gòu),,2024/3/29,13,注意事項(xiàng),算法的基本要素：(2) 控制結(jié)構(gòu)：各操作之間的執(zhí)行順序 選擇結(jié)構(gòu),,2024/3/29,14,1.算法的基本概念,算法的基本要素：(2) 控制結(jié)構(gòu)：各操作之間的執(zhí)行順序 循環(huán)結(jié)構(gòu),,2024/3/29,15,1.算法的基本概念,,歐幾里德算法,例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自 然數(shù) m 和 n 的最大公約數(shù),算法的描述方法,

8、2024/3/29,16,1.算法的基本概念,,① 輸入m 和n；② 求m除以n的余數(shù)r；③ 若r等于0，則n為最大公約數(shù)，算法結(jié) 束；否則執(zhí)行第④步；④ 將n的值放在m中，將r的值放在n中；⑤ 重新執(zhí)行第②步。,例：歐幾里德算法,自然語(yǔ)言,2024/3/29,17,1.算法的基本概念,,算法的描述方法——自然語(yǔ)言,優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線條描述算法思想 注意事項(xiàng)：避免寫成自然段,2024/3/

9、29,18,1.算法的基本概念,,流 程 圖,例：歐幾里德算法,2024/3/29,19,1.算法的基本概念,,優(yōu)點(diǎn)：流程直觀、控制靈活缺點(diǎn)：缺少嚴(yán)密性、篇幅過長(zhǎng)使用方法：描述簡(jiǎn)單算法注意事項(xiàng)：注意抽象層次，避免流 程圖中的一個(gè)處理對(duì)應(yīng) 程序中的一條語(yǔ)句,算法的描述方法——流程圖,2024/3/29,20,1.算法的基本概念,,#include in

10、t CommonFactor(int m, int n){ int r=m % n; while (r!=0) { m=n; n=r; r=m % n; } return n;}void main( ){ cout<<CommonFactor(63, 54)<<endl;},程序設(shè)計(jì)語(yǔ)言,例：歐幾里德算法,2024/3/29,21

11、,1.算法的基本概念,,算法的描述方法——程序設(shè)計(jì)語(yǔ)言,優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行 缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù),2024/3/29,22,1.算法的基本概念,,1. r = m % n; 2. 循環(huán)直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 輸出 n ;,偽

12、代 碼,例：歐幾里德算法,2024/3/29,23,1.算法的基本概念,,算法的描述方法——偽代碼,優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解使用方法：方便快速結(jié)合單詞,2024/3/29,24,1.算法的基本概念,算法設(shè)計(jì)基本方法：(1) 列舉法： 例：銀行卡密碼破解(2) 歸納法： 例：質(zhì)量檢測(cè) 個(gè)別→批次,,2024/3/29,25,1.算法的基本概念,算法設(shè)計(jì)基本方法：(

13、3) 遞推： 例：求1+2+3+...+100(4) 遞歸： 將復(fù)雜問題逐層分解，最后歸結(jié)為求解一些最簡(jiǎn)單的問題 漢諾塔游戲(搬盤子),,2024/3/29,26,1.算法的基本概念,算法設(shè)計(jì)基本方法(4) 遞歸：漢諾塔游戲(搬盤子)假設(shè)有3根柱子，第1根柱子上套著n個(gè)半徑大小不同的盤子（盤子中央有小孔），并且大盤子在下面，小盤子在上面。要求將第1根柱子上的盤子搬到第3

14、根柱子上。在搬動(dòng)過程中，可以使用第2根柱子暫時(shí)存放盤子，但無(wú)論何時(shí)都必須保證大盤子在下面，小盤子在上面，并且一次只能搬動(dòng)一個(gè)盤子。,,2024/3/29,27,求5！函數(shù)調(diào)用過程：,main( ){ …… n=5; printf( f(5) );},long f(5){ long y; …… y=5*f(4); },long f(4){ long y; …… y=4* f(3)

15、; },long f(3){ long y; …… y=3*f(2); },long f(3){ long y; …… y=3*f(2); },long f(2){ long y; …… y=2*f(1); },long f(1){ long y; y=1; ……},return(1);,return(2);,return(6);,retu

16、rn(6);,return(24);,return(120);,2024/3/29,28,1.算法的基本概念,算法設(shè)計(jì)基本方法：(5) 減半遞推技術(shù)：將問題的規(guī)模減半,,例1.1 用二分法求方程f(x)=0的近似根 p4,,,,,,,x,y,f((a+b)/2),0,a,b,(a+b)/2,f(a),f(b),,2024/3/29,29,1.算法的基本概念,算法設(shè)計(jì)基本方法：(6) 回溯法,,先試探，若試探失敗逐步返回，換別的

17、線路再進(jìn)行試探，直到達(dá)到目的,1,,,,,,,,,,5,,,,,2024/3/29,30,2.算法復(fù)雜度,算法的時(shí)間復(fù)雜度(Time Complexity) ：執(zhí)行算法所需要的計(jì)算工作量 基本運(yùn)算的執(zhí)行次數(shù) 問題的規(guī)模：輸入量的多少算法的工作量=f(n) n:問題的規(guī)模兩個(gè)n階矩陣相乘所需要的基本運(yùn)算次數(shù)：n3,,,,2024/3/29,31,2.算法復(fù)雜度,例：在一維整型數(shù)組A[n

18、]中查找與輸入值x相等的元素順序查找法：基本運(yùn)算(比較)的次數(shù)與具體輸入值x有關(guān),,2024/3/29,32,2.算法復(fù)雜度,兩種方法分析算法的工作量 ：(1)平均時(shí)間復(fù)雜度 各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值,,2024/3/29,33,2.算法復(fù)雜度,兩種方法分析算法的工作量 ：(2)最壞時(shí)間復(fù)雜度 在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù),,2024/3/29,34,2.算法復(fù)雜度,例1.2 P6 ：

19、在一維整型數(shù)組A[n]中查找與輸入值x相等的元素用兩種方法分析順序查找法的時(shí)間復(fù)雜度 A(n)=(n+1)q/2+(1-q)n W(n)=n,,2024/3/29,35,2.算法復(fù)雜度,算法的空間復(fù)雜度(Space Complexity) ：執(zhí)行這個(gè)算法所需要的內(nèi)存空間(影響執(zhí)行效率)包括：程序占用 初始數(shù)據(jù) 執(zhí)行開銷：變量占用

20、 鏈接占用,,2024/3/29,36,例題講解,2024/3/29,37,1.算法的時(shí)間復(fù)雜度是指A) 執(zhí)行算法程序所需要的時(shí)間 B) 算法程序的長(zhǎng)度C) 算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D) 算法程序中的指令條數(shù)2.算法的空間復(fù)雜度是指 A) 算法程序的長(zhǎng)度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲(chǔ)空間 D) 執(zhí)行過程中所需要的存儲(chǔ)空間3

21、.在計(jì)算機(jī)中，算法是指 A) 加工方法B) 解題方案的準(zhǔn)確而完整的描述 C) 排序方法D) 查詢方法4. 下面敘述正確的是______。A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B. 算法的空間復(fù)雜度是指算法程序中指令（或語(yǔ)句）的條數(shù)C. 算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止D. 以上三種描述都不對(duì),2024/3/29,38,5.算法分析的目的是 A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找