(1)--ch1 程序设计基础知识1.ppt

《(1)--ch1 程序设计基础知识1.ppt》由会员分享，可在线阅读，更多相关《(1)--ch1 程序设计基础知识1.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1章章 程序设计基础知识程序设计基础知识核心概念核心概念n程序与程序语言n计算机程序、计算机语言n算法与算法描述n结构化程序设计方法学习目标学习目标n了解程序、计算机语言等基本概念n了解算法的概念及其特性n掌握常用的算法描述的方法n掌握结构化程序设计方法章节内容章节内容1.1 程序与程序语言 1.2 算法和算法描述 1.3 结构化程序设计方法 1.1 程序与程序语言程序与程序语言 1.1.1计算机程序计算机程序 现在的计算机都是基于冯诺依曼结构设计的，它们是由运算器、控制器、存储器、输入设备、输出设备等5部分构成，如图1-1所示。计算机硬件是由存储在存储器中的程序控制下自动运行的，将数据输

2、入到计算机，按照程序的指令序列处理数据，并把结果输出到输出设备。在计算机中，硬件是躯体，程序是灵魂，计算机的一切操作都是由程序控制的，离开了程序，计算机硬件什么功能都完成不了。内存（程序和数据）控制器运算器输入设备，如键盘输出设备，如显示器图1-1 计算机组成1.1 程序与程序语言程序与程序语言1.1.2计算机语言计算机语言 按照解决问题的需要，选择恰当的指令构成一组指令序列的过程就是编写程序。从语言的角度来看，使用一种语言，告诉计算机如何输入数据？如何处理数据？如何输出？这种功能受限制的语言就称为计算机语言。程序设计语言的发展总体上经历了从低级语言到高级语言的过程。其中，低级语言包括机器语言

3、、汇编语言等，高级语言包括Fortran、Basic、Pascal、Java、C和C+等。1.1.2计算机语言计算机语言1机器语言机器语言 机器语言是指一台计算机硬件的全部指令集合。指令是设计计算机系统时确定的1和0的序列，不同的1和0的序列就构成了特定计算机的指令集，计算机只能识别和执行这些二进制指令，所以称为机器指令。在计算机应用的早期，只能使用由0和1构成的指令来编写程序，但这些指令与人们习惯的语言差别太大，难学、难记、难写，只能由专家才能编写程序。程序难检查、难修改，这样大大限制了程序的开发和应用。另外，不同类型计算机系统的指令集往往各不相同，所以，在一台计算机上编写的机器语言程序要想

4、在另一台计算机上执行，必须修改程序，造成重复工作，这称为机器语言的可移植性比较差。1.1.2计算机语言计算机语言2汇编语言汇编语言 汇编语言也称为符号语言，它是用助记符来代替指令和地址，即用英文单词的简写和数字来简化二进制机器指令，比如MOV代表数据传递操作、MUL代表乘法运算等等。这样比较容易记住指令和编写程序，也容易读懂并理解程序在干什么，便于纠错及维护，提高了编程的效率。由助记符或者符号表示的指令集称为汇编语言。用汇编语言编写的程序是由符号构成，计算机不能识别更不能执行这些指令，必须通过汇编程序把由符号组成的程序转换成机器语言的指令序列，这个转化的过程就是汇编。助记符表示的指令和机器指令

5、基本上是一一对应的，汇编语言也是面向特定的计算机系统，所以称机器语言和汇编语言是低级语言，它们的可移植性都比较差，但用它们编写出来的程序效率高，很多操作系统、驱动程序和一些系统程序都是用汇编语言开发的。1.1.2计算机语言计算机语言3高级语言高级语言（1）高级语言的出现 人们习惯使用自然语言，使用面向机器的低级语言增加了程序设计和开发的难度。随着计算机科学与技术的发展，1954年，第一个完全脱离机器硬件的高级语言FORTRAN问世了，这种语言接近于数学语言和自然语言，程序中所用的语句和指令是用英文单词表示的，计算表达式的操作数及运算符和数学公式近似，非常容易理解，从而可以很方便地控制数据的输入

