四章算法程序与编程.ppt
《四章算法程序与编程.ppt》由会员分享,可在线阅读,更多相关《四章算法程序与编程.ppt(73页珍藏版)》请在三一文库上搜索。
1、第四章 算法、程序与编程,问题的提出: 人是如何来解决问题的? 人是如何解决复杂问题的? 计算机如何来解决问题的? 问题的解决计算机算法、程序与编程,第四章 算法、程序与编程,学习目的和要求: 了解算法与程序概念 理解算法的复杂性与NP问题 熟悉基本算法 知道数据和数据结构 熟悉高级语言 掌握程序设计规划 了解程序理论和软件工程,一种逐步解决问题或完成任务的方法,输入列表,输出列表,算法,寻找最大值的一个算法(1),输入5个数,输出其中的最大值 1.输入:算法接受一组5个整数的数据。 2.过程 第一步 检查第一个整数,把这个整数赋给变量Largest 第二步 把第二个数与Largest中的数进
2、行比较,如大于Largest中的数就将该数赋予它,否则,Largest中的数不变 第三步 把第三个数与Largest中的数进行比较,如大于Largest中的数就将该数赋予它,否则,Largest中的数不变。此时13大于12,所以,变量Largest中变为13。,寻找最大值的一个算法(2),第四步 把第四个数与Largest中的数进行比较,如大于Largest中的数就将该数赋予它,否则,Largest中的数不变。此时第四个数是9,小于13,所以Largest中的数不变。 第五步 把第四五个数与Largest中的数进行比较,如大于Largest中的数就将该数赋予它,否则,Largest中的数不变。
3、此时第五个数是11,小于13,所以Largest中的数不变。 3.输出 最大值13 结束,算法的例子示意图,算法的精化,算法的泛化,三 种 结 构,算法的基本结构,流程图,算法的表示,伪代码:是在编写算法时,为了更好地表示算法本身,不在一些小的细节上纠缠,而采用类似于英语(或其他自然语言)表示算法的算法表示方法。,伪代码,用伪代码写出一个求两个数的平均值的算法,例1,AverageOfTwo Input: Two numbers Add the two numbers Divide the result by 2 Return the result by step 2 End,Algorith
4、m 8.1:,Average of two,Pass/NoPassGrade Input: One number if (the number is greater than or equal to 60) then 1.1 Set the grade to “pass” else 1.2 Set the grade to “nopass” End if Return the grade End,Algorithm 8.2:,Pass/no pass Grade,用伪代码写出一个可以把不同数值成绩分成及格或不及格的算法,例2,LetterGrade Input: One number 1. i
5、f (the number is between 90 and 100, inclusive) then 1.1 Set the grade to “A” End if 2. if (the number is between 80 and 89, inclusive) then 2.1 Set the grade to “B” End if,Algorithm 8.3:,Letter grade,用伪代码写出一个可以把数字型成绩变成字母等级成绩的算法,例3,Algorithm :,Letter grade (continued),Continues on the next slide,3.
6、if (the number is between 70 and 79, inclusive) then 3.1 Set the grade to “C” End if 4. if (the number is between 60 and 69, inclusive) then 4.1 Set the grade to “D” End if,算法的定义,算法定义1:算法是一组明确步骤的有序集合,它产生结果,并在有限的时间内终止。 有序集合 明确步骤 产生结果 在有限的时间内结束,算法定义2: (1)给定问题和设备,一个算法是用该设备可理解的语言表示的,解决这个问题的一种方法是精确刻画。特别地
7、,算法具有以下特征属性: 算法应用于一个具体的输入集合或问题描述将在有穷步动作之后得到结果; 该序列有一个唯一的初始动作: 该序列中的每一个动作有一个唯一的后继动作 该序列终止时或者得到这个问题的解,或者因该问题不可解而获得不可解说明。,算法定义3:一个算法,就是一个有穷规则的集合,其中之规则确定了一个解决某一特定型问题的运算序列。此外,算法的规则序列必须满足以下5个重要条件,即具有以下五个特性: (1)有穷性。算法必须总是在执行有穷步之后结束 (2)确定性。算法的每一个步骤必须是确切地定义的; (3)输入。算法有零个或多个输入 (4)输出。算法有一个或多个输出,即与输入有某个关系的量。 (5
8、)能行性。算法中有待执行的运算和操作必须是相当基本的,即是说,它们原则上是能够精确地进行的,而且用笔和纸做有穷次就可以完成。,计算的复杂性与NP问题,计算的复杂性(算法的复杂性)的概念 计算空间的复杂性 计算时间的复杂性 相似性与对偶原理:计算空间与计算时间的互换性 算法复杂性的描述:算法在执行过程中总共所需要的初等运算的步数来表示算法用于求解任一问题的某一例子时所需的时间。,计算的复杂性与NP问题(2),算法复杂性的表示 多项式时间算法:是指存在某个以输入长度n为变量的多项式函数中(n),使其时间复杂性函数为O(p(n)的算法。因此复杂性为O(n)、O(106n3)、O(5n8)等算法均为多
9、项式时间算法。 指数时间算法:是指任何其时间复杂性函数不可能如上用多项式函数去界定的算法,例如O(2n)、O(n!)、O(nn)、O(2n2)等都在算法上是不可接受的。,计算的复杂性与NP问题(3),时间复杂性的表示 O(1)称为常数级; O(logn)称为对数级; O(n)称为线性级; O (nc)称为多项式级,(C为常数); O (Cn)称为指数级,(C为常数); O (n!)称为阶乘级;,计算的复杂性与NP问题(4),P类与NP类问题:一个算法如果存在图灵机可计算的多项式时间计算复杂性算法,就将该算法归入P类;如果存在非确定性图灵机可计算的多项式时间计算复杂性算法,就将其归入NP类。 P
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 程序 编程
链接地址:https://www.31doc.com/p-3208182.html