第一章 算法和算法的表示 小结课件（24张幻灯片）

课件24张PPT。算法实例常用的算法设计方法小结01020304用枚举方法来设计算法用解析方法来设计算法对数据进行排序的简单算法用于查找的简单算法01PART ONE枚举算法基本思想：把问题所有可能的解一一罗列出来，并对每一个可能解进行判断，以确定这个解是否是问题的真正解，若是问题的真正解， 就予以采纳，否则就抛弃它。枚举法，也常称之为穷举法。什么是枚举算法？枚举算法举例例1：一份单据中被涂抹数字的推算
有一张单据上有一个5位数的编号n，其百位数和十位数处已经变得模糊不清，但是知道这个5位数是37或67的倍数。现要设计一个算法，找出所有满足这些条件的5位数，并统计这些5位数的个数。枚举算法举例例2：包装问题
包装1200个变形金刚，要求是：
（1）包装的规格分别是：小盒（每盒5个）和大盒
（每盒12个）；
（2）每种规格的盒数可任选，但每盒都必须装满。
设计一个算法，输出所有可能的包装方案，并输出包装方案的个数枚举算法举例例3：求小于N的最大素数
--找不到一个数学公式，使得根据N就可以计算出这个素数
--枚举：N-1是素数吗？N-2是素数吗？......暴力枚举~如果什么技巧都没有，所有可能情况都试一遍验证其是不是问题的答案，就是暴力枚举。
~即便是枚举，也要优雅地排除根本不需要试的那些情况，以加快速度，这就是优雅枚举。02PART TWO解析算法 是指用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。什么是解析算法？ 例1：计算N个电阻并联后的总电阻值解析算法举例设计一个算法，计算电阻并联的总电阻值R 例2：储蓄顾问解析算法举例 银行要改善为储户的服务，将设计一个计算机程序，专门回答储户如下的问题：
“M元钱需要存多少年，才能得到至少K元本息？”（为简单起见，算法中暂不考虑利息税问题。
为简单起见，假定银行公布的储蓄规则为：
①存期以年为单位，存款以元为单位；
②不论存期的长短，年利率均为2.8%；
③不计复利。解析算法解题思路1.明确问题的前提条件
2.明确要求的解
3.寻找前提条件与结果之间的数学表达式输入输出处理03PART THREE排序算法把杂乱无章的数据变为有序的数据，这一过程称为排序。
两种简单的排序算法：冒泡排序、选择排序。什么是排序算法？冒泡排序 冒泡排序（Bubble Sort）是在一列数据中把较小的数据逐次向上推移的一种排序技术。冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。当第一遍加工完成时，最小的数据已经上升到第一个元素的位置。然后对余下的n-１个元素重复上述处理过程，直至最后进行余下两个数据的比较和交换。由于每一遍加工都是将本遍最小的元素像气泡一样上浮至本遍的顶端位置，故称为冒泡排序。选择排序 选择排序算法(selection sort)是对冒泡排序算法的改进。这种方法是在参加排序数组的所有元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据相互交换位置。然后再在余下的元素中找出最小(或最大)数据的元素，与第二个元素中的数据相互交换位置。以此类推，直到所有元素成为一个有序的序列。其它排序算法插入排序桶排序快速排序归并排序04PART FOUR查找算法 查找（Search）是一种查询数据的技术、其目标是能以较小的步骤或较短的时间找到所需的对象。
两种简单的查找算法：顺序查找、对分查找什么是查找？顺序查找 顺序查找的基本思想：从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到所查数据的位置；反之，查找不成功。对分查找 对分查找的基本思想：在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，或直到子表不存在，即查找不成功。对分查找的条件是被查找的数据必须是有序的。对分查找和顺序查找的速度对比枚举算法逐个尝试答案解析算法数学表达式排序算法冒泡排序、选择排序算法小结查找算法顺序查找、对分查找