6、、处理和输出，语言的功能很强。由于这种语言不依赖于具体的计算机系统，编写的程序具有很强的可移植性，故称为高级语言。高级语言编写的程序称为源程序，计算机也不能识别，可以通过编译把源程序等价转换为机器语言表达的目标程序，才能执行；或者源程序通过解释，逐步执行1.1.2计算机语言计算机语言（2）程序设计语言的发展史）程序设计语言的发展史 高级语言的发展经历了从早期非结构化到结构化程序设计语言，从面向过程到面向对象程序语言的过程。相应地，程序或软件的开发也由最初的充满设计技巧的个人设计到小团队设计，最后发展为全球化协同程序开发的开放式软件工业生产的过程。1.2 算法和算法描述算法和算法描述用计算机求解

7、实际问题一般分为三个基本步骤用计算机求解实际问题一般分为三个基本步骤：n从实际问题中抽象出数学模型n设计解决该数学模型的算法n1984年的图灵奖获得者瑞士学者和计算机科学家尼克劳斯沃思(Niklaus Wirth)提出著名公式“数据结构+算法=程序”。n用计算机语言开发出对应的程序，运行该程序解决问题。1.2 算法和算法描述算法和算法描述程序设计必须掌握的内容：程序设计必须掌握的内容：n数据结构，程序中要处理和保存数据的描述，即指定数据的类型和数据的组织形式。n算法，对有限操作步骤的确定性描述。n程序设计方法，比如尼克劳斯沃思提出的结构化程序设计方法。n程序设计语言和程序开发平台，用集成的程序

8、语言开发工具编写、编辑、编译、调试程序，程序中的操作语句就是对算法的实现。1.2 算法和算法描述算法和算法描述1.2.1算法的概念算法的概念 算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的指令。从另外一个层面来看，算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。广义上讲，为解决一个问题而采取的方法和步骤，都称为算法。计算机算法分为数值算法和非数值算法两种。1.2 算法和算法描述算法和算法描述一个计算机算法应当具有以下5个基本特性：n有穷性。一个算法应包含有限个操作步骤。n确定性。算法中的每一个步骤都应当是明确的、无二义性，

9、而不应当是含糊的、模棱两可的。n可行性。算法的每一步都是能够实现的、可操作的，并得到确定的结果。也常称为算法的有效性。n输入。一个算法一般有零个或多个数据输入。n输出。一个算法一般有一个或多个输出。算法的目的就是为了求问题的“解”，这些解只有通过输出才能得到。1.2 算法和算法描述算法和算法描述1.2.2算法设计的要求算法设计的要求一个算法的设计需要注意以下四个方面。n正确性：算法的正确性包含四个层次，即算法不含语法错误、算法对于几组输入数据能够得出满足要求的结果、算法对于精心选择的典型及苛刻而带有刁难性的几组输入数据能够得出满足要求的结果、算法对于一切合法的输入数据都能产生满足要求的结果。n

10、可读性：算法主要是用于人的阅读与交流，可读性好有助于人们对算法的理解与掌握。n健壮性：当输入数据非法时，算法应适当地做出反应或进行处理，而不会产生错误的输出结果。n高效率和低存储量1.2 算法和算法描述算法和算法描述1.2.3算法的描述算法的描述一个算法可以用自然语言、计算机语言、数学语言、流程图、PAD图等来描述，或者用介于自然语言和计算机语言之间的伪代码来描述。对这些算法描述方法的唯一要求是必须精确地描述计算过程或步骤。好的描述方法使算法表达更加清晰和简洁。本书仅仅介绍几种常用的描述方法。1.用自然语言描述算法用自然语言描述算法自然语言就是人们日常生活、工作中使用的语言，可以是汉语、英语或

