20192014华南理工大学广州学院,算法设计与分析期末考试复习PPT.ppt
《20192014华南理工大学广州学院,算法设计与分析期末考试复习PPT.ppt》由会员分享,可在线阅读,更多相关《20192014华南理工大学广州学院,算法设计与分析期末考试复习PPT.ppt(68页珍藏版)》请在三一文库上搜索。
1、复习,考试题型: 选择题(算法类型、时间复杂度,共15题,30分) 简答题(设计思想,共2题,12分) 应用题(解题步骤、搜索空间树等,共4题,48分) 编程题(上机实验题,作业题等,共1题,10分),复习,2019/5/13,复习,Page 3,2019/5/13,Page 3,算法的几种描述方法(重点掌握伪代码和C+语言,会使用伪代码写算法); 理解大O符号的含义; 算法的几个重要特性:输入、输出、有穷性、确定性、可行性。,第一章、第二章,自然语言 优点:容易理解 缺点:冗长、二义性 使用方法:粗线条描述算法思想 注意事项:避免写成自然段,算法的几种描述方法 (重点掌握伪代码和C+语言,会
2、使用伪代码写算法);, 流程图 优点:流程直观 缺点:缺少严密性、灵活性 使用方法:描述简单算法 注意事项:注意抽象层次,程序设计语言 优点:能由计算机执行 缺点:抽象性差,对语言要求高 使用方法:算法需要验证 注意事项:尽量将算法写成子函数, 伪代码算法语言 伪代码(Pseudocode):介于自然语言和程序设计语言之间的方法,它采用某一程序设计语言的基本语法,操作指令可以结合自然语言来设计。 优点:表达能力强,抽象性强,容易理解,理解大O符号的含义;时间复杂度,算法的五大特性:,2019/5/13,第1章 算法设计基础,Page 9,输入:一个算法有零个或多个输入。 输出:一个算法有一个或
3、多个输出。 有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。算法的有穷性意味着不是所有的计算机程序都是算法. 确定性:算法中的每一条指令必须有确切的含义,对于相同的输入只能得到相同的输出。 可行性:算法描述的操作可以通过已经实现的基本操作执行有限次来实现(每步可执行)。,2019/5/13,复习,Page 10,2019/5/13,Page 10,蛮力法的基本思想(重要!): 蛮力法依赖的基本技术扫描技术,即采用一定的策略将待求解问题的所有元素依次处理一次,从而找出问题的解; 关键依次处理所有元素。,第三章 蛮力法,2019/5/13,复习,Page 11,2019/
4、5/13,Page 11,熟记哪些问题使用了蛮力法进行解决:顺序查找、串匹配(KMP,BM,BF),选择排序,冒泡排序,生成排列对象,生成子集,0/1背包,任务分配,哈密顿回路,TSP,最近对问题,凸包问题,7-11问题,百钱买百鸡问题;并熟记这些问题的时间复杂度;,第三章 蛮力法,2019/5/13,复习,Page 12,2019/5/13,Page 12,其中: BF:依次扫描,对比,O(n+m); KMP:依次扫描,对比(虽然这个“依次”已经是按照一定的规律,效率较高),O(n+m),注意:对于KMP算法,必须求出next数组; 选择排序:扫描整个序列,找到整个序列的最小记录和序列中的第
5、一个记录交换位置,再扫第二小,依此类推,O(n2);,第三章 蛮力法,2019/5/13,复习,Page 13,2019/5/13,Page 13,其中: 冒泡排序:扫描整个序列,在扫描过程中两两比较相邻记录,如果反序则交换,直到n-1趟扫描后,即排好序, O(n2) ; TSP:把所有可能的回路都找出来,就可以得到最短路径,O(n!); 7-11:把所有可能都计算一遍,就能得到正确的解; 百钱买百鸡:把所有可能都计算一遍,就能得到正确的解。,第三章 蛮力法,2019/5/13,复习,Page 14,2019/5/13,Page 14,冒泡排序、选择排序、TSP问题的设计思想和伪代码(可能出简
6、答题) 7-11问题、百钱买百鸡问题的代码实现(猜测是编程题),第三章 蛮力法,冒泡排序,设计思想,选择排序,设计思想,TSP问题,设计思想,TSP问题:旅行家要旅行n个城市然后回到出发城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。 用蛮力法解决TSP问题,可以找出所有可能的旅行路线,从中选取路径长度最短的简单回路。,注意到,在图中有3对不同的路径,对每对路径来说,不同的只是路径的方向,因此,可以将这个数量减半,则可能的解有(n-1)!/2个。这是一个非常大的数,随着n的增长,TSP问题的可能解也在迅速地增长。用蛮力法求解TSP问题,其时间复杂性为O(n!),只能解决问题规模很小的
7、实例。,一个简单的例子百元买百鸡问题 已知公鸡5元一只,母鸡3元一只,小鸡1元三只,用100元钱买100只鸡,问公鸡、母鸡、小鸡各多少只?,void chicken() int x,y,z; for(x=0;x=20;x+) for(y=0;y=33;y+) z=100-x-y; if(z%3=0) ,(编程,代码要记牢),7-11问题(编程,代码要记牢),设计蛮力算法找出四件物品的价格各是什么? #include void main() int a,b,c,d; for(a=1;a=711;a+) for(b=1;b=711;b+) for(c=1;c=711;c+) d=711-a-b-c
8、; if(a*b*c*d=711) couta/100.0tb/100.0tc/100.0td/100.0endl; return; ,2019/5/13,复习,Page 22,2019/5/13,Page 22,分治法的基本思想(重要!自底向上,理解+应用): 将要求解的原问题划分成k个较小规模的子问题,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子问题划分为k个规模更小的子问题,如此分解下去,直到问题规模足够小,很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。 步骤:(1)划分(2)求解子问题(3)合并,第四章 分治法,2019
9、/5/13,复习,Page 23,2019/5/13,Page 23,分治法的基本思想(自底向上,理解+应用):,第四章 分治法,2019/5/13,复习,Page 24,2019/5/13,Page 24,熟记哪些问题使用了分治法进行解决:归并排序,快速排序,最大子段和,棋盘覆盖,循环赛日程安排,最近对问题,凸包问题;并熟记这些问题的时间复杂度:,第四章 分治法,2019/5/13,复习,Page 25,2019/5/13,Page 25,其中: 归并排序:划分成等长子序列分别对两子序列归并排序将排完的有序子序列合并成一个有序序列,O(nlog2n); 快速排序:用一个轴值划分成两个子序列分
10、别对两个子序列递归地快速排序, O(nlog2n) ; 最大子段和:划分成等长子序列针对3种情况分别处理求子序列最大子段和合并3种情况下的最大子段和, O(nlog2n) 。,第四章 分治法,2019/5/13,复习,Page 26,2019/5/13,Page 26,归并排序、快速排序、最大子段和问题的设计思想和伪代码;(可能出简答题) 用快速排序和归并排序算法对数字序列排序。,第四章 分治法,归并排序,设计思想,二路归并排序的分治策略是: (1)划分:将待排序序列r1, r2, , rn划分为两个长度相等的子序列r1, , rn/2和rn/21, , rn; (2)求解子问题:分别对这两个
11、子序列进行排序,得到两个有序子序列; (3)合并:将这两个有序子序列合并成一个有序序列。 二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间,因此其空间复杂性为O(n)。,快速排序,设计思想,以第一个记录作为轴值,对待排序序列进行划分的过程为: (1)初始化:取第一个记录作为基准,设置两个参数i,j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置,也就是本次划分的区间; (2)右侧扫描过程:将基准记录与j指向的记录进行比较,如果j指向记录的关键码大,则j前移一个记录位置。重复右侧扫描过程,直到右侧的记录小(即反序),若ij,则将基准记录与j指向的记录进行交换; (3)左
12、侧扫描过程:将基准记录与i指向的记录进行比较,如果i指向记录的关键码小,则i后移一个记录位置。重复左侧扫描过程,直到左侧的记录大(即反序),若ij,则将基准记录与i指向的记录交换; (4)重复(2)(3)步,直到i与j指向同一位置,即基准记录最终的位置。,最大子段和问题,设计思想,复习,减治法的基本思想(理解+应用): 原问题的解只存在于其中一个较小规模的子问题中,所以,只需求解其中一个较小规模的子问题就可以得到原问题的解。 熟记哪些问题使用了减治法进行解决:折半查找,二叉树查找,插入排序,堆排序,选择问题,淘汰赛冠军问题,假币问题(8枚硬币不知道假币轻重);并熟记这些问题的时间复杂度:,第五
13、章 减治法,2019/5/13,复习,Page 33,2019/5/13,Page 33,其中: 折半查找:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;若给定值大于中间记录的关键码,则在中间记录的右半区继续查找,O(log2n)。 插入排序:依次将待排序序列中的每一个记录插入到一个已排好序的序列中,直到全部记录都排好序,O(n2),第五章 减治法,2019/5/13,复习,Page 34,2019/5/13,Page 34,其中: 选择问题:考虑快速排序中的划分过程,选定一个轴值将序列ri rj进行
14、划分,使得比轴值小的元素都位于轴值的左侧,比轴值大的元素都位于轴值的右侧,假定轴值的最终位置是s,则: (1)若k=s,则rs就是第k小元素; (2)若ks,则第k小元素一定在轴值后半区中;,第五章 减治法,2019/5/13,复习,Page 35,2019/5/13,Page 35,其中: 假币问题(8枚硬币不知道假币轻重):从八枚硬币中任取六枚a,b,c,d,e,f,在天平两端各放三枚进行比较。假设a,b,c三枚放在天平的一端,d,e,f三枚放在天平的另一端,可能出现三种比较结果(再根据三种比较结果进行分析) abcdef abcdef abcdef,第五章 减治法,2019/5/13,复
15、习,Page 36,2019/5/13,Page 36,折半查找问题的设计思想和伪代码(可能出简答题) 给一个数字序列,要求采用折半查找,找某个数,写出求解的过程。,第五章 减治法,折半查找问题,设计思想 在有序表中,取中间记录作为比较对象, 若给定值与中间记录的关键码相等,则查找成功; 若给定值小于中间记录的关键码,则在中间记录的左半区继 续查找; 若给定值大于中间记录的关键码,则在中间记录的右半区继 续查找。不断重复上述过程,直到查找成功,或所查找的区 域无记录,查找失败。,2019/5/13,第5章 减治法,Page 38,例:查找值为14的记录的过程:,0 1 2 3 4 5 6 7
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 20192014 华南理工大学 广州 学院 算法 设计 分析 期末考试 复习 PPT
链接地址:https://www.31doc.com/p-2773693.html