算法程序与编程

《算法程序与编程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章算法、程序与编程问题的提出：人是如何来解决问题的？人是如何解决复杂问题的？计算机如何来解决问题的？问题的解决——计算机算法、程序与编程第四章算法、程序与编程学习目的和要求：了解算法与程序概念理解算法的复杂性与NP问题熟悉基本算法知道数据和数据结构熟悉高级语言掌握程序设计规划了解程序理论和软件工程一种逐步解决问题或完成任务的方法输入列表输出列表算法寻找最大值的一个算法(1)输入5个数，输出其中的最大值1.输入：算法接受一组5个整数的数据。2.过程第一步检查第一个整数，把这个整数赋给变量Largest第二步把第二个数与Largest中的数进行比较，如大于Largest中的数就将该

2、数赋予它，否则，Largest中的数不变第三步把第三个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变。此时13大于12，所以，变量Largest中变为13。寻找最大值的一个算法(2)第四步把第四个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变。此时第四个数是9，小于13，所以Largest中的数不变。第五步把第四五个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变。此时第五个数是11，小于13，所以Larg

3、est中的数不变。3.输出最大值13结束算法的例子示意图算法的精化算法的泛化三种结构算法的基本结构流程图算法的表示伪代码：是在编写算法时，为了更好地表示算法本身，不在一些小的细节上纠缠，而采用类似于英语（或其他自然语言）表示算法的算法表示方法。伪代码用伪代码写出一个求两个数的平均值的算法例1AverageOfTwoInput:TwonumbersAddthetwonumbersDividetheresultby2Returntheresultbystep2EndAlgorithm8.1:AverageoftwoPass/NoPassGradeInput:Onenumberif(th

4、enumberisgreaterthanorequalto60)then1.1Setthegradeto“pass”else1.2Setthegradeto“nopass”EndifReturnthegradeEndAlgorithm8.2:Pass/nopassGrade用伪代码写出一个可以把不同数值成绩分成及格或不及格的算法例2LetterGradeInput:Onenumber1.if(thenumberisbetween90and100,inclusive)then1.1Setthegradeto“A”Endif2.if(thenumberisbetween80and8

5、9,inclusive)then2.1Setthegradeto“B”EndifAlgorithm8.3:Lettergrade用伪代码写出一个可以把数字型成绩变成字母等级成绩的算法例3Algorithm:Lettergrade(continued)Continuesonthenextslide3.if(thenumberisbetween70and79,inclusive)then3.1Setthegradeto“C”Endif4.if(thenumberisbetween60and69,inclusive)then4.1Setthegradeto“D”Endif算法的定义

6、算法定义1：算法是一组明确步骤的有序集合，它产生结果，并在有限的时间内终止。有序集合明确步骤产生结果在有限的时间内结束算法定义2：（1）给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法是精确刻画。特别地，算法具有以下特征属性：①算法应用于一个具体的输入集合或问题描述将在有穷步动作之后得到结果；②该序列有一个唯一的初始动作：③该序列中的每一个动作有一个唯一的后继动作④该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。算法定义3：一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定型问题的运算序列。此外，算法的规则序列必须满

7、足以下5个重要条件，即具有以下五个特性：（1）有穷性。算法必须总是在执行有穷步之后结束（2）确定性。算法的每一个步骤必须是确切地定义的；（3）输入。算法有零个或多个输入（4）输出。算法有一个或多个输出，即与输入有某个关系的量。（5）能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上是能够精确地进行的，而且用笔和纸做有穷次就可以完成。计算的复杂性与NP问题计算的复杂性（算法的复杂性）的概念计算空间的复杂性计算时间的复杂性相似性与对偶原理：计算空间与计