11、其它语言。1.2.3算法的描述算法的描述例例1.1求n的阶乘。如果n=6，即求123456连乘的积。设s代表连乘之积，t代表乘数，以自然语言描述求n的阶乘的算法：步骤1：使s=1，t=1；步骤2：让st，得到的乘积仍放在s中；步骤3：使t的值增加1；步骤4：如果tn那么转到步骤2继续执行；如果tn那么转到步骤5；步骤5：连乘结束，s中的值就是n的阶乘，输出s。用自然语言描述算法通俗易懂，但自然语言描述风格自由，比较适合描述简单问题的求解算法。如果问题复杂，描述会比较繁杂、冗长，并且也很难清楚地表达复杂逻辑的算法，比如判断和循环，容易出现“歧义性”，往往需要根据上下文判断语句的含义，这样算法很难

12、进行准确地设计、交流和使用。1.2.3算法的描述算法的描述2.用计算机语言描述算法用计算机语言描述算法 计算机高级程序设计语言具有很强的描述能力，接近计算机高级程序设计语言具有很强的描述能力，接近于自然语言和数学语言。但是用计算机语言描述的算于自然语言和数学语言。但是用计算机语言描述的算法实际上就是对算法的实现，通过编译或解释后直接法实际上就是对算法的实现，通过编译或解释后直接可以执行，这是算法设计的终极目的，这样违反了算可以执行，这是算法设计的终极目的，这样违反了算法描述方法所需要的简单、直观、抽象级别高的要求，法描述方法所需要的简单、直观、抽象级别高的要求，所以在算法设计过程中用计算机语言

13、描述算法是不合所以在算法设计过程中用计算机语言描述算法是不合适的。适的。3.用流程图描述算法用流程图描述算法 流程图是用一些几何图形、带方向的线条以及问题说流程图是用一些几何图形、带方向的线条以及问题说明来描述算法操作步骤的方法。该方法形象、简明直明来描述算法操作步骤的方法。该方法形象、简明直观、易于理解、便于交流，是描述算法的主要方法之观、易于理解、便于交流，是描述算法的主要方法之一。流程图分为传统的流程图、结构化流程图、一。流程图分为传统的流程图、结构化流程图、N-S流程图等多种。流程图等多种。1.2 算法和算法描述算法和算法描述n（1）传统流程图）传统流程图n传统流程图又称程序框图，美国

14、国家标准化协会ANSI（American National Standard Institute）规定了一些常用的流程图符号，如图1-2所示，这种符号目前已经被大多数国家接受和使用。起止框 输入/输出框 判断框处理框 流程线 连接符 注释框图1-2流程图常用符号1.2.3算法的描述算法的描述例例1.2判断某数判断某数m（大于等于（大于等于3的正整数）是否为素数的的正整数）是否为素数的算法。算法。素数是一个自然数，它除了素数是一个自然数，它除了1和本身之外，不能被任何其和本身之外，不能被任何其它整数整除的数。判断一个数它整数整除的数。判断一个数m是否为素数的方法很简单，是否为素数的方法很简单，如

15、果如果m不能为不能为2至至m-1的所有整数的所有整数i整除则为素数，如果被整除则为素数，如果被其中任何一个数整除则不是素数。判断其中任何一个数整除则不是素数。判断m为素数的流程图为素数的流程图如图如图1-4所示。所示。1.2.3算法的描述算法的描述开始2ir为零?输入mmi的余数r输出m为素数结束成立不成立i+1iim成立不成立输出m不是素数图图1-41.2.3算法的描述算法的描述（2）结构化流程图）结构化流程图 传统流程图用流程线指出各框操作的先后执行顺序，它对流程线没有严格的限制，如图1-4所示。如果问题复杂，流程随意转向，流程线可能会非常密集、交叉较多，从而使人们在阅读算法时需要花费许多

