计算机应用基础讲程序设计基础PPT课件.ppt

可编辑 1 如何正确对待不感兴趣的课 2020 3 18 请在 我学网 开复学生网 上阅读 第九章程序设计基础 可编辑 2 9 1算法与程序设计概述 2020 3 18 9 1 1程序的概念9 1 2算法的概念及特征1 算法的特征2 算法的评价9 1 3算法的表示方法1 用自然语言表示2 用传统流程图表示3 N S流程图4 用伪代码表示9 1 4简单的程序设计实例 下一讲 9 1算法与程序设计 可编辑 3 2020 3 18 1 程序 先看生活中的程序 现实生活中 程序的直观特征是按事先安排的步骤 一步步完成一系列动作 这种对活动过程的步骤描述就是一个 程序 在计算机领域 程序是指为让计算机完成特定的任务而设计的指令序列 它是程序设计人员编写的 计算机能够理解并执行的一些命令的集合 是解决问题的具体步骤在计算机中的实现 9 1 1程序的概念 可编辑 4 2020 3 18 计算机中的问题事例 例1 求解一元二次方程4 346 51 24X 8 0例2 求解一元二次方程a bX c 0例3 设a 0 b 0 c 0 若以正数a b c为三角的三条边 求三角形abc的面积 可利用海伦公式 例4 求10以上200以下的整数中 能被3整除但不能被5整除的所有数据之和 9 1 1程序的概念 可编辑 5 2020 3 18 计算机中的程序与日常生活中的程序的概念是类似的 只不过执行日常生活程序的主体是人 而执行计算机程序的主体是计算机 计算机程序就是要由计算机进行解释和执行的程序 它表示的是计算机处理事务的时间顺序和处理问题的步骤 程序只能由计算机可以解释和执行的基本操作组成 组成计算机程序的基本单位一般称为指令 因此简单的说 程序就是事先编制好的具有特定功能的指令序列 9 1 1程序的概念 可编辑 6 2020 3 18 2 程序设计既然程序是按一定次序编排的指令序列 那么编写指令序列的过程就是程序设计 用什么来编写指令序列 由于指令序列是给计算机执行的 因此这些指令应该是以计算机能够理解的语言表示的 这种语言就是程序设计语言 现在能够充当人和计算机之间的交流工具的 就是计算机语言 包括各种命令语言和程序设计语言 主要是程序设计语言 9 1 1程序的概念 可编辑 7 2020 3 18 例1的FoxPro程序A 4 346B 51 24C 8X1 B SQRT B B 4 A C 2 A X2 B SQRT B B 4 A C 2 A X1 X1 X2 X2 9 1 1程序的概念 可编辑 8 2020 3 18 例2的FoxPro程序INPUT 输入数据到A TOAINPUT 输入数据到B TOBINPUT 输入数据到C TOCIFB B 4 A C 0X1 B SQRT B B 4 A C 2 A X2 B SQRT B B 4 A C 2 A X1 X1 X2 X2ELSE 无实数解 ENDIF 9 1 1程序的概念 可编辑 9 2020 3 18 例3的C语言程序 includemain floata b c p area scanf f f f 9 1 1程序的概念 可编辑 10 2020 3 18 例4的FoxPro程序sum 0n 10dowhilenn 5s s nendifstorn 1tonenddo 5 10say 10 200内被3整除但不能被5整除的所有数据之和为 str s 5 9 1 1程序的概念 可编辑 11 2020 3 18 1 算法的概念所谓算法是指解题方案的准确而完整的描述 算法是程序的灵魂 计算机程序设计的实质是算法的设计 自从计算机广泛用于解决现实问题以来 人们积累了大量的算法 这些算法是前人思想的结晶 也是新算法产生的基础 学习和研究这些算法 对解决实际问题 以及研究新的算法都是极为必要的 每个算法实际上是按解题要求从所有的指令系统操作中选择合适的操作所组成的一组指令序列 因此 计算机算法就是计算机能处理的操作所组成的指令序列 9 1 2算法的概念及特征 可编辑 12 2020 3 18 一个算法的功能不仅取决于所选用的操作 而且还与各操作之间的执行顺序有关 算法中各操作间的执行顺序称为算法的控制结构2 算法的基本要素一个算法通常由两种基本要素组成 一是对数据对象的运算和操作 二是算法的控制结构 一个算法的运算操作或控制结构无论是简单还是复杂 一般必须满足以下五个重要特性 有穷性 确定性 可行性 输入 输出 9 1 2算法的概念及特征 可编辑 13 2020 3 18 1 有穷性对于任意一组合法输入值 在执行有穷步骤之后一定能结束 即 算法中的每个步骤都能在有限时间内完成 2 确定性对于每种情况下所应执行的操作 在算法中都有确切的规定 使算法的执行者或阅读者都能明确其含义及如何执行 并且在任何条件下 算法都只有一条执行路径 3 可行性算法中的所有操作都必须足够基本 都可以通过已经实现的基本操作运算有限次实现之 4 输入一个算法有零个或多个输入 5 输出一个算法有一个或多个有效信息的输出 9 1 2算法的概念及特征 可编辑 14 2020 3 18 3 算法的评价 算法复杂度 解决同一个问题的算法可以有多种 不同人员的设计不尽相同 其效率也存在差别 一个不好算法可能导致程序要运行几天 几个月甚至几年 一个好的算法可能只要几分种 几秒钟就可以完成 在设计算法时 应当遵循以下原则 首先是保证算法的正确性其次要具有良好的可读性第三 算法应具有健壮性第四 算法执行时间的高效性第五 降低对存储空间的需求 9 1 2算法的概念及特征 可编辑 15 2020 3 18 一般而言 方法有优劣之分 算法的优劣可以有多种不同的评价标准 例如 可以从时间上来评价 也可以从空间上来评价 或者从其他的角度来评价 人们当然愿意选择较优的算法 因此 为了有效解题 不仅需要保证算法的正确性 还要考虑算法的质量 选择合适的算法 从时间上来评价算法的优劣 即执行时间短的算法效率高 用算法的时间复杂度来度量 所谓算法的时间复杂度是指执行算法所需要的计算工作量 可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量 9 1 2算法的概念及特征 可编辑 16 2020 3 18 例如 求1 2 100的结果 有人是先求1 2 再把和加上3 再加4 一直加到100 而高斯采取的办法是 先将这100个数分为若干个组 100 1 99 2 98 49 51 50 前面50个组每个组的和都是100 因此结果为50 100 50 当然还有其他的方法 从空间上来评价即为算法所需辅助空间越少越好 用算法的空间复杂度来度量 一个算法的空间复杂度 一般是指执行这个算法所需要的内存空间 一个算法所占用的存储空间包括算法程序所占的空间 输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间 9 1 2算法的概念及特征 可编辑 17 2020 3 18 1 用自然语言表示 教材中有例 2 用传统流程图表示3 N S流程图4 用伪代码表示 例 求1 2 100的和 算法描述如下 将1赋值给x 将2赋值给y 将x与y相加 结果存放在x中 将y加1 结果存放在y中 若y大于100 则输出结果x 算法结束 否则转步骤 算法继续执行 9 1 3算法的表示方法 可编辑 18 2020 3 18 例 求1 2 100的和 算法描述二 i 1 sum 0 即将1赋值给i 0赋值给sum sum sum i 即将sum i的结果保存到sum中 i i 1 判断是否i 100 如果是 转到步骤 否则 转到步骤 输出sum的值 算法结束 9 1 3算法的表示方法 可编辑 19 2020 3 18 2 用传统流程图表示传统流程图是用规定的一组图形符号 流程线和文字说明来表示各种操作的算法表示方法 9 1 3算法的表示方法 可编辑 20 2020 3 18 2 用传统流程图表示在算法设计中常用到三种基本流程控制结构 即顺序 分支和循环结构 顺序结构 每一个基本的处理单位顺序地被执行 9 1 3算法的表示方法 可编辑 21 2020 3 18 分支结构 又称作选择结构 根据逻辑条件的成立与否 选择执行不同的处理 当逻辑条件成立时 执行处理A 否则执行处理B 2 用传统流程图表示 循环结构 当逻辑条件成立时 反复执行处理A 直到逻辑条件不成立时结束 左 9 1 3算法的表示方法 可编辑 22 2020 3 18 2 用传统流程图表示求1到100的自然数的和流程图 9 1 3算法的表示方法 可编辑 23 2020 3 18 4 用伪代码表示 赋值 给一个变量赋值变量名 表达式例s 12x s 6 2 8 给多个变量赋相同的值变量名 变量名 变量名 表达式例x y z 3 5s t x y 9 1 3算法的表示方法 可编辑 24 2020 3 18 4 用伪代码表示 从键盘上输入数据到一个变量input 数据类型 to变量名例INPUT 姓名 TOXMINPUT 数值数据 TOS 输出一个或多个结果值output 结果提示 表达式 表达式 例OUTPUT 二次方程式的根为 X Youtput 1 100的数据和S sOUTPUTS 9 1 3算法的表示方法 可编辑 25 2020 3 18 4 用伪代码表示 分支 9 1 3算法的表示方法 可编辑 26 2020 3 18 单分支if语句组endif 双分支if语句组Aelse语句组Bendif 4 用伪代码表示 分支 9 1 3算法的表示方法 可编辑 27 2020 3 18 多分支 可省略 DOCASECASE语句组1CASE语句组2 CASE语句组NOTHER语句组N 1ENDCASE 注 逻辑运算符3个 NOTANDOR 4 用伪代码表示 循环 9 1 3算法的表示方法 可编辑 28 2020 3 18 DOWHILE ENDDO结构 当条件为真时执行循环体 DOWHILE循环体ENDDO FOR NEXT结构 不超越终值时执行循环体 FOR循环控制变量 初值 表达式 TO终值 表达式 STEP步长值 表达式 循环体NEXT 综合举例 例1 求数列1 1 2 3 5 8 13 21 前30项的数据和 X Y 1N S 2DOWHILEN 30G X YX YY GS S YN N 1ENDDOOUTPUT 数列1 1 2 3 5 8 13 21 前30项的数据和S SOUTPUT 数列当前项为 N 9 1 3算法的表示方法 可编辑 29 2020 3 18 例2 从键盘上任意输入十个非负数据 求平均值 sum 0count 1dowhilecount 10input 输入数值数据 toxifnotx 0sum sum xcount count 1endifenddooutput 10个数据的平均值 sum 10 9 1 3算法的表示方法 可编辑 30 2020 3 18 例3 求给定的十个数的平均值 教材例9 1 sum 0forcount 1to10step1input 输入数值数据 toxsum sum xnextout