算法分析与设计[1].ppt

计算机算法分析与设计学习目标课程要求授课教材第一章导引1.1算法(Algorithm)的定义和特征算法是指解决问题的一种方法或一个过程一个算法是求解某一类特定问题的一组有穷规则的集合。首先，一个算法是一组规则，通常称之为算法步骤，这组规则是有穷的，即能用有限的形式表示出来。其次，一个算法是针对一类问题而设计的。1.2算法的描述算法的基本思想：轻者（小的元素）像气泡那样从水底往上浮。在排序过程中，每次把相邻的两个元素作比较，当前面的元素大于后面的元素时，就交换它们的位置。这样，所有相邻的元素比较一遍以后最大的元素就被交换到了最后面。依此类推，直到把最后两个元素排好序。用冒泡排序法对6个数进行排序(从小到大)算法1.1冒泡排序输入：待排序数组A，其中有n个元素；输出：排好序的数组A。bubblesort(floatA[],intn){inti,j;for(i=0;i<n-1;i++)for(j=0;j<n-1-i;j++)if(A[j]>A[j+1])swap(A+j,A+j+1);}算法1.2元素交换输入：待交换元素的位置x和y；输出：交换后的结果仍存于x和y中。swap(float*x,float*y){floatu=*x;*x=*y;*y=u;}例1.2求两个正整数m,n的最大公约数例1.2求两个正整数m,n的最大公约数求两个正整数最大公因子的一个实例算法1.3求最大公约数的辗转相除法输入：两整数m和n；输出：m和n的最大公约数。intgcd(intm,intn){inta=max{m,n};intb=min{m,n};intc;while(b!=0){c=amodb;a=b;b=c;}return(a);}算法1.4求最大公约数的递归算法输入：两整数m和n；输出：m和n的最大公约数。intgcd(intm,intn){inta=max{m,n};intb=min{m,n};intc;if(b==0)return(a);else{c=amodb;return(gcd(b,c));}}Horner根据等式设计出一个高效算法。首先，我们给出两个更为基本的集合运算算法。一个用Member(b,A)表示，其功能是考查b是不是集合A的一个元素。另一个记为Insert(b,A)，它的功能是在集合A中增加一个元素b，这个运算以b原本不是A的元素为前提。实现Member(b,A)的实质性工作是查找。把A的元素逐个同b进行比较，若找到一个元素等于b，就输出1并停止运算；当查找完集合A的全部元素都没有找出同b相等的元素时，就输出0。算法的五个重要特性算法的特性1.3算法分析频率计数例子计算时间的渐进估计表示时间的渐进估计表示时间的渐进估计表示算法的分类n假设：机器运算速度设计算法时间算法时间复杂度甲105/s5天O(n3)乙108/s2小时O(2n)时间的渐进估计表示常用的整数求和公式冒泡排序算法的时间复杂性分析。冒泡排序算法主要包含两种基本运算：比较和交换。比较和交换运算都出现在双重嵌套循环语句的循环体中，比较运算是作为交换运算的条件而出现的。从这个双重嵌套的循环语句结构容易知道，比较运算共需进行次。当待排序数组的元素之间满足关系时，一次交换运算都不需要执行。反之，如果待排序数组的元素满足关系那么每一次比较后都需要把相邻两个元素进行交换。平均情况下的时间复杂性分析需要先引入逆序的概念。在一个序列中，若存在，使得i<j但，则说A[i]和A[j]构成一个逆序。显然，用算法1.1对这个序列进行排序，交换运算的次数就等于这个序列中逆序的个数。由于n个数的不同排列共有n!种，而在各种排列中，逆序个数的最小值为0，最大值为n(n-1)/2。因此各种分布的平均逆序个数为上式值等于n(n-1)/4。可见平均交换运算次数和最坏情况下的交换运算次数都是输入量n的二次函数，即1.4递归方程求解一个黄铜板上，插着三根宝石针，其中一根针上从下到上放了由大到小的64块金片，这就是Hanoi塔。Hanoi塔问题：就是如何将64块金片按照梵天不渝法则，由一根宝石针全部移动到另一根宝石针上去。Hanoi问题AAAAA移动步骤：①(n-1)个圆盘AB②第n个圆盘AC③(n-1)个圆盘BC如果只有一块金片，则只需作一次移动就可以了。如果有两块金片，则先将上面小的金片从第一根针移到第三根针上，再将下面大的金片从第一根针移到第二根针上，最后将第三根针上的小的金片从第三根针移到第二根针上。总共作3次移动动作。如果有n个金片呢？假设对n-1块金片怎样移动我们已经掌握，那么就可以把金片分成两部分：上面n-1块作为一部分，最底下的一块作为另一部分。这样，就可以把上面的n-1块金片整体移动到第三根针上，然后把最底下的一块金片移到第二根针上，最后再把第三根针上的块金片整体移到第二根针上，放