第8章 算法基础

第8章算法基础,算法（Algorithm）是一种逐步解决问题或完成任务的方法，是为解决一个特定问题而采取的确定的、有限的步骤。做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤就称为算法。例如，利用公式（1）实现华氏温度到摄氏温度的转换。c=5(32)9（1）,算法,计算机科学家唐纳德.E.克努斯（DonaldE.Knuth）在他撰写的“TheArtofComputerProgramming”中写到：“一个算法，就是一个有穷规则的集合，其中的规则规定了一个解决某一特定类型的问题的运算序列。”,有穷性（Finiteness）确定性(Definiteness)输入项(Input)输出项(Output)可行性(Effectiveness),算法具有如下基本特征,顺序选择循环,算法的三种结构,自然语言表示方法例如，用自然语言描述求解最大公约数（欧几里得算法）的算法如下：(1)对于已知两个正整数m，n，使得mn；(2)以大数m作被除数，小数n作除数，m除以n得余数r；(3)若r0，mn，nr，继续执行步骤(2)；(4)若r=0，则n即为所求的m与n的最大公约数，算法结束。,算法的表示方法,流程图表示方法,欧几里得算法流程图,求和,基本算法介绍,乘积（1）将乘积（product）初始化。图8.3求和算法流程图（2）循环，在每次迭代中将一个新数与乘积（product）相乘。（3）退出循环后，输出乘积（product）。乘积算法通过较小的改动可用来计算xn和n!(阶乘)算法。,最大和最小（1）求一组数中的最大值。例如，一组数5,3,0,9,6求其中的最大值，方法如下：输入第1个数字5；设置m等于第1个数5；再输入下一个数到x；比较m和x，如果x大于m，则m=x；判断这组数字是否结束，如果没结束，转再重复上面的操作；如果结束就返回最大值m。,穷举法（ExhaustiveAttackAlgorithm），也称为暴力破解法（Brute-ForceAttack）。其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。,穷举法,例如：百钱百鸡问题。这是中国古代算书张丘建算经中一道著名的百鸡问题：公鸡每只值5文钱，母鸡每只值3文钱，而3只小鸡值1文钱。用100文钱买100只鸡，问：这100只鸡中，公鸡、母鸡和小鸡各有多少只?,递推算法（RecurrenceAlgorithm）是一种用若干步可重复的简单运算来描述复杂问题的方法。递推算法分为顺推和逆推两种。所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法。所谓逆推法是从已知问题的结果出发，用迭代表达式逐步推算出问题的开始条件，即顺推法的逆过程。递推算法是一种理性思维模式的代表，根据已有的数据和关系，逐步推导出问题的结果。,递推法,例，猴子吃桃问题：一只猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天只剩下一个桃子了。求第一天共摘了多少。,1.冒泡排序图8.7冒泡排序流程图冒泡排序（BubbleSort），是一种相对比较较简单的排序算法。它的排序思想是：重复走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。,排序算法,2.选择排序选择排序（Selectionsort）算法是对冒泡排序算法的改进，在参加排序的所有数组元素中找出最小数据的元素，使它与第一个元素中的数据相互交换位置。然后再在余下的元素中找出次最小数据的元素，与第二个元素中的数据相互交换位置，以此类推，直到所有元素成为一个有序的序列,查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。,查找算法,1.顺序查找顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。,2.二分查找二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样一直进行，直到查找到或查找结束发现表中没有这样的结点,设在a中存放这n个整数，已经按照从小到大的顺序排序，要查找的数为x。用L、R、m分别表示查找数据范围的起点、终点和中点，m=(L+R)/2，m取整。如果x=am，则找到，否则进行下面的判断；如果xam，x应在m+1和R的范围之内查找，则L=m+1；在确定了新的查找范围后，重复进行以上比较，直到找到或者LR。,递归是计算机科学的一个重要概念。递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身，这种过程(或函数)叫递归过程(或函数)例如，已知1！=1，利用递归算法求整数n（n2）的阶乘。（n!=n*(n-1)!来计算n!）,递归,递归算法解决问题的特点：递归就是在过程或函数里调用自身。在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。,2.递归算法要求：递归算法所体现的“重复”一般有三个要求：每次调用在规模上都有所缩小；相