计算机软件技术基础-03 算法和数据结构1

3、算法和数据结构设计程序首先要研究要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤。模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来；同时需要确定合适的数据结构。如何解决移动问题？解题过程的准确、完整的描述称作解该问题的算法。程序就是用计算机语言表述的算法，流程图就是图形化了的算法。著名计算机科学家、PASCAL语言发明者N·沃思(NiklausWirth)教授进一步提出如下的著名公式：程序＝算法＋数据结构——不能离开数据结构去抽象地分析程序的算法，也不能脱离算法去孤立地研究程序的数据结构，而只能从算法与数据结构的统一上去认识程序。算法的两要素算法由操作与控制结构两要素组成操作(1)逻辑运算：“与”、“或”、“非”；(2)算术运算：加、减、乘、除；(3)数据比较：大于、小于、等于、不等于；(4)数据传送：输入、输出、赋值。控制结构算法的控制结构，决定了各操作的执行次序。用流程图可以形象地表示出算法的控制结构任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成（1966年，Bohm和Jacopini证明）S1S2BS1S2BS(a)(b)(c)S3FTBFT(d)S算法的特征1.算法是由一套计算规则组成的一个过程2.组成算法的规则是确定的、可执行的3.每种算法必须有确定的结果，产生一个或多个输出4.每个算法必须有0个（自动生成初始数）或多个输入5.解答必须在有限步内得到,不能出现“死循环”我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答算法的表示算法设计通常是经历由粗到细的过程，一般可以使用下面几种类型的工具描述算法：自然语言用自然语言描述算法通俗易懂，但它存在着难以克服的缺陷：易产生歧义性。自然语言往往要根据上下文才能判别其含义，不太严格。语句比较繁琐冗长，并且很难清楚地表达算法的逻辑流程。如果算法中包含判断、循环处理，尤其是这些处理的嵌套层数增多，自然语言描述其流程既不直观又很难表达清楚。当今的计算机尚不能处理用自然语言表示的算法算法的表示专用工具◦常用的有流程图、伪代码、PAD图和N-S图等程序设计语言算法描述语言◦为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。常用算法1、枚举法（穷举法）先依据题目的部分条件确定答案的大致范围；在此范围内对所有可能的情况逐一验证，直到全部情况验证完；若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。常用算法2、迭代法使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程。迭代法的基本思想是：首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差；然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差；并认为最后一次迭代得到的近似值为问题的解。常用算法2、迭代法牛顿迭代求根：)()(1nnnnpfpfppvoidmain(){doublexn,x=1.5,res=1;for(inti=0;i1000;++i){doublexn=Iterate(x);doubleres=fabs(xn–x);if(res0.001)break;x=Relax(xn,x);}printf(“%f\n”,xn);}010423xxxxxxxxnn831042231doubleIterate(doublex){returnx–(x*x*x+4*x*x-10)/(3*x*x+8*x);}doubleRelax(doublexn,doublex){returnx;}常用算法3、递归法如果一个过程直接或间接地调用它自身，则称该过程是递归的。递归过程必须有一个递归终止条件；递归从函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值。常用算法3、递归法老大老二老三大头目小头目喽啰常用算法3、递归法求n的阶乘：intFact(intn){if(n1)return1;elsereturnn*Fact(n-1);}1n=0　n!＝n(n-1)!n0voidmain(){intnn=Fact(10);printf(“%d”,nn);}常用算法4、递推法所谓递推法，它的数学公式也是递归的。只是在实现计算时与递归相反。从给定边界出发逐步迭代到达指定计算参数。递推操作是提高递归函数执行效率最有效的方法，科技计算中最常见。常用算法4、递推法递推法求n的阶乘：voidmain(){intnn=Fact(10);printf(“%d”,nn);}intFact(intn){intnn=1;for(inti=1;i=n,++i)nn*=i;returnnn;}常用算法5、分治法解一个夏杂的问题时，尽可能地把这个问题分解为较小部分，找出各个的解，然后再把各部分的解组合成整个问题的解，这就是所谓的分治法。把一个大的处理对象分割为小对象，如果小对象仍用原方法处理，就是递归；如果小对象用不同的算法处理，就是分治。常用算法3、分治法老大大头目小头目喽啰大头目小头目小头目小头目喽啰喽啰喽啰喽啰喽啰喽啰喽啰常用算法6、回溯法在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解。回溯法的实质是不断试错，出错则返回。常用算法4、回溯法老大大头目小头目喽啰大头目小头目小头目喽啰喽啰喽啰喽啰算法分析评价一个算法，我们主要关心以下三个问题：◦算法的复杂度时间复杂度----执行算法的计算工作量，即算法的时间代价。衡量算法工作量的方法：执行算法所需时间作为算法工作量的度量。算法程序中所执行的指令条数或语句条数作为度量。语句执行的次数作为度量。空间复杂度----执行算法所需的内存空间，包括：算法程序所占的空间输入初始数据所占的空间算法执行过程中所需的额外空间，包括：算法执行过程中的工作单元数据结构所需的附加空间算法分析1、递归法2、递推法老大老二老三大头目小头目喽啰𝑶𝟐𝒏𝑶𝒏算法的最优性----衡量算法的好坏主要依据算法的复杂度，特别是时间复杂度。通常总是在最坏的情况下分析算法的工作量。◦最优算法是指在解决一个问题时，如果在被研究的算法类中，没有一个算法比现有算法执行更少的基本运算，则称此算法是最优的。快速算法的设计----与工程上常用的算法相比，其时间复杂度较小。◦快速算法不一定是最优算法。