16、精力去追踪操作流程，使人们难以阅读、修改，算法的可靠性和可维护性难以保证。1966年，C.Bohm和G.Jacopini提出了顺序结构、选择结构、循环结构这3种基本结构，如图1-5所示，限制了箭头的使用，解决了传统流程图的弊端。现在各种程序设计语言都支持这三种结构，它们可以解决任何可计算的复杂问题。1.2.3算法的描述算法的描述S1S2S3PS1S2(a)顺序结构(b)分支结构NYPS1S1P(c)当型循环结构(d)直到型循环结构图1-5三种基本结构的流程图NYYN1.2.3算法的描述算法的描述 修改图1-4为结构化流程图需要增设一个条件p（prime的简写），初始时p为0，如果在循环中m能够

17、被代表2至m-1之间的数i整除，则设p为1，表示m不是素数；如图1-6所示。从图中可以看出程序结构是嵌套的结构，判断整除的余数是否为零的选择结构成为直到型循环结构的一个语句，在循环结构之后是一个判断结构，根据循环结构设置的条件p来判断是否为素数并进行输出。1.2.3算法的描述算法的描述开始2i0pr为零?输入mmi的余数r输 出 m为 素数结束成立不成立i+1iim且p不为1成立不成立1pp为1?不成立输出m不是素数成立图1-6 判断m是否为素数的结构化流程图1.2.3算法的描述算法的描述（3）N-S流程图流程图 为了简化控制流、适应“结构化”算法的要求，1973年美国学者I.Nassi和B.

18、shneiderman提出了一种无流线的流程图，称为N-S图（又称为盒图）。它的三种基本结构如下图1-7中的(a)、(b)、(c)、(d)所示。因为结构化流程图只有一个入口和一个出口，同时执行顺序只能从上到下一个方向，去掉流程线就是N-S图了。图1-8为判断素数的N-S流程图。N-S流程图的每一种基本结构都是一个矩形框。整个算法可以像堆积木一样堆成。N-S图只有一个入口和一个出口，也就是框的上边和下边。其最大特点是没有带箭头的流程线，并以基本结构作为图形的基本符号，所以用它描述的算法必定是结构化的。1.2 算法和算法描述算法和算法描述S1S2S3PTFS1S2当P条件成立循环体S循环体S直到P

19、条件成立(a)顺序结构(b)选择结构(c)当型循环结构(d)直到型循环结构图1-7三种基本结构的N-S图输入m0p2im整除i的余娄是否为0？FTi=i+1p=1直到im或p为1P是否为0？TF输出m是素数输出m不是素数图1-8判断m为素数的N-S流程图1.2.3算法的描述算法的描述4.用伪代码描述算法用伪代码描述算法 传统流程图和N-S图描述算法比较直观易懂、逻辑结构清晰，但画起来比较费时，修改起来困难。在设计一个算法时，往往要经过反复修改，使用这些图形工具就有些美中不足了。为了设计算法时方便，常用一种称为伪代码（pseudo code）的工具，它是用介于自然语言与计算机语言之间的文字和符号

20、来描述算法。例例1.3给定一个四位数的年份，判断它是否是闰年。地球绕太阳运行周期为 365天5小时48分46秒（合365.24219天）即一回归年（tropical year）。公历的平年只有365日，比回归年短约0.2422 日，所余下的时间约四年累计一天，故四年在2月加1天，使当年为366日，这一年就为闰年。按照每四年一个闰年计算，平均每年就要多算出0.0078天，这样经过四百年就会多算出大约3天来，因此，每四百年中要减少三个闰年。所以规定，公历年份是整百数的，必须是400的倍数才是闰年，不是400的倍数的，虽然是100的倍数，也是平年，这就是通常所说的：四年一闰，百年不闰，四百年再闰。例

21、如，2000年是闰年，1900年则是平年。1.2.3算法的描述算法的描述用伪代码表示的算法如下：begin （算法开始）输入年份yif y能被4整除 then if y不能被100整除 Then 输出“是闰年”else if y能被400整除 Then 输出“是闰年”else 输出“不是闰年”end if end ifelse 输出“不是闰年”end ifend （算法结束)1.3 结构化程序设计方法结构化程序设计方法 1.3.1结构化程序设计的产生和发展 n早期的计算机存储器容量非常小，人们设计程序时,首先考虑的问题是如何减少存储器开销，程序本身短小，逻辑简单，也无需人们考虑程序设计方法问题

