算法設(shè)計(jì)與分析第鄭宗漢PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 算法設(shè)計(jì)與分析第鄭宗漢算法設(shè)計(jì)與分析第鄭宗漢 2 o算法組成算法組成 n（1）問(wèn)題）問(wèn)題 n（2）規(guī)則）規(guī)則 n（3）結(jié)果）結(jié)果 o算法是解某一問(wèn)題的一組算法是解某一問(wèn)題的一組有窮有窮規(guī)則的集合。規(guī)則的集合。 o算法是把算法是把輸入輸入轉(zhuǎn)換成轉(zhuǎn)換成輸出輸出的一個(gè)計(jì)算序列。的一個(gè)計(jì)算序列。 第1頁(yè)/共24頁(yè) 3 第2頁(yè)/共24頁(yè) 4 第3頁(yè)/共24頁(yè) 5 第4頁(yè)/共24頁(yè) 6 第5頁(yè)/共24頁(yè) 7 第6頁(yè)/共24頁(yè) 8 第7頁(yè)/共24頁(yè) 9 第8頁(yè)/共24頁(yè) 10 第9頁(yè)/共24頁(yè) 11 第第1章章 算法的基本概念算法的基本概念 o 1.1 引言引言 n1.1.1 算法的定義和特性算法

2、的定義和特性 n1.1.2 算法的設(shè)計(jì)和復(fù)雜性分析算法的設(shè)計(jì)和復(fù)雜性分析 第10頁(yè)/共24頁(yè) 12 第11頁(yè)/共24頁(yè) 13 輸入： 輸出： 第一步: 第二步: 第三步: 第四步: 正整數(shù)m和n m和n的最大公約數(shù) 求余數(shù)r m%n if r = 0? yes 終止(n為答案) no 執(zhí)行第三步。 m n, n r, 返回第一步。 最大公約數(shù)問(wèn)題：求兩個(gè)正整數(shù)m和n的最大公約數(shù) 輸入輸入： 一個(gè)算法有一個(gè)算法有0 0個(gè)或多個(gè)輸入，個(gè)或多個(gè)輸入， 它是由外部提供的，作為算法它是由外部提供的，作為算法 開(kāi)始執(zhí)行前的初始值，或初始開(kāi)始執(zhí)行前的初始值，或初始 狀態(tài)。狀態(tài)。 算法的輸入是從特定的對(duì)象集算

3、法的輸入是從特定的對(duì)象集 合中抽取的。算法中有兩個(gè)輸合中抽取的。算法中有兩個(gè)輸 入入m m、n n，就是從正整數(shù)集合中，就是從正整數(shù)集合中 抽取的。抽取的。 輸出輸出： 一個(gè)算法有一個(gè)或多個(gè)輸出，一個(gè)算法有一個(gè)或多個(gè)輸出， 這些輸出與輸入有特定的關(guān)系，這些輸出與輸入有特定的關(guān)系， 實(shí)際上是輸入的某種函數(shù)。不實(shí)際上是輸入的某種函數(shù)。不 同取值的輸入，產(chǎn)生不同結(jié)果同取值的輸入，產(chǎn)生不同結(jié)果 的輸出。的輸出。 算法中的輸出是輸入算法中的輸出是輸入m m、n n的最的最 大公約數(shù)。大公約數(shù)。 有限性有限性： 算法在執(zhí)行有限步之后必須終算法在執(zhí)行有限步之后必須終 止。止。 算法（歐幾里德算法）中，對(duì)算法

4、（歐幾里德算法）中，對(duì) 輸入的任意正整數(shù)輸入的任意正整數(shù)m m、n n，將，將m m 除以除以n n的余數(shù)賦予的余數(shù)賦予r r之后，再通之后，再通 過(guò)過(guò)r r賦予賦予n n，從而使，從而使n n值變小。值變小。 如此往復(fù)進(jìn)行，最終或者使如此往復(fù)進(jìn)行，最終或者使r r 為為0 0，或者使，或者使n n遞減為遞減為1 1。這兩。這兩 種情況，都最終使種情況，都最終使r=0r=0，而使，而使 算法終止。算法終止。 確定性確定性： 算法的每一個(gè)步驟，都有精確算法的每一個(gè)步驟，都有精確 的定義。要執(zhí)行的每一個(gè)動(dòng)作的定義。要執(zhí)行的每一個(gè)動(dòng)作 都是清晰的、無(wú)歧義的。都是清晰的、無(wú)歧義的。 例如，在算法的第例

5、如，在算法的第3 3行中，如果行中，如果 m m、n n是無(wú)理數(shù)，那么，是無(wú)理數(shù)，那么，m m除以除以n n 的余數(shù)就沒(méi)有一個(gè)明確的界定。的余數(shù)就沒(méi)有一個(gè)明確的界定。 確定性的準(zhǔn)則意味著必須確保確定性的準(zhǔn)則意味著必須確保 在執(zhí)行第在執(zhí)行第3 3行時(shí)，行時(shí)，m m和和n n的值都是的值都是 正整數(shù)。正整數(shù)。 算法規(guī)定了算法規(guī)定了m m、n n都是正整數(shù)，都是正整數(shù)， 從而保證了后續(xù)各個(gè)步驟中都從而保證了后續(xù)各個(gè)步驟中都 能確定地執(zhí)行。能確定地執(zhí)行。 可行性可行性： 算法中所有待實(shí)現(xiàn)的運(yùn)算，都算法中所有待實(shí)現(xiàn)的運(yùn)算，都 是基本的運(yùn)算。原則上可以由是基本的運(yùn)算。原則上可以由 人們用紙和筆，在有限的時(shí)

