程序设计初步讲义

程序设计初步3.1算法初步及其描述方法3.1.1算法初步1.什么是算法算法是为解决一个特定问题而采取的特定的有限的步骤。广义地说，做任何事情都有算法，例如一张太极拳打法图解也可以看作是一个“太极拳算法”。因此，算法概念不限于算术问题，而是具有更广泛的含义。从计算机应用的角度来说，算法是指完成一个任务所需要的具体步骤和方法（解决问题的方案）。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。【算法3.1】给定两个正整数p和q，求其最大公因数。古希腊数学家欧几里德给出的算法：步骤1：如果pq，交换p和q。步骤2：求p/q的余数r。步骤3：如果r=0，则q就是所求的结果。否则反复做如下工作：令p=q，q=r，重新计算p和q的余数r，直到r=0为止，则q就是原来的两正整数的最大公因数。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。从原则上说，有了算法，人们就可以借助纸、笔和算盘等工具直接求解问题了。但如果问题比较复杂，计算步骤很多，则应通过编写计算机程序，使用计算机解决。2.算法的特征算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征：(1)有穷性：一个算法必须保证执行有限步之后结束。(2)确切性：算法的每一步骤必须有确切的定义。(3)输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。(4)输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。(5)可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。3.算法的类型和结构(1)算法的类型算法可分为两大类：数值算法和非数值算法。数值算法是为数学问题形成一个构造性解法的完备而确切的描述，并规定方法中仅允许使用加、减、乘、除等基本的算术运算。非数值算法广泛应用在“数据处理”的场合。需要对大量的信息（数据）进行加工处理，包括转换、分类、查找、排序和存储等。常用的算法有穷举、递推、顺序查找和冒泡排序等。(2)算法的结构一个算法是由“结构”和“原操作”构成的。原操作包括：输入、输出、赋值和比较等。算法的三种基本结构是：顺序结构、分支结构和循环结构。用这三种基本结构可以表示任意一个复杂的算法。①顺序结构顺序结构是指通过安排操作的排列顺序来决定算法流程的结构。在这种结构中，各个操作是依次执行的。顺序结构是由若干个依次执行的处理块组成，这是任何一个算法都离不开的基本主体结构。②分支结构在绝大多数情况下，算法不会按部就班地从第一条操作执行到最后一条操作，往往由特定的条件决定执行哪个操作，这就是分支结构。分支结构是以条件或情况的判断为起始点，它是人脑判断思维活动的抽象。最基本的分支结构是二分支结构，根据判断逻辑是否成立而决定选择哪一边的处理块去执行。③循环结构循环结构是指在算法设计中，从某处开始有规律地反复执行某一处理块，这个处理块称为循环体。循环体的执行次数由一个控制循环条件决定。满足条件反复做，不满足则停止。3.1.2算法的描述工具设计一个算法可以根据问题的不同需要用某种语言符号来描述。目前最常用的几种算法描述工具有：自然语言、流程图、N-S图、伪代码等。1.自然语言自然语言就是人们日常使用的语言，可以是中文、英文等。用自然语言表示的算法通俗易懂，但一般篇幅较冗长，表达上不易准确，易引起理解上的“歧义性”（即对同一段文字，不同的人会有不同的理解）。【算法3.2】输入3个数，求其最大数。分析：该算法可以使用分支结构表示。设num1，num2，num3存放3个数，max存放其最大值。为求其最大数，只要对3个数进行比较，可按如下步骤去做：S1：输入3个数num1，num2，num3；S2：先把第1个数num1的值赋给max；S3：将num2与max比较，如果num2max，则把num2的值赋给max，否则，不做任何事情。S4：将num3与max比较，如果num3max，则把num3的值赋给max，否则，不做任何事情。S5：输出max的值，即最大值。【算法3.3】求1+2+3+…+100。分析：该算法可以使用循环结构表示。设n存放1到100之间的整数，sum存放1到100的和，即sum=1+2+3+…+100，可按如下步骤去做：S1：进行初始化，1=n，0=sum；S2：sum+n=sum；S3：n+1=n；S4：进行判断，n是否小于等于100，如果条件为真，则返回S2，否则执行S5；S5：输出sum的值。2.流程图流程图是用一组规定的图形符号、流程线和文字说明来表示算法，它直观形象，易于理解。流程图的特点是用“流线”给算法执行中的每一个步骤指定了逻辑上的顺序，因此能把程序执行的控制流表达得十分清楚。但如果使用不当会使程序的流程出现缠绕，不利于结构化程序设计的实施。流程图符号见图3-1。【算法3.4】用流程图描述算法3.2（如图3-2）。【算法3.5】用流程图描述算法3.3（如图3-3）。3.N-S图N-S图也是描述算法的常用工具。与流程图相比，N-S图完全去掉了流程图中的流线和箭头，因此能用N-S图表示的算法，必是结构化的算法。【算法3.6】用N-S图描述算法3.2（如图3-5）。【算法3.7】用N-S图描述算法3.3（如图3-6）。4.伪代码伪代码是一种算法描述语言，使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。【算法3.8】用伪代码描述算法3.2。INPUTnum1,num2,num3num1=maxIFnum2maxTHENnum2=maxIFnum3maxTHENnum3=maxPRINTmax【算法3.9】用伪代码描述算法3.3。1=n,0=sumwhile(n=100){sum+n=sum；n+1=n；}printsum3.1.3算法和程序设计前面介绍了如何描述算法，但计算机是无法识别流程图和伪代码的，只有用计算机语言编写的程序，经编译成目标程序后，才能被计算机执行。因此，用任何方法描述的算法，还得要将它转化成计算机语言程序。程序设计是人关于现实问题求解的思维活动的“代码化”过程，是用计算机语言作为工具进行的创造性劳动。编程序的一个主要内容就是如何将解决应用问题所使用的算法用程序设计语言来描述。1.程序设计的一般步骤(1)分析问题根据用户的具体要求，进行需求分析、数据及处理分析、可行性分析、运行环境分析。然后在分析的基础上，将实际问题抽象化，建立相应的数学模型并确定解决方案。读者在初学程序设计的时候，教科书中的例题都比较简单，从这些简单的例题中读者很难体会到分析问题的作用。而且题目本身往往已经对需要解决的问题做了清楚准确的描述。但尽管如此，我们也不应直接开始编程，而应该首先进行问题分析。(2)确定算法根据选取的数学模型和确定的方案，设计出具体的操作步骤，并可以通过流程图等描述算法的工具将确定的算法清晰、直观的表示出来。(3)编写程序选用合适的开发平台和程序设计语言，将算法按所选语言的规则描述出来，即形成程序设计语言编制的源程序。(4)调试运行程序对编写好的程序进行试运行和检验，发现问题立即对程序进行修改，然后再试运行和检验，直至得出正确的结果。(5)建立文档资料整理分析计算结果，并建立相应的文档资料（程序技术说明书、用户使用说明书等），以便维护和修改。2.结构化程序设计方法结构化的程序设计方法的要点如下：(1)程序的质量标准是“清晰第一，效率第二”。(2)程序的设计采用“自顶向下，逐步求精，模块化设计，结构化编程”的方法。(3)程序的结构仅由顺序、分支、循环三种基本结构的组合、嵌套而成，且满足：·每个程序模块只有一个入口和一个出口；·没有死语句（永远执行不到的语句）；·没有死循环（永远不能终止的循环）；(4)程序的书写必须按一定的规范和格式进行（参见附录部分）。(5)程序的设计风格要以好的可读性为标准，力求外观美观、结构流畅、语句简洁。3.2基本计算3.2.1数据类型在C++中，数据具有不同的类型，类型定义了变量可存储的数值范围以及可进行的操作。变量是用于内存中保存数据的，每个变量都必须有确定的数据类型，C++语言的数据类型如图3-7所示。说明：①基本数据类型前可以添加修饰符，以改变基本类型的意义，可用的修饰符有long、short、signed和unsigned四种，其中，unsigned和signed只用于修饰char和int，且signed修饰词可以省略。当用unsigned修饰词时，后面的类型说明符可以省略。另外，双精度型前可以加long修饰符。基本的数据类型及其表示范围，可参见表3-1。②当多种类型的数据进行混合运算时，往往需要进行类型转换，将它们转换为相同的类型，即较低类型转换为较高类型，然后再参加运算，转换规则如图3-8。注：其中，type表示一种非void的数据类型。图3-7C++数据类型表3-1基本的数据类型及其表示范围类型名类型字节表示范围char字符型1-128~127unsignedchar无符号字符型10~255int整型4-2,147,483,648~2,147,483,647数据类型基本类型非基本类型指针类型整型字符型（char）浮点型布尔型（bool）空类型（void）枚举类型（enum）数组类型type[]结构体类型（struct）共用体类型（union）类类型（class）type*短整型（int）整型（int）长整型（longint）单精度型（float）双精度型（double）长双精度型（longdouble）unsignedint无符号整型40~4,294,967,295short短整型2-32,768~32,767unsignedshort无符号短整型20~65,535long长整型4-2,147,483,648~2,147,483,647unsignedlong无符号长整型40~4,294,967,295float浮点型43.4E+/-38(7位有效数字)double双精度型81.7E+/-308(15位有效数字)longdouble长双精度型101.2E+/-4932(19位有效数字)图中横向的箭头表示必须的转换，如两个float型数参加运算，虽然它们类型相同，但仍要先转换成double型再进行运算，结果亦为double型。纵向箭头表示当运算符两边的操作数为不同类型时的转换，如一个long型数据与一个int型数据一起运算，需要先将int型数据转换为long型，然后两者再进行运算，结果为long型。所有这些转换都是由系统自动进行的，因此也称为隐式转换。#includeiostreamusingnamespacestd;intmain(void){chara='x';intb=3;intf=2;floatc=2.5678;doubled=5.2345;longe=32L;couta-b+d/c-e*fendl;return0;}¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯下面我们来分析一下这段程序：（1）进行d/c运算时，要将c转换成double型，运算的中间结果为double型；（2）进行e*f运算时，将f转换为long型，运算的中间结果为long型；（3）进行a-b运算时，将a转换为int型，运算的中间结果为int型；（4）当（3）的中间结果与（1）的中间结果运算时，将（3）的中