软件技基础_算法ppt课件.ppt

《软件技基础_算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章算法2.1算法的概念2.2算法的种类2.3算法的评估2.1算法的概念2.1.1算法的基本概念算法是指在处理问题的过程中所采取的方法和步骤。计算机解决问题的方法和步骤就是计算机的算法。通常，算法又分为数值型算法与非数值型算法。非数值型算法又称为符号处理。算法重在过程或方法，而给不了问题求解的结果。2.1.2算法的基本特征（1）可行性①算法中的每一个步骤必须能够实现。②算法执行的结果要能够达到预期的目的。（2）确定性算法的确定性（Definiteness），是指算法中的每一个步骤都必须是有明确定义的，不能有二义性。（3）有穷性算法的有穷性（Finiteness），是指算法必须能在有限的时间内

2、做完，即算法必须能在执行有限个步骤之后终止。（4）输入一个算法中可以有零个或多个输入。（5）输出一个算法中可以有一个或多个输出。2.2.1算法描述1.自然语言自然语言描述算法通俗易懂，但它有着难以克服的缺陷：(1)易产生歧义性(2)语句繁琐冗长，很难清楚地表达算法的逻辑流程(3)当今的计算机尚不能处理用自然语言表示的算法2.2算法的种类2.专用工具常用的有流程图、PAD图和N-S图、伪代码等3.程序设计语言为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。在本书中为类C语言。流程图是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作2.2.2算法设计基本方法

3、简介1．列举法列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。2．枚举归纳法枚举归纳法的基本思想是，通过列举足够多（但不是全部）的特殊情况，发现其中的一些规律，经过分析，最后找出一般的关系。3．递推递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。例：求阶乘f(n)＝n!＝n×(n-1)!＝n×f(n-1)要计算10!，可以从递推初始条件f(0)=1出发，应用递推公式f(n)=n×f(n-1)逐步求出f(1)、f(2)…、f(9)、最后求出f(10)的值4．递归这种将问题逐层分解的过程，实际上并没有对问题进行求解，

4、而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。由此可以看出，递归的基础也是归纳。递归分为直接递归与间接递归两种。如果一个算法P直接调用自己则称为直接递归。如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。5．减半递推技术“减半”是指将问题的规模减半，而问题的性质不变。“递推”是指重复“减半”的过程。6．回溯法ProcBacktracking(succ:Boolean)确定起始状态值走第一步确定下一步还有几种可能选一可能走下一步，记住可能和本步特征做完新一步应做的事While目标未达到do确定下一步有几种可能While没有可能

5、and还有上一步do回退上一步查有无下一可能EnddoIf上一步没有了Thenreturn(SUCC=FALSE)EndIf选一可能走的一步，记住可能和本步特征做完新一步应做的事Enddoreturn(SUCC=TRUE)EndBacktracking回溯法2.3.1算法的设计要求对于同一个问题，各人编写的算法（或程序）往往是不同的。算法评估的目的正是希望找到一个评价标准，来对这些算法进行评价，从而选出较合适的一种。2.3算法的评估例2-1：计算S=1+2+3+…+n/*算法1*/voidmain(){longs=0;for(inti=1;i

6、n",s);}/*算法2*/voidmain(){longs=(1+n)*n/2;printf("%d",s);}（1）正确性正确性是设计和评估一个算法的首要条件。算法的正确性可通过理论推导及实验测试两方面判定。（2）可读性（3）效率和存储量效率指的是确定条件下算法的运行时间。执行时间越短，效率越高。（4）简单性简单的算法便于编写、修改、调试以及交流，但效率往往不高。2.3.2算法效率的度量算法效率的度量主要包括时间度量和空间度量。1．算法的时间度量假定：计算机执行简单操作所需要的时间是相等的。算法的时间度量标准即算法中进行简单操作的次数，也称时间复杂度，用表示。常用的简单操作：四则运算及

7、赋值（=,+=,-=,*=,/=）比较（>,>=,==,<,<=）例2-2：求n个数的平均值/*求n个整数的平均值的算法*/intave(inta[],intn){ints,i;s=0;/*1*/for(i=0;i