算法设计与分析 第1章 绪论

《算法设计与分析 第1章 绪论》由会员分享，可在线阅读，更多相关《算法设计与分析 第1章 绪论（17页珍藏版）》请在金锄头文库上搜索。

1、信息科学与技术学院课程主要内容u 绪论u 算法效率分析基础u 蛮力法u 分治法u 减治策略和变治策略u 动态规划u 贪心算法u 回溯法和分支限界法u NP完全性理论主要教材及参考资料u 师智斌，靳雁霞，井超，梁志剑，雷海卫编著. 算法分析与设计及案例教程. 清华大学出版社. 2015年1月 （教材）u 美 Anany Levitin 著. 算法设计与分析基础（第3版影印版）.清华大学出版社. 2013年5月u 美Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein著，潘金贵，顾铁城，李成法，叶懋译. 算

2、法导论.机械工业出版社. 2007年3月 u王晓东编著. 计算机算法设计与分析（第3版）. 电子工业出版社. 2008年4月u网站资源：Standford Mooc课程： https:/class.coursera.org/algo-008http:/ 绪 论算法：解决问题的确定方法和有限步骤。算法的描述方法：（1）文字描述（2）流程描述（3）伪代码描述 例子：（1）多元一次方程组的求解。（2）求最大公因数。（3）直接插入排序算法实现排序求最大公约数算法描述：（1）输入m,n。（2）设置 变量r，令r为m除以n的余数。（3）若r等于0，则n为最大公约数，算法结束。否则执行（3）（4）将n赋值给

3、m,r赋值给n。（5）转到（1）。求 最 大 公 约 数程序：#include “stdio.h“int main()int m, n, r;printf(“Please input m and n:“);scanf(“%d%d“, while(1)r = m%n;if (r != 0)m = n;n = r;elsebreak;printf(“The common divisor of m and n is:%dn“, n);return 0; 求解问题的分类：（1） 排序（2）查找（3） 字符串匹配（4） 图（5）组合问题（6）几何问题 （7）数值计算问题算法的特征：（1）输入（2）输出（3）确定性（4）有穷性（5）可行性基本数据结构：（1）线性结构（2）树结构（3）图结构（4） 集合算法问题求解步骤：（1）分析问题，建立数学模型。（2）分解问题。（3）设计算法。（4）算法正确性证明。（5）算法效率分析。（6）程序实现。（7）撰写文档。作业：P16： 题5。