《可视化计算》算法综合-加工了的.pptxVIP

基本算法和策略西安交大《可视化计算》

学习目标程序与算法有哪些异同?算法有哪些基本特性？算法的效率如何度量？如何为算法设计做准备？2http://

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。算法定义3http://通俗来说，就是通过计算来解决问题的过程，在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法不同的是：前者是推理实现的算法，后者是操作实现的算法所以，程序是使用计算机实现的算法；而算法则不一定需要有计算机才能实现

算法具有五个基本特性：算法的特性4http://可行性（能够通过执行有限次数完成）确定性（每一步骤的含义，不会出现二义性）有穷性（自动结束而不会出现无限循环）输出（一或多个输出）输入（具有零个或多个输入）

算法设计的要求5http://正确性可读性健壮性时间效率高存储量需求低

正确性的层次6http://算法程序没有语法错误;算法程序对于合法的输入数据能够产生满足要求的输出结果;算法程序对于非法的输入数据能够得出满足规格说明的结果;算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。

为了便于阅读、理解和交流，可读性要素：可读性7http://增加算法文件名、子图、子程序、算法样本数据文件名的可读性；在算法语句中增加注释语句，说明重要变量、决策语句的用途；将算法有关的文档整理在一个目录中

健壮性8http://能对输入数据不合法的情况做合适的处理比如输入的时间或者距离不应该是负数算法的健壮性表现在当输入数据不合法时，算法也能做出相关处理，而不是产生异常或无法解释的结果

时间效率高和存储量需求低9http://对于同一个问题，如果有多个算法能够达到同样的问题解决标准，执行时间最短的算法效率最高存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间，越少越好

算法效率的度量10http://一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：编译产生的代码质量；算法采用的策略、方法；问题的输入规模；机器执行指令的速度。

2-end

学习目标12http://01什么是基本算法？02哪些算法在计算问题求解中最为常用？03算法与算法策略有何区别？04哪些基本的算法策略在各种算法解决方案中被普遍采用?

基本算法13http://蛮力法01分段函数02递推法03模运算04字符和字符串运算05递归06组合计算07迭代法08

蛮力法14http://计算机问题求解的第一号方法被称为蛮力法(BruteForce)，也称穷举法采用蛮力算法解题的基本思路：确定穷举对象、穷举范围和判定条件；一一穷举可能的解，验证是否是问题的解在蛮力算法中，穷举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的穷举对象可以获得更高的效率

百钱买百鸡问题15http://某个人有一百块钱，打算买一百只鸡。到市场上一看，公鸡五块钱一只，母鸡三块钱一只，小鸡一块钱三只。现在，请编一个算法，算出如何能刚好用一百块钱买一百只鸡?

蛮力法求解16http://STEP3STEP2STEP1三种鸡的个数为穷举对象分别设为x，y，z以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*5+y*3+z/3)为判定条件，穷举各种鸡的个数由于三种鸡的和是固定的，只要穷举二种鸡（x，y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了穷举范围

求解流程图17http://如果需要解决的问题规模不大用蛮力法设计的算法其速度是可以接受的

分段函数18http://01收费问题与我们的生活息息相关，如水费问题、电费问题、话费问题等03以收费为题材的数学问题多以分段函数的形式出现02这些收费问题往往根据不同的用量，采用不同的收费方式

阶梯电价问题19http://为鼓励节约用电，某市开始采取按月用电量分段收费办法，某户居民每月应交电费y（元）与用电量x（度）的函数如下：请设计上述电费的收费算法。

阶梯电价流程图20http://

分段函数求解中的问题21http://最常见的错误的是将函数的数学表达式直接搬到算法中，例如：“0=x=100”；01函数定义中，没有定义x0，也就是输入为负数的时候，如何处理。当然，可以实验一下，当x取负值时结果如何？02这个算法没有设计输入和规范的输出界面，例如输入的提示，输出内容的量纲等03

递推法是利用问题本身所具有的一种递推关系求解问题的一种方法递推法22http://所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定

可递推求解的问题特点23http://该类题目一般有以下二个特点：问题可以