计算机算法基础.ppt

1算法设计与分析 Design and Analysis to Algorithms 2 教材: 算法设计与分析吕国英主编清华大学出版社计算机算法基础余祥宣等编华中科大出版社参考书: 算法设计与分析王晓东编清华大学出版社计算机算法导引——设计与分析卢开澄编清华大学出版社学时: 2学时/周 3 与数据结构的区别: 考虑问题的角度:数据结构关心不同的数据结构在解题中的作用和效率;算法关心不同设计技术的适用性和效率。考虑问题的高度:数据结构关心的是解具体问题,算法不仅如此,它提供一种解决问题的通用方法。与其他课程的关系高级程序设计语言( C, C++ ) 数据结构算法设计与分析 4 ?广播操图解是广播操的算法; ?菜谱是做菜的算法; ?歌谱是一首歌曲的算法; ?空调说明书是空调使用的算法等 What ?5 例1:给出求 1+2+3+4+5 的一个算法。算法 1按照逐一相加的程序进行。第一步计算 1+2, 得到 3; 第二步将第一步中的运算结果 3与3相加,得到 6; 第三步将第二步中的运算结果 6与4相加,得到 10; 第四步将第三步中的运算结果 10与5相加,得到 15。 6 算法 2可以运用公式 2 )1(321 ?????? nnn?直接计算; 第一步取n=5; 第二步计算 2 )1(?nn第三步输出运算结果。 7 例2:三个牧师和三个野人过河,只有一条能装下两人的船,在河的任一边或者船上,若野人人数大于牧师人数,那么牧师就会有被吃掉的危险。你能不能找出一种安全的渡河算法呢? 第一步两个野人先过河,一个野人回来; 第二步再两个野人过河,一个野人回来; 第三步两个牧师过河,一个野人和一个牧师回来; 第四步两个牧师过河,一个野人回来; 第五步两个野人过河,一个野人回来; 第六步两个野人过河。 8 算法广义: 在解决问题时,按照某种机械步骤一定可以得到问题结果(有解时给出问题的解,无解时给出无解的结论)的处理过程。狭义: 用计算机解决问题的方法和步骤的描述。 9 20 世纪最伟大的科学技术发明---计算机; 计算机是对人脑的模拟,它强化了人的思维; 没有软件的支持,超级计算机只是一堆废铁而已。软件的核心就是算法软件的核心就是算法! ! Why to study ? 程序=数据结构+算法程序=数据结构+算法 10现代科学研究的三大支柱理论研究科学实验科学计算研究算法