算法设计与分析第郑宗汉PPT学习教案

1、会计学1 算法设计与分析第郑宗汉算法设计与分析第郑宗汉 2 o算法组成算法组成 n（1）问题）问题 n（2）规则）规则 n（3）结果）结果 o算法是解某一问题的一组算法是解某一问题的一组有穷有穷规则的集合。规则的集合。 o算法是把算法是把输入输入转换成转换成输出输出的一个计算序列。的一个计算序列。 第1页/共24页 3 第2页/共24页 4 第3页/共24页 5 第4页/共24页 6 第5页/共24页 7 第6页/共24页 8 第7页/共24页 9 第8页/共24页 10 第9页/共24页 11 第第1章章 算法的基本概念算法的基本概念 o 1.1 引言引言 n1.1.1 算法的定义和特性算法

2、的定义和特性 n1.1.2 算法的设计和复杂性分析算法的设计和复杂性分析 第10页/共24页 12 第11页/共24页 13 输入： 输出： 第一步: 第二步: 第三步: 第四步: 正整数m和n m和n的最大公约数 求余数r m%n if r = 0? yes 终止(n为答案) no 执行第三步。 m n, n r, 返回第一步。 最大公约数问题：求两个正整数m和n的最大公约数 输入输入： 一个算法有一个算法有0 0个或多个输入，个或多个输入， 它是由外部提供的，作为算法它是由外部提供的，作为算法 开始执行前的初始值，或初始开始执行前的初始值，或初始 状态。状态。 算法的输入是从特定的对象集算

3、法的输入是从特定的对象集 合中抽取的。算法中有两个输合中抽取的。算法中有两个输 入入m m、n n，就是从正整数集合中，就是从正整数集合中 抽取的。抽取的。 输出输出： 一个算法有一个或多个输出，一个算法有一个或多个输出， 这些输出与输入有特定的关系，这些输出与输入有特定的关系， 实际上是输入的某种函数。不实际上是输入的某种函数。不 同取值的输入，产生不同结果同取值的输入，产生不同结果 的输出。的输出。 算法中的输出是输入算法中的输出是输入m m、n n的最的最 大公约数。大公约数。 有限性有限性： 算法在执行有限步之后必须终算法在执行有限步之后必须终 止。止。 算法（欧几里德算法）中，对算法

4、（欧几里德算法）中，对 输入的任意正整数输入的任意正整数m m、n n，将，将m m 除以除以n n的余数赋予的余数赋予r r之后，再通之后，再通 过过r r赋予赋予n n，从而使，从而使n n值变小。值变小。 如此往复进行，最终或者使如此往复进行，最终或者使r r 为为0 0，或者使，或者使n n递减为递减为1 1。这两。这两 种情况，都最终使种情况，都最终使r=0r=0，而使，而使 算法终止。算法终止。 确定性确定性： 算法的每一个步骤，都有精确算法的每一个步骤，都有精确 的定义。要执行的每一个动作的定义。要执行的每一个动作 都是清晰的、无歧义的。都是清晰的、无歧义的。 例如，在算法的第例

5、如，在算法的第3 3行中，如果行中，如果 m m、n n是无理数，那么，是无理数，那么，m m除以除以n n 的余数就没有一个明确的界定。的余数就没有一个明确的界定。 确定性的准则意味着必须确保确定性的准则意味着必须确保 在执行第在执行第3 3行时，行时，m m和和n n的值都是的值都是 正整数。正整数。 算法规定了算法规定了m m、n n都是正整数，都是正整数， 从而保证了后续各个步骤中都从而保证了后续各个步骤中都 能确定地执行。能确定地执行。 可行性可行性： 算法中所有待实现的运算，都算法中所有待实现的运算，都 是基本的运算。原则上可以由是基本的运算。原则上可以由 人们用纸和笔，在有限的时

6、间人们用纸和笔，在有限的时间 里精确地完成。里精确地完成。 算法算法中整除、判断、赋值等等中整除、判断、赋值等等 运算都是可行的。因为整数可运算都是可行的。因为整数可 以用有限的方式表示。以用有限的方式表示。 如果所涉及的数值必须由展开如果所涉及的数值必须由展开 成无穷小数的实数来精确地完成无穷小数的实数来精确地完 成，则这些运算就不是可行的成，则这些运算就不是可行的 了。了。 注意：注意： 有限性的限制是不够的。有限性的限制是不够的。 一个实用的算法，不仅要求步一个实用的算法，不仅要求步 骤有限，同时要求运行这些步骤有限，同时要求运行这些步 骤所花费的时间是人们可以接骤所花费的时间是人们可以

7、接 受的。受的。 特性：特性： （1）输入）输入 （2）输出）输出 （3）有限性）有限性 （4）确定性）确定性 （5）可行性）可行性 第12页/共24页 14 o 1.1 引言引言 n1.1.1 算法的定义和特性算法的定义和特性 n1.1.2 算法的设计和复杂性分析算法的设计和复杂性分析 第13页/共24页 15 理 解 问 题 算 法 表 示 算 法 分 析 算 法 实 现 第14页/共24页 100abc 53/ 3100abc %30c 16 第15页/共24页 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 分析发现：只能买到 n/5只公鸡，n/3只母鸡， 将算法进行改进。 1.1.2 1.1.2 算法的设计和复杂性分析算法的设计和复杂性分析 第16页/共24页 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; / 原来为 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 算法的设计和复杂性分析算法的设计和复杂性分析 第17页/共24页 19 n最短路径的哈密尔顿回 路问题，数据结构是无 向加权图G = ，V 是顶点集合，E是距离集 合。 第18页/共24页 1. void salesman_problem(int n, flo

10、at 4. float cost; 5. min = MAX_FLOAT_NUM; 6. while (i = n!) 7. 产生n个城市的第i个排列于p; 8. cost = 路线p的费用； 9. if (cost min) 10. 把数组p的内容复制到数组t； 11. min = cost; 12. 13. i+; 14. 15. n! 20 1.1.2 1.1.2 算法的设计和复杂性分析算法的设计和复杂性分析 第19页/共24页 （假定循环体每执行一次，需要1s时间） 21 1.1.2 1.1.2 算法的设计和复杂性分析算法的设计和复杂性分析 第20页/共24页 22 说明了改进算法的设计方 法对提高算法性能是非常 重