《《可视化计算》算法综合加工了的》由会员分享，可在线阅读，更多相关《《可视化计算》算法综合加工了的（204页珍藏版）》请在金锄头文库上搜索。
1、基本算法和策略,西安交大可视化计算,学习目标,程序与算法有哪些异同? 算法有哪些基本特性？ 算法的效率如何度量？ 如何为算法设计做准备？,2,算法定义,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。 通俗来说，就是通过计算来解决问题的过程，在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法 不同的是：前者是推理实现的算法，后者是操作实现的算法 所以，程序是使用计算机实现的算法；而算法则不一定需要有计算机才能实现,3,算法的特性,算法具有五个基本特性： 输入（具有零个或多个输入） 输出（一或多个输出） 有穷性（自动结束而不会出现无限循环） 确定性（每一步骤的含义，不会出
2、现二义性） 可行性（能够通过执行有限次数完成）,4,算法设计的要求,正确性 可读性 健壮性 时间效率高 存储量需求低,5,正确性的层次,算法程序没有语法错误; 算法程序对于合法的输入数据能够产生满足要求的输出结果; 算法程序对于非法的输入数据能够得出满足规格说明的结果; 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。,6,可读性,为了便于阅读、理解和交流，可读性要素： 增加算法文件名、子图、子程序、算法样本数据文件名的可读性； 在算法语句中增加注释语句，说明重要变量、决策语句的用途； 将算法有关的文档整理在一个目录中,7,健壮性,能对输入数据不合法的情况做合适的处理 比如输
3、入的时间或者距离不应该是负数 算法的健壮性表现在当输入数据不合法时，算法也能做出相关处理，而不是产生异常或无法解释的结果,8,时间效率高和存储量需求低,对于同一个问题，如果有多个算法能够达到同样的问题解决标准，执行时间最短的算法效率最高 存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间，越少越好,9,算法效率的度量,一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素： 编译产生的代码质量； 算法采用的策略、方法； 问题的输入规模； 机器执行指令的速度。,10,2-end,学习目标,什么是基本算法？ 哪些算法在计算问题求解
4、中最为常用？ 算法与算法策略有何区别？ 哪些基本的算法策略在各种算法解决方案中被普遍采用?,12,基本算法,蛮力法 分段函数 递推法 模运算 字符和字符串运算 递归 组合计算 迭代法,13,蛮力法,计算机问题求解的第一号方法被称为蛮力法(Brute Force) ，也称穷举法 采用蛮力算法解题的基本思路： 确定穷举对象、穷举范围和判定条件； 一一穷举可能的解，验证是否是问题的解 在蛮力算法中，穷举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的穷举对象可以获得更高的效率,14,百钱买百鸡问题,某个人有一百块钱，打算买一百只鸡。到市场上一看，公鸡五块钱一只，母鸡三块钱一只，小鸡
5、一块钱三只。现在，请编一个算法，算出如何能刚好用一百块钱买一百只鸡?,15,蛮力法求解,三种鸡的个数为穷举对象 分别设为x，y，z 以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*5+y*3+z/3)为判定条件，穷举各种鸡的个数 由于三种鸡的和是固定的，只要穷举二种鸡（x，y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了穷举范围,16,求解流程图,如果需要解决的问题规模不大 用蛮力法设计的算法其速度是可以接受的,17,分段函数,收费问题与我们的生活息息相关，如水费问题、电费问题、话费问题等 这些收费问题往往根据不同的用量，采用不同的收费方式 以收费为题材的数学问题
6、多以分段函数的形式出现,18,阶梯电价问题,为鼓励节约用电，某市开始采取按月用电量分段收费办法，某户居民每月应交电费y（元）与用电量x（度）的函数如下： 请设计上述电费的收费算法。,19,阶梯电价流程图,20,分段函数求解中的问题,最常见的错误的是将函数的数学表达式直接搬到算法中，例如：“0=x=100”； 函数定义中，没有定义x0，也就是输入为负数的时候，如何处理。当然，可以实验一下，当x取负值时结果如何？ 这个算法没有设计输入和规范的输出界面，例如输入的提示，输出内容的量纲等,21,递推法,递推法是利用问题本身所具有的一种递推关系求解问题的一种方法 所谓递推，是指从已知的初始条件出发，依据
7、某种递推关系，逐次推出所要求的各中间结果及最后结果 其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定,22,可递推求解的问题特点,该类题目一般有以下二个特点： 问题可以划分成多个状态； 除初始状态外，其它各个状态都可以用固定的递推关系式来表示 在实际解题中，该类题目一般不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式,23,猴子吃桃问题,小猴子摘桃若干，立即吃了一半还觉得不过瘾，又多吃了一个； 第二天接着吃剩下桃子的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃剩下的桃子一半多一个； 到第10天小猴子再去吃桃子的时候，看到只剩下一个桃子； 则小猴子第一天共摘
8、了多少桃子？,24,递推问题求解,由题意可以得到下表： 分析后可知，猴子吃桃问题递推关系为： Sn=1 （当n=10时） Sn =2（Sn+1+1）（当1n10时） 在此基础上，以第10天的桃数作为基数，用以上归纳出来的递推关系设计出一个循环过程，将第1天的桃数推算出来,25,递推流程图,为了加强交互性，增加了交互界面，可以输入不同的天数进行递推 算法使用了两个变量，一个用于递推的循环控制，另一个保存递推得到的结果 注意主要的循环控制变量是递减的，与题意设计完全相同，便于理解。 算法中加入了输入数据的正确性控制，也就是不可以输入0和负数,26,模运算,在算法应用中，有一类计算与模运算（求除法之
9、余数）有关，例如： 一个星期的模为7天 一天的模是24小时或1440分钟 一年的模是12个月（也可以是365或366天） 而模运算在数字比较和诸多计算案例中有应用,27,求1001000范围内的平方回数,所谓平方回数，是指某个数，既是一个回文数，又是一个平方数， 例如：121是回文数，又是11的平方,28,模运算求解分析,一个100以上的平方数，必须从平方根大于等于10的数字开始计算，而1000可以作为搜索循环的控制变量 但是，如何求出回文数？ 由于是在三位数中求回文数，也就是要求个位与百位上相等 这个时候，模（在RAPTOR中模运算符：mod）运算就可以派上用场,29,求平方回数流程图,请思
10、考一下，这个算法还使用了其他什么算法思想？,30,字符和字符串运算,字符和字符串运算在算法中的用途有： 在输入输出界面中的应用，如在输出过程中将计算结果与量纲结合在一起； 在信息安全中的应用，如信息的加密与解密； 对用户对特定应用的输入的字符串，进行模式正确性的判断（如电子邮件地址需包含“”符号）等,31,替换加密,试用以下替换码表，实现通信过程的加密 明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 密码表 Q W E R T Y U I O P A S D F G H J K L Z X C V B N M,32,替换加密,保存
11、明文 Key保存密码表 B保存密文 解密算法，自行设计,33,递归,在数学和计算机科学中，递归是指由一种（或多种）简单的基线条件(Base case)定义的一类对象或方法，并规定其他所有情况都能被还原为其基线条件 具体表现为：一个函数在其定义或说明中有直接或间接调用自身： 把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解 递归策略只需少量的程序就可描述出解题过程,34,递归过程,一般来说，递归需要有边界条件、递归前进段和递归返回段 当边界条件不满足时，递归前进； 当边界条件满足时，递归返回 一般递归过程需要通过函数或子程序传递参数 而RAPTOR中要实现子程序的参数调用，必
12、须使用其所谓的“中级模式（Intermediate mode）”,35,递归算法常用于解决三类问题,(1)数据的定义是按递归定义的 (2)问题解法按递归算法实现 (3)数据的结构形式是按递归定义的 典型的递归算法(带参数传递实现)的运行效率较低 在递归调用的过程当中系统为每一层的返回点、局部变量等开辟了栈来存储 递归次数过多容易造成栈溢出等问题,36,递归算法,理论上而言，所有递归算法都可以用非递归算法来实现 递归的应用： 递归是很好的求解问题的方法，可以很好的描述一个算法的原理 但是在算法实现中，必须避免“天真的递归”,37,汉诺塔,有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘
13、子，要把所有的盘子从A柱移动到C柱，移动过程中如下要求： 一次只能移动一个盘子； 不允许把大盘放在小盘上面； 盘子只能放在三根柱子上,38,汉诺塔递归求解,N个盘子的移动过程分作3大步： 把A柱上面的N-1个盘子移动到B柱； 把A柱上剩下的一个盘子移动到C柱； 把B柱上面的N-1个盘子移动到C柱； 其中N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束,39,汉诺塔递归main子图,40,汉诺塔递归子程序,41,斐波那契(Fibonacci)数列,一些问题本身是递归定义的，但它并不适合用递归算法来
14、求解 如斐波那契(Fibonacci)数列，它的递归定义为：斐波那契数列为：0、1、1、2、3、，即： fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2) （当n1时）,42,斐波那契数列的递归求解,43,递归的辨识,斐波那契递归实现，调用一次产生二个新的递归，调用次数呈指数增长，时间复杂度为O（2n）。 这种使用递归的方式，被称为“天真的递归（Naive recursion）”。 而使用递推算法求斐波那契数列，时间复杂度只是为O（n）,44,数论问题,数论的本质是对素数性质的研究 2000多年前，欧几里得证明了有无穷个素数。寻找表示所有素数的素数通项公式
15、，或者叫素数普遍公式，是古典数论最主要的问题之一 加法、减法和乘法这三种运算，在整数范围内可以毫无阻碍地进行 整数之间的除法在整数范围内并不一定能够无阻碍地进行 大数密码体系，至今仍然关系着国家的安全,45,测素子程序,测素子程序是解决数论问题的核心，所以在数论应用算法中，几乎都要用到。 因此它的计算效率，直接影响与数论相关的算法效率,46,一个测素子程序,如何改善测素子程序的效率？,47,组合计算,计算一些物品在特定条件下分组方法的数目。这些是关于排列、组合和整数分拆问题的求解，属于组合数学研究的范畴 例如，求解从n个元素中取出m个元素的不同组合，用C(n,m)表示。根据组合的性质有如下公式
16、成立： 1. C(n，m) = n!/(m!*(n-m)!) 但：13！是6227020800会超出32位机的字长,48,组合计算,另，用C(n，m)表示从n个元素中取出m个元素的不同组合数，也可使用递归的形式定义： 2. C(n，m) = C(n-1，m) + C(n-1，m-1),49,求n个数中取m个数的所能产生组合形式的数量,根据组合的递归形式的数学定义：公式（2）可知，从从n个元素中取出m个元素的基本案例和递归案例分别为： m=n， c=1 m=1， c=n mn ， c= C(n-1，m) + C(n-1，m-1),50,递归实现组合数,51,迭代法,迭代是数值计算中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程 为实现这一过程所使用的方法统称为迭代法（Iterative Method）,52,一个简单的代数方程,三种迭代法,53,三种迭代方法的比较,54,测试的目的,迭代法是数值计算中求解非
