2014华南理工大学广州学院,算法设计与分析期末考试复习PPT

2014华南理工大学广州学院,算法设计与分析期末考试复习PPT

ID:38755215

大小:3.90 MB

页数:68页

时间:2019-06-18

2014华南理工大学广州学院,算法设计与分析期末考试复习PPT_第1页
2014华南理工大学广州学院,算法设计与分析期末考试复习PPT_第2页
2014华南理工大学广州学院,算法设计与分析期末考试复习PPT_第3页
2014华南理工大学广州学院,算法设计与分析期末考试复习PPT_第4页
2014华南理工大学广州学院,算法设计与分析期末考试复习PPT_第5页
资源描述:

《2014华南理工大学广州学院,算法设计与分析期末考试复习PPT》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、复习考试题型:选择题(算法类型、时间复杂度,共15题,30分)简答题(设计思想,共2题,12分)应用题(解题步骤、搜索空间树等,共4题,48分)编程题(上机实验题,作业题等,共1题,10分)复习2021/8/23复习Page32021/8/23Page3算法的几种描述方法(重点掌握伪代码和C++语言,会使用伪代码写算法);理解大O符号的含义;算法的几个重要特性:输入、输出、有穷性、确定性、可行性。第一章、第二章⑴自然语言优点:容易理解缺点:冗长、二义性使用方法:粗线条描述算法思想注意事项:避免写成自然段算法的几种描述方法(重点掌握伪代码和C++语言,会使用伪代码写算法);⑵流

2、程图优点:流程直观缺点:缺少严密性、灵活性使用方法:描述简单算法注意事项:注意抽象层次⑶程序设计语言优点:能由计算机执行缺点:抽象性差,对语言要求高使用方法:算法需要验证注意事项:尽量将算法写成子函数⑷伪代码——算法语言伪代码(Pseudocode):介于自然语言和程序设计语言之间的方法,它采用某一程序设计语言的基本语法,操作指令可以结合自然语言来设计。优点:表达能力强,抽象性强,容易理解理解大O符号的含义;时间复杂度算法的五大特性:2021/8/23第1章算法设计基础Page9输入:一个算法有零个或多个输入。输出:一个算法有一个或多个输出。有穷性:一个算法必须总是在执行有穷

3、步之后结束,且每一步都在有穷时间内完成。算法的有穷性意味着不是所有的计算机程序都是算法.确定性:算法中的每一条指令必须有确切的含义,对于相同的输入只能得到相同的输出。可行性:算法描述的操作可以通过已经实现的基本操作执行有限次来实现(每步可执行)。2021/8/23复习Page102021/8/23Page10蛮力法的基本思想(重要!):蛮力法依赖的基本技术——扫描技术,即采用一定的策略将待求解问题的所有元素依次处理一次,从而找出问题的解;关键——依次处理所有元素。第三章蛮力法2021/8/23复习Page112021/8/23Page11熟记哪些问题使用了蛮力法进行解决:顺序

4、查找、串匹配(KMP,BM,BF),选择排序,冒泡排序,生成排列对象,生成子集,0/1背包,任务分配,哈密顿回路,TSP,最近对问题,凸包问题,7-11问题,百钱买百鸡问题;并熟记这些问题的时间复杂度;第三章蛮力法2021/8/23复习Page122021/8/23Page12其中:BF:依次扫描,对比,O(n+m);KMP:依次扫描,对比(虽然这个“依次”已经是按照一定的规律,效率较高),O(n+m),注意:对于KMP算法,必须求出next数组;选择排序:扫描整个序列,找到整个序列的最小记录和序列中的第一个记录交换位置,再扫第二小,依此类推…,O(n2);第三章蛮力法202

5、1/8/23复习Page132021/8/23Page13其中:冒泡排序:扫描整个序列,在扫描过程中两两比较相邻记录,如果反序则交换,直到n-1趟扫描后,即排好序,O(n2);TSP:把所有可能的回路都找出来,就可以得到最短路径,O(n!);7-11:把所有可能都计算一遍,就能得到正确的解;百钱买百鸡:把所有可能都计算一遍,就能得到正确的解。第三章蛮力法2021/8/23复习Page142021/8/23Page14冒泡排序、选择排序、TSP问题的设计思想和伪代码(可能出简答题)7-11问题、百钱买百鸡问题的代码实现(猜测是编程题)第三章蛮力法冒泡排序设计思想选择排序设计思想

6、TSP问题设计思想TSP问题:旅行家要旅行n个城市然后回到出发城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。用蛮力法解决TSP问题,可以找出所有可能的旅行路线,从中选取路径长度最短的简单回路。8abdc23571序号路径路径长度是否最短1a→b→c→d→a18否2a→b→d→c→a11是3a→c→b→d→a23否4a→c→d→b→a11是5a→d→b→c→a23否6a→d→c→b→a18否注意到,在图中有3对不同的路径,对每对路径来说,不同的只是路径的方向,因此,可以将这个数量减半,则可能的解有(n-1)!/2个。这是一个非常大的数,随着n的增长,TSP问题的可能

7、解也在迅速地增长。用蛮力法求解TSP问题,其时间复杂性为O(n!),只能解决问题规模很小的实例。一个简单的例子——百元买百鸡问题已知公鸡5元一只,母鸡3元一只,小鸡1元三只,用100元钱买100只鸡,问公鸡、母鸡、小鸡各多少只?voidchicken(){intx,y,z;for(x=0;x<=20;x++){for(y=0;y<=33;y++){z=100-x-y;if((z%3==0)&&(5*x+3*y+z/3==100)){cout<<"公鸡:"<

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。