22、n结构化程序设计n面向对象的程序设计1.3 结构化程序设计方法结构化程序设计方法 1.3.2程序设计的基本过程程序设计的基本过程 程序设计是一个创新的过程，因此设计一个程序，特别是一个软件系统，通常是一项非常复杂和困难的任务。程序设计的基本过程是从确定任务到得到结果、写出文档的全过程。n问题描述问题描述n算法设计算法设计n代码编制代码编制n调试运行调试运行n编写程序文档编写程序文档 1.3.2程序设计的基本过程程序设计的基本过程1.问题描述问题描述 程序设计的最终目的是为了利用计算机求解某一特定问题，因此程序设计面临的首要任务是得到问题的完整和确定的定义。如果不能确定程序的输出，最后就会对程序

23、的结果产生怀疑。还要确定程序的输入，而且要知道提供了特定的输入后，程序的输出是什么，以及输出的格式是什么，这些内容也是程序测试的基础。1.3.2程序设计的基本过程程序设计的基本过程2.算法设计算法设计 了解了问题的确定含义后，就要设计具体的解题思路。经过对实际问题进行分析，找出它内在的规律，建立数学模型，设计出准确的解题方法和具体过程，一般用流程图来表示解题的步骤。1.3.2程序设计的基本过程程序设计的基本过程3.代码编制代码编制不同的语言有各自的特点，因此首先要针对问题选用合适的开发设计环境和平台。尽管写出的程序有时会有较大差别，但它必须是忠实于算法描述的。正因为如此，有人说代码编制的过程是

24、算法到计算机语言程序的翻译过程。程序设计时，人们将在纸上编写好的程序代码通过编辑器输入到计算机内，利用编辑器可对输入的程序代码进行复制、删除、移动等编辑操作，然后以文件(源程序)形式保存。现在的程序设计语言一般都有一个集成开发环境，自带编辑器，用户可以方便地编辑程序；当然也可以用Windows环境下的记事本来编辑程序。源程序必须是纯文本文件，不能用带有格式的字处理软件来建立，如word软件。1.3.2程序设计的基本过程程序设计的基本过程4.调试运行调试运行计算机是不能直接执行源程序（机器语言程序除外）的，因此，计算机上提供的各种语言，必须配备相应语言的“编译程序”或“解释程序”。通过“编译程序

25、”或“解释程序”使人们编写的程序能够最终得到执行的工作方式，称为程序的编译方式和解释方式。编译是指将使用高级语言编写的程序(又称源程序、源代码)，经编译程序翻译，形成可由计算机执行的机器指令程序(称为目标程序)的过程。如果使用编译型语言，必须把程序编译成可执行代码。因此编制程序需要三步：写源程序、编译和运行。一旦发现程序有错，哪怕只是一个错误，也必须修改源程序后再重新编译，然后才能运行。幸运的是，只要编译成功一次，其目标代码便可以反复运行，并且基本上不需要编译程序的支持就可以运行。1.3.2程序设计的基本过程程序设计的基本过程5.编写程序文档编写程序文档对于小程序来说，有没有文档显得不重要，但

26、对于一个需要多人合作，并且开发、维护较长时间的软件来说，文档至关重要。文档记录程序设计的算法、实现以及修改的过程，保证程序的可读性和可维护性。一个有50000行代码的程序，在没有文档的情况下，即使是编程者本人在6个月后也很难记清其中某些程序是完成什么功能的。这些文档都是程序开发时的文档，另外一种是程序说明书，因为许多程序是提供给别人使用的，必须向用户提供一个说明书之类的用户文档，包括程序名称、程序功能、运行环境、程序的装入和启动、需要输入的数据，以及使用注意事项，程序文档是软件的一个重要组成部分，软件是计算机程序和程序文档的总称。1.3结构化程序设计方法结构化程序设计方法1.3.3结构化程序设

