《计算机程序设计基础——绪论》由会员分享，可在线阅读，更多相关《计算机程序设计基础——绪论（71页珍藏版）》请在金锄头文库上搜索。
1、04:07,1,自 我 介 绍,姓名：王坤 E-mail: Phone: 13060065885,04:07,2,教 学 用 书,西南交通大学出版社 计算机程序设计基础（C+） 2009年2月第1版,04:07,3,第一章 引论,西南交通大学软件学院 计算机基础教研室,计算机程序设计基础与Visual C+,04:07,4,教学内容,1程序设计和软件开发的概念； 2. 程序设计语言发展史 3算法的相关概念； 4程序设计过程的简单示例,04:07,5,一、什么是程序？,程序就是让计算机完成某项任务的一系列命令的集合。 人们编写程序的过程称为程序设计（程序开发）。,程序设计和软件开发的概念,程序
2、作为商品以有形介质为载体进行交易时即为软件 软件泛指程序和相关文档的集合 文档是为方便了解程序所需要的资料说明,二、什么是软件？,三、软件开发过程：,从开始软件的研制到废弃该软件的整个期间，称为软件生命期 传统的软件开发过程可划分为问题定义与可行性研究、需求分析、概要设计、详细设计、编码和单元测试、测试和使用维护七个阶段 每一阶段的工作建立在前一阶段工作的基础上,问题定义与可行性研究： 关键的任务是要确切地定义用户“要解决的问题是什么?”，“有可行的解吗?” 需求分析： 目的是要弄清楚系统应该/必须“做什么”，需求分析是软件开发项目得以成功的基础,概要设计： 回答“应该如何解决这个问题”，“总
3、体上说，系统应该如何实现” 详细设计： 目标是确定应该怎样具体地实现所要求的系统,编码和单元测试： 把对于软件的定义、描述和设计的结果翻译成计算机能“理解”和执行的形式 测试： 通过精心选择的测试数据，观察程序执行的结果是否与规定的预期结果相符,使用维护： 校正性维护排除使用中暴露出的错误 适应性维护使软件适应运行环境变化 完善性维护对软件的功能加以扩充,四、程序设计方法：,1. 面向过程的程序设计 为了得到问题的解而执行的一步一步的操作，称为过程 面向过程的程序设计是一种基于功能分析及每个功能由计算机的一个操作过程实现的程序设计方法，又称为传统的程序设计。面向过程程序设计的关键是规划算法和数
4、据结构,程序=算法+数据结构,2. 面向对象的程序设计 面向对象程序设计模拟自然界认识和处理事物的方法，将数据和对数据的操作方法组织在一起，形成一个相对独立的整体，称为对象 对象是活动的，对象行为靠消息触发而激活。面向对象程序设计的关键是确定对象并对其分类,程序=对象+对象+. 对象=算法+数据结构,五、程序设计过程 ：,1分析问题 通过原始资料，取得对问题的一个清晰的理解，进而确定解决问题的目标（称为输出）以及实现该目标所需要的条件（称为输入）,2设计算法与数据结构 数据结构描述了问题涉及的对象之间的联系和组织结构；算法描述了求解问题的步骤或规则。设计合理的数据结构可以简化算法，好的算法使程
5、序具有更高的效率,3检查算法 使用多组样本数据，通过手工计算，对方案的正确性进行证明和验证 4编码实现 选用一种程序设计语言（如C+语言）将算法转换成计算机能够理解的程序（称为编程）,5测试和调试程序 “测试”是在计算机上用样本数据运行程序，测试代码的正确性。“调试”就是查找和排除程序错误，直到能够得到正确的运行结果为止 程序中的错误可能是语法错误，也可能是逻辑错误。大多数语法错误容易找到和改正，但逻辑错误就较难找到，因为导致逻辑错误的原因很多,04:07,18,程序设计语言发展史,程序设计语言（计算机语言） 人与机器交换信息的语言。 四个阶段： 1.机器语言 2.汇编语言 3.面向过程的高级
6、语言 4.面向对象的高级语言,1.机器语言： 由二进制数组成的指令代码的集合，机器能直接识别，各种机器指令系统互不相同。 计算机编码： 常用ASCII码（美国标准信息交换编码）American Standard Code for Information Interchange,示例：按ASCII码将 A=1+2 写成机器语言 字符 ASCII码 十进制 A 01000001 65 = 00111101 61 1 00110001 49 + 00101011 43 2 00110010 50,按ASCII码写出的A=1+2的机器语言： 010000010011110100110001001010
7、110011001 机器语言优点： 质量高、执行速度快、占存储空间小。 机器语言缺点： 编程难度大、指令难记、繁琐、直观性差、容易出错、检查调试困难、通用性差不兼容。,2.汇编语言 用助记符代替指令代码，符号化 例： ADD （加法） DIV （除法） 汇编语言不能直接在机器上运行，要转换成机器语言才能执行。,例：汇编语言源程序： main proc pay mov ax,dseg mov ax,0b00h add ax,dx mov al,bl mul bl,ax mov bl,04h,汇编语言优点：质量高、执行速度快、占存储空间小、可读性有所提高。 汇编语言缺点：类似机器语言，通用性、可移
8、植性差，与人的自然语言还相差很悬殊。 机器语言和汇编语言也称为低级语言。,3.面向过程的高级语言 特点：接近人们习惯用的自然语言和数学语言，通用性强，可移植性好。 input “Entername”;name$ input “Enterhoursworked”;hours input “Enter pay rate”;rate grossPay=hours*rate federalTax=.02*grossPay socSecTax=.07*grossPay stateTax=.06*grossPay netPay=grossPay-federalTax-socSecTax-stateTax
9、print name$,netPay,常见语言： BASIC 、PASCAL、FORTRAN、C、 高级语言所编写的程序同样不能直接在计算机上执行，要转换成机器指令代码。 两种转换方式： (1)编译方式 通过编译程序（编译、链接）将整个程序转换为机器语言。 (2)解释方式 通过解释程序，逐行转换为机器语言，转换一行运行一行。,编译方式：,解释方式：,4.面向对象的高级语言 面向对象的程序设计方法： 围绕真实世界的概念来组织模型。 class Date public: void changeDate(int month,int day,int year); void displayDate();
10、 private: int month; int day; int year; ; Date payDay;,常见的面向对象程序设计语言： Visual C+、Visual Basic、Java. 面向对象的程序设计方法的优点： 问题求解更容易 程序的编制、调试和维护更容易,04:07,30,算法的相关概念,一、什么是算法？ 算法是解决某类具体问题的方法，是解决问题的步骤序列 二、什么是计算机算法？ 是指利用计算机解决问题的方法，简称算法，分为数值算法和非数值算法两大类,三、算法的主要特征：,有效性： 算法中的每一步骤都应当是可执行的，并能得到确定的结果。 有穷性： 算法应该在执行有限的步骤后
11、结束，不能是无限的。,确定性： 组成算法的每一步骤应该有确定的语义，不能有任何歧义。 有零个或多个输入： 部分数据在操作之前需要通过外界赋值，称为输入。 有一个或多个输出： 算法的运算结果即是算法的输出。,四、算法的主要因素：,五、算法的表示方法,1.自然语言 2.传统流程图 3.结构化流程图 4.N-S流程图 5.伪代码,1.自然语言表示算法,例 计算n!,？2I,2.传统流程图表示算法,04:07,39,04:07,40,例将求5！的算法用传统流程图表示,3.结构化流程图表示算法,（1）顺序结构,1966年，Bohra和Jacopini提出了三种基本结构作为表示算法的基本单元,(2) 选择
12、结构(又称选取结构),04:07,43,(3) 循环结构(又称重复结构),04:07,44,4.N-S流程图描述算法, 选择结构, 循环结构,例 用N-S流程图表示求5!的算法,5.伪代码描述算法,例 用伪代码表示求5!的算法,六、算法设计策略,1.枚举法 枚举法也称为穷举法，其设计思想是：在有限的范围中，列举和检验所有可能的结果，从中找出那些符合要求的候选解作为问题的解,04:07,51,【例】设有算式：A B C D- C D C=A B C，其中的A、B、C、D 均为一位非负整数，要求找出A、B、C、D各值 思路分析：设正整数A、B、C、D，A和C的取值范围应是1，9，B和D的取值范围应
13、是0，9，分别对相应范围中的每一个数值进行检测，输出满足条件（1000a100b10cd）-（100c10dc）=（100a10bc）的数值,04:07,52,算法描述： for a1 step 1 until 9 do for b 0 step 1 until 9 do for c 1 step 1 until 9 do for d 0 step 1 until 9 do x1000a100b10cd y100c10dc z100a10bc if x-y=z then 输出a,b,c,d end,2.递推法 递推法的设计思想是：利用问题本身所具有的一种递推关系求问题的解，即从已求得的规模为1
14、，2，n-1的一系列解，构造出问题规模为n的解,例计算n!,思路分析：1!=1，由1!2得2! 由2!3得3! 由(n-1)!n得n!。 算法描述： f1 i1 while in do ffi ii1 print f,3.递归法 递归法的设计思想是：为求解规模较大的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解,04:07,56,例计算斐波那契数列的第n项值,思路分析：斐波那契数列为:0、1、1、2、3、 即
15、f(0)=0 f(1)=1 f(n)=f(n-1)+f(n-2) (当n1时) 算法描述： call Fibonacci (n) if n=0 then return 0 if n=1 then return 1 if n1 then return Fibonacci(n-1)+ Fibonacci(n-2),4.分治法 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。由分治法产生的子问题往往是原问题的较小模式，在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解，这自然导致递归
16、过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法,04:07,58,例 欲在按非降次序排列的n个元素 a1,a2,an(aiai+1)中查找是 否有与b相同的元素。,七、算法复杂性分析,04:07,59,算法二：采用折半查找(二分查找)的方法，即先用位居中点的元素a（n/2）与b比较，若b= a（n/2），则查找成功。若ba（n/2），同时ba（n/2），则在a1,a2, ,a（n/2-1）中采用上述方法继续查找；否则在a（n/2+1）,a（n/2+2）,an 中采用上述方法继续查找。这种算法显然要优越于前一种算法，因为最多也只需要比较log2n次。,不同类型的问题有不同的算法 同一类型的问题也有多种算法 解决一个实际问题时，可能会有多种算法可供使用，我们需要对这些算法进行分析，选
