ppt课件-顾刚43529-00顾刚-大学计算机基础课件ch8-4

第3章基本算法和策略,可视化计算,学习目标,什么是基本算法？哪些算法在计算问题求解中最为常用？算法与算法策略有何区别？哪些基本的算法策略在各种算法解决方案中被普遍采用?,基本算法,蛮力法分段函数递推法模运算字符和字符串运算递归组合计算迭代法,蛮力法,计算机问题求解的第一号方法被称为蛮力法(BruteForce)，也称穷举法采用蛮力算法解题的基本思路：确定穷举对象、穷举范围和判定条件；一一穷举可能的解，验证是否是问题的解在蛮力算法中，穷举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的穷举对象可以获得更高的效率,百钱买百鸡问题,某个人有一百块钱，打算买一百只鸡。到市场上一看，公鸡五块钱一只，母鸡三块钱一只，小鸡一块钱三只。现在，请编一个算法，算出如何能刚好用一百块钱买一百只鸡?,蛮力法求解,三种鸡的个数为穷举对象分别设为x，y，z以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*5+y*3+z/3)为判定条件，穷举各种鸡的个数由于三种鸡的和是固定的，只要穷举二种鸡（x，y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了穷举范围,求解流程图,如果需要解决的问题规模不大用蛮力法设计的算法其速度是可以接受的,分段函数,收费问题与我们的生活息息相关，如水费问题、电费问题、话费问题等这些收费问题往往根据不同的用量，采用不同的收费方式以收费为题材的数学问题多以分段函数的形式出现,阶梯电价问题,为鼓励节约用电，某市开始采取按月用电量分段收费办法，某户居民每月应交电费y（元）与用电量x（度）的函数如下：请设计上述电费的收费算法。,阶梯电价流程图,分段函数求解中的问题,最常见的错误的是将函数的数学表达式直接搬到算法中，例如：“0=x=100”；函数定义中，没有定义x1时）,斐波那契数列的递归求解,递归的辨识,斐波那契递归实现，调用一次产生二个新的递归，调用次数呈指数增长，时间复杂度为O（2n）。这种使用递归的方式，被称为“天真的递归（Naiverecursion）”。而使用递推算法求斐波那契数列，时间复杂度只是为O（n）,递归算法常用于解决三类问题,(1)数据的定义是按递归定义的(2)问题解法按递归算法实现(3)数据的结构形式是按递归定义的典型的递归算法(带参数传递实现)的运行效率较低在递归调用的过程当中系统为每一层的返回点、局部变量等开辟了栈来存储递归次数过多容易造成栈溢出等问题,RAPTOR与递归,RAPTOR不支持全局变量（子图和子程序皆可访问的公共变量），如果所有算法参数要靠子程序参数传递，是极为不现实理论上而言，所有递归算法都可以用非递归算法来实现递归的应用：递归是很好的求解问题的方法，可以很好的描述一个算法的原理但是在算法实现中，必须避免“天真的递归”,数论问题,数论的本质是对素数性质的研究2000多年前，欧几里得证明了有无穷个素数。寻找表示所有素数的素数通项公式，或者叫素数普遍公式，是古典数论最主要的问题之一加法、减法和乘法这三种运算，在整数范围内可以毫无阻碍地进行整数之间的除法在整数范围内并不一定能够无阻碍地进行大数密码体系，至今仍然关系着国家的安全,测素子程序,测素子程序是解决数论问题的核心，所以在数论应用算法中，几乎都要用到。因此它的计算效率，直接影响与数论相关的算法效率,一个测素子程序,如何改善测素子程序的效率？,组合计算,计算一些物品在特定条件下分组方法的数目。这些是关于排列、组合和整数分拆问题的求解，属于组合数学研究的范畴例如，求解从n个元素中取出m个元素的不同组合，用C(n,m)表示。根据组合的性质有如下公式成立：1.C(n，m)=n!/(m!*(n-m)!)但：13！是6227020800会超出32位机的字长,组合计算,另，用C(n，m)表示从n个元素中取出m个元素的不同组合数，也可使用递归的形式定义：2.C(n，m)=C(n-1，m)+C(n-1，m-1),求n个数中取m个数的所能产生组合形式的数量,根据组合的递归形式的数学定义：公式（2）可知，从从n个元素中取出m个元素的基本案例和递归案例分别为：m=n，c=1m=1，c=nmn，c=C(n-1，m)+C(n-1，m-1),递归实现组合数,迭代法,迭代是数值计算中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程为实现这一过程所使用的方法统称为迭代法（IterativeMethod）,一个简单的代数方程,三种迭代法,三种迭代方法的比较,测试的目的,迭代法是数值计算中求解非线性方程的基本思想方法，其构造方法可以有多种多样但关键是怎样才能使迭代收敛且有较快的收敛速度取定某个初始值，分别计算（3.3）（3.5）迭代结果，它们的收敛性如何？对三个迭代法中的某个，取不同的初始值进行迭代，结果如何？,牛顿迭代法求方程解,请用牛顿迭代法（3.6式）求方程在区间-3,3上误差不大于10-9的根，分别取初值X0=1.5,X0=0,X0=1分别进行计算，比较它们的迭代次数,牛顿迭代法基本原理,设,令其解为,得：,这称为f(x)=0的牛顿迭代格式，给定初值x0,迭代产生数列：,X0，