27、计结构化程序设计结构化程序就是由顺序结构、分支结构和循环结构组成的程序，这种程序的结构清晰，便于编写、阅读、修改和维护，减少了程序出错的机会，提高了程序的可靠性，保证了程序的质量。结构化程序设计是一种基于结构化程序设计方法的程序设计技术，它采用自顶向下逐步求精的设计方法和单入口单出口的控制结构。结构化程序设计方法是指导解决一个复杂问题进行程序设计各个阶段所遵循的规范和原则。1.3.3结构化程序设计结构化程序设计在结构化程序设计中，一般采用自顶向下、逐步细化的分解原则。首先将系统分解为若干子系统；然后，将子系统继续分解，直到每个子系统都足够基础，不需要再分为止；也可以将系统划分为若干模块，每个模

28、块又划分为若干较小模块，每个较小模块继续分解直到问题变得非常简单为止。这样就可以将一个复杂的大系统划分为若干具有特定功能的子系统，从而使系统的复杂性下降，同时，又使待解决的问题具体化。“自顶向下、逐步细化”的程序设计方法使程序设计整个体系结构清晰、层次分明，与日常生活中常用的方法（如撰写论文）相似。1.3.3结构化程序设计结构化程序设计1.结构化程序设计优点结构化程序设计优点由于模块相互独立，因此在设计其中一个模块时，不会受到其它模块的牵连，因而可将原来较为复杂的问题化简为一系列简单模块的设计。模块的独立性还有利于扩充已有的系统、建立新系统。结构化程序设计优点是：（1）整体思路清楚，目标明确；

29、（2）设计工作中阶段性非常强，有利于系统开发的总体管理和控制；（3）在系统分析时可以诊断出原系统中存在的问题和结构上的缺陷。1.3.3结构化程序设计结构化程序设计2.结构化程序设计的缺点结构化程序设计的缺点结构化程序设计有许多优点，但也存在一些缺点：（1）用户要求难以在系统分析阶段准确定义，致使系统在交付使用时产生许多问题；（2）用系统开发每个阶段的成果来进行控制，不能适应事物变化的要求；（3）系统的开发周期长。1.3 结构化程序设计方法结构化程序设计方法1.3.4程序调试程序调试程序调试，是将编制的程序投入实际运行前，用手工或编译程序等方法进行测试，修正语法错误和逻辑错误的过程。这是保证软件

30、正确性的必不可少的步骤。编写完成计算机程序之后，必须送入计算机进行测试。程序的调试分为四步：n用编辑程序把编制的源程序按照一定的书写格式输入计算机中。n把输入的源程序翻译成机器语言，即用编译程序对源程序进行语法检查并将符合语法规则的源程序语句翻译成计算机能识别的机器语言。如果经编译程序检查，发现有语法错误，必须用编辑程序来修改源程序中的语法错误，然后再编译，直至没有语法错误为止。1.3.4程序调试程序调试n使用计算机中的连接程序，把翻译好的计算机语言程序连接成一个计算机能真正运行的程序。在连接过程中，如果出现了连接错误，说明源程序中存在函数的调用混乱或参数传递错误等问题。这时又要用编辑程序对源

31、程序进行修改，再进行编译和连接，如此反复进行，直至没有连接错误为止。1.3.4程序调试程序调试n将修改后的程序进行试运行，这时可以假设几个模拟数据去试运行，并把输出结果与手工处理的正确结果相比较。如有差异，就表明计算机的程序存在有逻辑错误。如果程序不大，可以用人工方法去模拟计算机对源程序的这几个数据进行修改处理；如果程序比较大，人工模拟显然行不通，这时只能将计算机设置成单步执行的方式，一步步跟踪程序的运行。一旦找到问题所在，仍然要用编辑程序来修改源程序，接着仍要编译、连接和执行，直至无逻辑错误为止。如果程序复杂、测试数据量大，则采用自动测试的方式实现。作业作业1.什么是程序？什么是程序设计？4.试述三种基本结构的特点。5.用传统流程图表示求解下面问题的算法。