第1章算法求解基础课件

计算机算法分析与设计

任课教师：周文刚周口师范学院计算机科学系1周口师范学院计算机科学系学习目标掌握算法分析与设计的基本理论掌握进行算法分析与设计的基本方法（时间、空间复杂度分析，算法正确性的证明）掌握计算机领域中常用的非数值计算方法，并学会用这些算法解决实际问题2周口师范学院计算机科学系课程要求教学方式：理论(72学时)考核方式：考试(70%)+实验作业(30%)先修课程：《数据结构》《C语言程序设计》3周口师范学院计算机科学系授课教材选用教材：《算法设计与分析》

陈慧南电子工业出版社参考书目：《算法引论》张益新，沈雁国防科技大学出版社《计算机算法设计与分析》王晓东电子工业出版社4周口师范学院计算机科学系第一章导引

---计算机算法分析与设计是面向设计的、处于核心地位的教育课程

---计算机算法是计算机科学和计算机应用的核心。1.什么是算法？2.如何分析算法？3.如何表示算法？4.基本数据结构5周口师范学院计算机科学系1.什么是算法算法数值计算方法（求解数值问题，插值计算、数值积分等）非数值计算方法（求解非数值问题，主要进行判断比较）算法笼统的定义：求解确定一类问题的任意一种特殊方法。非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。6周口师范学院计算机科学系算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。7周口师范学院计算机科学系程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。8周口师范学院计算机科学系问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法9周口师范学院计算机科学系算法复杂性分析

算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。10周口师范学院计算机科学系描述算法的方法自然语言伪代码流程图程序特别注意算法描述≠程序特别在科技论文写作时，一般不能写原程序，而应通过伪代码或流程图描述11周口师范学院计算机科学系例1求两个正整数m,n的最大公因子算法1-1欧几里得算法输入：正整数m和n输出：m和n的最大公因子第一步：求余数。rm%n第二步：判断r=0?，若是，终止(n为答案)，否则，转第三步。第三步：互换,mn,nr,返回第一步。BeginRm%nr=0？Swap(m.n)EndNY12周口师范学院计算机科学系例1求两个正整数最大公因子的一个实例假设m=21和n=45，求21和45的最大公因子第一步：r=m%n=21%45=21；第二步：r不等于0，转入第三步；第三步：互换，m=n=45,n=r=21，返回第一步。第一步：r=m%n=45%21=3；第二步：r不等于0，转入第三步；第三步：互换，m=n=21,n=r=3，返回第一步。第一步：r=m%n=21%3=0；第二步：r等于0，算法结束，3即为21和45的最大公因子。13周口师范学院计算机科学系算法的五个重要特性确定性每一种运算必须要有确切的定义，无二义性可行性运算都是基本运算，原理上能在有限时间内完成输入有 1个或多个输入输出一个或多个输出有穷性在执行了有穷步运算后终止14周口师范学院计算机科学系算法的特性凡是算法，都必须满足以上五条特性。只满足前四条特性的一组规则不能称之为算法，只能叫做计算过程。操作系统就是计算过程的一个典型例子。设计操作系统的目的是为了控制作业的运行，当没有作业时，这一计算过程并不终止，而是处于等待状态，一直等到一个新的作业的进入。15周口师范学院计算机科学系算法学习的五个内容如何设计算法运用一些基本设计策略规划算法如何表示算法用恰当的方式表示算法如何确认算法算法正确性的证明(算法确认algorithmvalidation)如何分析算法通过时间和空间复杂度的分析，确定算法的优劣如何测试程序测试程序是否会产生错误的结果16周口师范学院计算机科学系1.1.2为什么学习算法只有具有良好的算法基础才能成为训练有素的软件人才能让人更聪明，掌握更多的解决问题的方法17周口师范学院计算机科学系1.2问题求解方法算法是问题的程序化解决方案1、问题和问题求解2、问题求解过程理解问题设计方案编程实现复查18周口师范学院计算机科学系3、系统生命周期分析设计编码测试维护19周口师范学院计算机科学系1.3算法设计与分析1、问题求解过程精确算法启发式算法（近似算法）－－简化和智能猜测可行解最优解启发式算法并不总能导致理想解，但常常能在合理的时间内求得令人满意的结果20周口师范学院计算机科学系4、如何确认算法数学归纳法证明或实例验证21周口师范学院计算机科学系1.4递归和归纳1、递归直接或间接引用自己的定义方法包括基础情况和递归部分longFib(longn){

if(n<=1)returnn;elsereturnFib(n-2)+Fib(n-1);}22周口师范学院计算机科学系将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。23周口师范学院计算机科学系算法总体思想对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。24周口师范学院计算机科学系算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)25周口师范学院计算机科学系算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