6、間人們用紙和筆，在有限的時(shí)間 里精確地完成。里精確地完成。 算法算法中整除、判斷、賦值等等中整除、判斷、賦值等等 運(yùn)算都是可行的。因?yàn)檎麛?shù)可運(yùn)算都是可行的。因?yàn)檎麛?shù)可 以用有限的方式表示。以用有限的方式表示。 如果所涉及的數(shù)值必須由展開(kāi)如果所涉及的數(shù)值必須由展開(kāi) 成無(wú)窮小數(shù)的實(shí)數(shù)來(lái)精確地完成無(wú)窮小數(shù)的實(shí)數(shù)來(lái)精確地完 成，則這些運(yùn)算就不是可行的成，則這些運(yùn)算就不是可行的 了。了。 注意：注意： 有限性的限制是不夠的。有限性的限制是不夠的。 一個(gè)實(shí)用的算法，不僅要求步一個(gè)實(shí)用的算法，不僅要求步 驟有限，同時(shí)要求運(yùn)行這些步驟有限，同時(shí)要求運(yùn)行這些步 驟所花費(fèi)的時(shí)間是人們可以接驟所花費(fèi)的時(shí)間是人們可以

7、接 受的。受的。 特性：特性： （1）輸入）輸入 （2）輸出）輸出 （3）有限性）有限性 （4）確定性）確定性 （5）可行性）可行性 第12頁(yè)/共24頁(yè) 14 o 1.1 引言引言 n1.1.1 算法的定義和特性算法的定義和特性 n1.1.2 算法的設(shè)計(jì)和復(fù)雜性分析算法的設(shè)計(jì)和復(fù)雜性分析 第13頁(yè)/共24頁(yè) 15 理 解 問(wèn) 題 算 法 表 示 算 法 分 析 算 法 實(shí) 現(xiàn) 第14頁(yè)/共24頁(yè) 100abc 53/ 3100abc %30c 16 第15頁(yè)/共24頁(yè) 1. void chicken_question(int n, int 4. k = 0; 5. for (a = 0; a

8、= n; a+) 6. for ( b = 0; b = n; b+) 7. for (c = 0; c = n; c+) 8. if (a + b + c = n) 10. mk = b; 11. sk = c; 12. k+; 13. 14. 15. 16. 17. 17 分析發(fā)現(xiàn)：只能買(mǎi)到 n/5只公雞，n/3只母雞， 將算法進(jìn)行改進(jìn)。 1.1.2 1.1.2 算法的設(shè)計(jì)和復(fù)雜性分析算法的設(shè)計(jì)和復(fù)雜性分析 第16頁(yè)/共24頁(yè) 1. void chicken_question_2(int n, int 4. k = 0; 5. i = n / 5; 6. j = n / 3; 7. for

9、 (a = 0; a = i; a+) 8. for ( b = 0; b = j; b+) 9. c = n a - b; / 原來(lái)為 for (c = 0; c = n; c+) 10. if (a + b + c = n) 12. mk = b; 13. sk = c; 14. k+; 15. 16. 18 1.1.2 1.1.2 算法的設(shè)計(jì)和復(fù)雜性分析算法的設(shè)計(jì)和復(fù)雜性分析 第17頁(yè)/共24頁(yè) 19 n最短路徑的哈密爾頓回 路問(wèn)題，數(shù)據(jù)結(jié)構(gòu)是無(wú) 向加權(quán)圖G = ，V 是頂點(diǎn)集合，E是距離集 合。 第18頁(yè)/共24頁(yè) 1. void salesman_problem(int n, flo

10、at 4. float cost; 5. min = MAX_FLOAT_NUM; 6. while (i = n!) 7. 產(chǎn)生n個(gè)城市的第i個(gè)排列于p; 8. cost = 路線p的費(fèi)用； 9. if (cost min) 10. 把數(shù)組p的內(nèi)容復(fù)制到數(shù)組t； 11. min = cost; 12. 13. i+; 14. 15. n! 20 1.1.2 1.1.2 算法的設(shè)計(jì)和復(fù)雜性分析算法的設(shè)計(jì)和復(fù)雜性分析 第19頁(yè)/共24頁(yè) （假定循環(huán)體每執(zhí)行一次，需要1s時(shí)間） 21 1.1.2 1.1.2 算法的設(shè)計(jì)和復(fù)雜性分析算法的設(shè)計(jì)和復(fù)雜性分析 第20頁(yè)/共24頁(yè) 22 說(shuō)明了改進(jìn)算法的設(shè)計(jì)方 法對(duì)提高算法性能是非常 重