26周口师范学院计算机科学系1.4.1递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例。27周口师范学院计算机科学系1.4.1递归的概念例1阶乘函数

阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。28周口师范学院计算机科学系1.4.1递归的概念例2Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算如下：int

fibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}29周口师范学院计算机科学系2.1递归的概念例3Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：30周口师范学院计算机科学系Hanoi塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。31周口师范学院计算机科学系hanio(n,A,B,C)盘子数，原在杆，目标杆，借助杆32周口师范学院计算机科学系在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n＞1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。Hanoi塔问题例6Hanoi塔问题

voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}33周口师范学院计算机科学系递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。34周口师范学院计算机科学系求最大公约数例子Example1

35周口师范学院计算机科学系递归例子：Fibonacci数列定义F(n)=1, n=01, n=1F(n-1)+F(n-2), n>1非递归部分,终止条件递归部分,起始条件求Fibonacci数列算法ProcedureF(n) integern ifn≤1thenreturn(1) elsereturn(F(n-1)+F(n-2)) endifEndF36周口师范学院计算机科学系1.5递归和消去递归递归直接调用自己或间接通过一些语句调用自己优点：描述某些数学问题非常自然，证明算法很容易。缺点：执行时间、空间消耗多一个递归问题可分为“回推”和“递推”两个阶段未知已知递推回推37周口师范学院计算机科学系用递归实现求最大公因数ProcedureGCD(a,b)ifb=0thenreturn(a)elsereturn(GCD(b,amodb))

endifEndGCD例如：a=22,b=8求GCD(22,8)=？38周口师范学院计算机科学系GCD(22,8)GCD(8,6)GCD(6,2)GCD(2,0)2回推回推回推回推递归递归递归递归用递归实现求最大公因数结果为GCD(22,8)=239周口师范学院计算机科学系消去递归递归的优点：与数学定义相似，容易编写算法递归的缺点：计算时间长，很多值都被重复计算了多次消去递归目的是克服递归时间空间的开销解决方法：先使用递归，然后证明所设计的递归算法正确并且确信是一个好算法，再把递归消去，翻译成与之等价的只使用迭代的算法。直接递规翻译成迭代过程的规则40周口师范学院计算机科学系小结算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。算法的五个重要特性确定性、可行性、输入、输出、有穷性算法分析是对一个算法需要多少时间和存储空间作定量分析。递归和消去递归41周口师范学院计算机科学系作业

1－11－91－1442周口师范学院计算机科学系第2章算法分析基础2.1算法复杂度好的算法应该具备：正确简明高效最优健壮43周口师范学院计算机科学系2.如何分析算法算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法分析步骤：首先确定使用那些运算以及执行这些运算所用的时间。(运算包括基本数值运算和一些更基本的任意长序列的运算)其次是要确定出能反映算法在各种情况下工作的数据集。（即要求我们编造出能产生最好、最坏和有代表性情况的数据配置，通过使用这些数据来运行算法，以更了解算法的性能）44周口师范学院计算机科学系全面分析一个算法的两个阶段事前分析(apriorianalysis)求出该算法的一个时间限界函数(一些关于参数的函数)事前分析只限于每条语句的频率计数(frequencyc