算法的概念课件

算法的概念算法是指解决给定问题的有穷操作步骤的描述。算法是计算机科学中的重要概念之一，它指明了问题的求解过程，是对给定问题解题方案的准确而完整地描述。2020年10月2日1【例4.1】给定任意两个整数，按从小到大顺序排列。解决这一问题的算法可描述如下：输入两个整数A和B；比较A和B的大小，若AB，则分别输出A和B，且计算到此结束，否则(AB)，分别输出B和A，且计算到此结束。2020年10月2日2 算法的基本特征 有穷性。一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。确定性。算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。可行性。算法中的每一个步骤都是可以在有限的时间内完成的基本操作，并能得到确定的结果。2020年10月2日3数据输入。每个算法都要求有原始数据输入，即给定计算初值。算法不同，输入的原始数据可能不同，但缺少原始数据的算法则是一个不完善的算法。信息输出。一个算法至少要有一个有效的信息输出，这就是问题求解的结果。2020年10月2日4衡量一个算法好坏的标准是：算法应当正确，易于阅读和理解，实现算法所占存储空间要少，运算时间短，实现方法简单可行等。2020年10月2日5 算法的表示方法 用文字叙述形式表示 可以用中文或英文叙述的形式来描述算法采用文字叙述形式表示算法通俗易懂，但文字冗长，而且容易产生“歧义”（即对同一段文字，不同的人可能会有不同的理解）。因此，除了一些非常简单的问题外，一般不采用文字叙述形式来表示算法。2020年10月2日6 用流程图表示 流程图一般可分为传统流程图和结构化流程图（图)。所谓传统的流程图是指用几何框、箭头、连线以及文字说明相结合的一种图形。用流程图表示算法不仅直观、灵活，而且易于理解。2020年10月2日7起始或终止框起始或终止框计算处理框（过程）计算处理框（过程）条件判断框（决策）条件判断框（决策）输入输出框（数据）输入输出框（数据）流向或路径流向或路径连接点连接点2020年10月2日8开开 始始输入两个整数输入两个整数A和和BAB输出输出A和和B值值输出输出B和和A值值成立不成立2020年10月2日9结结 束束2020年10月2日103.用伪代码表示 所谓伪代码表示是指用介于自然语言和计算机语言之间的一种代码来描述算法。用伪代码表示例4.1 的算法。INPUT A,B IF AB PRINT A,B ELSE PRINT B,A ENDIF2020年10月2日11利用计算机处理问题的过程 用计算机所能接受的形式把解题的算法用程序设计语言描述出来的工作叫程序设计，它包括了大量的工作和许多具体的步骤。其中这些步骤包括以下内容：分析问题。即明确实际问题的要求，给定的数据有哪些，需要输出什么样的数据，需要进行哪种处理。确定求解方案。2020年10月2日12算法分析。根据处理方案，具体列出让计算机如何进行操作的步骤（算法），并进行算法的准确性和有效性分析，找出合理的算法。编写程序。拟定算法的步骤和说明后，使用某种程序设计语言，以书面形式将算法描述出来，所得到的编程结果就是源程序。上机调试运行程序。将编写好的源程序输入计算机并调试、运行，如果程序是正确的，应能得到预期的结果，如果得2020年10月2日13 不到正确结果，应该检查前几步是否有误，改正后再上机运行。编写文档。编写文档是程序设计的必要组成部分。从问题的提出开始一直到程序运行结束，都应该全面、完整地编写文档资料，内容包括技术文档资料和使用文档资料，这是后期使用和维护程序所必需的资料。维护。程序所处理的各种数据是非常宝贵的信息资源，其宝贵价值就在于信息的真实性、准确性和有效性。要保证信息的真实性和准确性，就需要及时地进行增、删和更新等维护工作。2020年10月2日144.3 结构化程序设计概述4.3.1 结构化程序的三种基本结构 结构化程序规定了三种基本的结构，即顺序结构、分支结构和循环结构。顺序结构 顺序结构是一种最简单、最基本的结构，其特点是各部分按照出现的先后顺序执行。它由A和B两个语句块组成，且仅有一个入口（）和一个出口（）。最简单的情况是每一语句块中只含有一条不产生控制转移的执行语句。2020年10月2日15 每个语句块本身也可以是一个顺序结构，因此一个顺序结构可以由许多顺序执行的语句组成。ABab2020年10月2日16 分支结构 它根据给定的条件在两条可供选择的分支中选择其中的一条执行。当条件成立时，执行语句块A，否则执行语句块B。执行完语句块A或语句块B后，都从点出口。因此就整个分支结构来讲，它仍然只有一个入口（）和一个出口（）。2020年10月2日17条条 件件ABab成立成立不成立不成立2020年10月2日18 循环结构 循环结构也叫重复结构，即重复执行某些操作。根据其执行情况和循环结束条件的不同可分为当型循环（也称WHILE型结构）和直到型循环（也称UNTIL型结构）。当型循环结构，它是当满足某个指定的条件时，反复执行语句块A，否则不执行。直到型循环结构，它是反复执行语句块A，直到条件满足为止。它们也只有一个入口（）和一个出口（）。2020年10月2日19条条 件件A条条 件件Aab成立成立不成立不成立成立成立b不成立不成立a当当 型型直到型直到型2020年10月2日20两种循环结构的区别：执行情况不一样。当型结构是先判断循环条件，当条件成立时，才执行语句块A，若循环条件一开始就不成立，则语句块A一次也不执行。而直到型结构是先执行语句块A，后判断循环条件，且语句块A至少要执行一次。循环结束条件不一样。当型结构是条件不成立时结束循环，而直到型结构是条件成立时结束循环。2020年10月2日21 由三种基本结构（可以是其中的一种、二种或三种）构成的程序，称为结构化程序。一个结构化程序以及三种基本结构中的每一种都应当具有以下特点：程序执行的路径只有一个入口和一个出口，在入口和出口之间是一种基本方盒或逻辑结构。该结构中的任一个部分都存在着从入口到出口的路径，换句话说，结构中每一部分都可以被执行，不存在执行不到的死块（程序段）。没有死循环（永无休止的循环）。2020年10月2日224.3.2 结构化流程图 在结构化程序设计中，经常采用结构化流程图来表示算法。结构化流程图是在去掉传统流程图中的流程线的基础上形成的，由美国计算机科学家I.Nasi和B.Schneiderman 1973 年提出，因此又称为图。看图就好比是看一页书，从上到下看下来就全明白了。2020年10月2日23 三种基本结构的图符号 顺序结构 顺序结构用矩形框表示，有时为了简便，也可以将一个顺序结构写在一个矩形框内。AB2020年10月2日24 分支结构 分支结构用带三角形的框来表示，若三角形中的条件成立，则执行语句块A，否则执行语句块B。条条 件件成立成立不成立不成立AB2020年10月2日25 循环结构 循环结构用一个包含形的矩形表示，分当型循环结构和直到型循环。循环条件放在形框（或倒立形框）中，重复执行部分放在矩形框中。当条件成立时执行当条件成立时执行AA直到条件成立直到条件成立2020年10月2日26 所谓结构化程序设计方法是指采用顺序、分支和循环三种基本结构来实现算法。按照结构化程序设计方法设计出的程序结构良好，具有易读、易维护等优点。自顶向下、逐步求精和模块化是结构化程序设计方法中最典型、最具有代表性的方法。自顶向下的设计方法 自顶向下设计方法是一种从顶层开始，向下逐层分解、逐步细化，直到最底一层达到最简单的功能模块为止的方法。这种方法能够使编程者思路清楚、2020年10月2日27 有条不紊地一步一步深入地工作，用较短的时间设计出结构良好、可读性强、可靠性较高的程序，并容易验证程序的正确性，便于维护。逐步求精设计方法 逐步求精设计方法是将一个抽象的问题分解成若干个相对独立的小问题，并逐级进行由抽象到具体，由粗到细，由表及里不断进行精细化的程序设计方法。每一步求精过程都将问题的算法进一步细化，直到算法精细化到可以用三种基本结构实现为止。2020年10月2日28 模块化设计方法 模块化设计方法是指将一个复杂的问题，分解成许多功能单一、相对独立的模块，各模块之间按照层次结构联系起来构成模块结构图。在模块结构图中，每个模块用一个矩形框表示，框内写上每个模块的名称，模块之间的调用关系用带箭头的方向线表示。模块化设计方法的核心是如何划分模块，产生模块结构图。2020年10月2日29 上述三种结构化程序设计方法各有其特点。逐步求精设计方法主要指一个程序的设计过程，它符合人们逻辑推理和思维的习惯。模块化设计方法和自顶向下设计方法主要指一个比较大的系统的设计过程，采取的是化整为零，各个击破的方法。将问题分割成若干个子问题，对子问题再进行分割，这样可将问题分割成一个模块层次结构。2020年10月2日30 4.4 Foxpro程序的建立、运行和调试4.4.1 Foxpro程序的一般结构*PROG4_6.PRG的功能是已知三角形三边,求 三角形面积 SET TALK OFF&执行结果不在屏幕上显示 A=3 B=4 C=5 P=(A+B+C)/2 S=SQRT(P*(P-A)*(P-B)*(P-C)?三角形面积为:,S SET TALK ON2020年10月2日31 PARAMETERS A,B,C&形式参数 SET TALK OFF P=(A+B+C)/2 S=SQRT(P*(P-A)*(P-B)*(P-C)?三角形面积为:,S SET TALK ON *带参数程序2020年10月2日32*PROG4_8.PRG PARAMETERS A,B,C SET TALK OFF IF A+B=C OR A+C=B OR B+C=A *判断能否构成三角形 DO DISPERR&调用过程 DISPERR ELSE?三角形面积为:,SOLVEAREA(A,B,C)*调用函数SOLVEAREA计算三角形面积 ENDIF 2020年10月2日33SET TALK ON RETURN PROCEDURE DISPERR&显示错误信息 WAIT不能构成三角形!WINDOW；NOWAIT RETURN FUNCTION SOLVEAREA*计算三角形面积自定义函数 PARAMETERS X,Y,Z P=(X+Y+Z)/2 2020年10月2日34 AREA=SQRT(P*(P-X)*(P-Y)*(P-Z)RETURN AREA2020年10月2日35通过以上几个程序例子可以看到：一个Foxpro程序是由一个主程序或者一个主程序和若干个过程或自定义函数构成 主程序、过程或用户自定义函数通常包括三个基本部分，即参数说明部分、执行部分和结束部分。参数说明部分 Foxpro规定其程序可以有两种，即不带参数程序和带参数程序，两者的主要区别在于有无参数说明部分。2020年10月2日36对于不带参数的程序，其第一条可执行的命令应为程序的执行部分。对于带参数程序，其第一条可执行的命令必须是参数说明命令PARAMETERS。参数说明命令的格式如下：PARAMETERS 该命令说明程序、过程或用户自定义函数中所使用的全部形式参数，以便接收程序、过程或用户自定义函数传来的数据，它必须是“被调用程序”中的第一条可执行命令。2020年10月2日37中的参数可以是任何内存变量名或数组名，当使用多个形参时，参数之间以逗号“，”分隔。在Foxpro中，一次最多能传送24个参数。执行部分 一个程序、过程或用户自定义函数的执行部分是由若干条有序的可执行命令组成的，它完成该程序、过程或自定义函数的所有功能。通常把过程的执行部分称为过程体，用户自定义函数的执行部分称为函数体。2020年10月2日38结束部分 在Foxpro中，一个程序、过程或用户自定义函数可以有结束部分，也可以没有结束部分。如果有结束部分，一般都是通过执行一条“结束程序执行的命令”来结束该程序、过程或用户自定义函数的执行。Foxpro提供了以下四条结束程序执行的命令：返回命令RETURN 【格式】RETURN TO MASTERTO 2020年10月2日39【功能】该命令终止程序、过程或用户自定义函数的执行。若RETURN后不带任何选项，则返回到调用程序中调用处的下一条命令继续执行，当在命令窗口下执行程序时将返回到命令窗口。如果RETURN后带TO MASTER，则返回到最高层调用程序。如果RETURN后加入TO，则返回到由所指定的程序。在用户自定义函数的最后通常用RETURN 命令将一个的值返回给调用程序。2020年10月2日40重试命令RETRY 【格式】RETRY 【功能】返回调用程序，并再次执行调用程序中上一次被执行的那一行。该命令常用在错误处理程序中。结束命令CANCEL 【格式】CANCEL 【功能】中止程序的执行，直接返回到Foxpro命令窗口。退出命令QUIT 【格式】QUIT2020年10月2日41【功能】结束程序的执行，关闭所有已打开的文件，退出Foxpro环境，返回到操作系统。以上四条结束命令可以放在一个程序、过程或用户自定义函数中的任何地方，并且允许出现多次。Foxpro规定，如果在一个程序、过程或用户自定义函数中没有结束部分，则默认为RETURN，在这种情况下，当执行完最后一条命令后，将返回到调用处的下一条命令继续执行。2020年10月2日42综上所述，给出Foxpro程序的一般结构如下：PARAMETERS 结束部分 PROCEDURE PARAMETERS 结束部分 .2020年10月2日43 FUNCTION PARAMETERS RETURN .2020年10月2日444.4.2 Foxpro程序的建立与修改 程序文件的建立 MODIFY COMMAND?MODIFY FILE?modi comm 主要用来编辑程序文件，modi file 主要用来编辑文本文件。2020年10月2日454.4.3 Foxpro程序的运行与调试 程序的运行 在Foxpro环境下，运行一个程序有两种方法：一种是在Foxpro系统菜单下执行 Program菜单中的Do选项，另外一种方法是在命令窗口中执行Do命令。Foxpro的Do命令的格式如下：DO WITHIN 该命令用来执行一个Foxpro程序文件。如果没有指定程序文件的扩展名，则按可执行文件（.EXE）应用程序（.APP2020年10月2日46）编译后的文件（.FXP）源程序（.PRG）顺序来执行。对于带参数程序，必须带WITH，此时WITH后的实际参数表将被传送给该程序文件 使用。带IN选项表示要执行指定程序中的一个过程。通常我们把在Foxpro命令窗口中执行DO命令称为“运行程序”，而在一个程序中执行该命令称为“调用程序”。Foxpro中的每个程序都可以被调用，所以在任何程序中都可以通过DO命令来调用其它程序。2020年10月2日47 程序的调试 初次建立的程序由于种种原因可能会出现各种各样的错误，需要通过试运行来检查和修改程序中的错误，这就是常说的“程序的调试”。调试程序的常用方法是用一些典型数据来试验运行程序，通过分析运行结果来判断程序是否正确。若运行结果不正确，需要找出错误的地方并加以修改。也可以使用Foxpro提供的调试工具来帮助我们跟踪在程序调试中出现的错误。例如，如果使用SET STEP ON命令可以设置单步执行方式，Foxpro 在执行每条命令后暂停，并在2020年10月2日48 Trace窗口显示该程序，以便查看程序的执行情况。如果使用SET ALTERNATE TO 命令和SET ALTERNATE ON命令，可将程序运行过程中输出到屏幕上的数据存入指定的磁盘文件（可以利用CLOSE ALTERNATE命令关闭建立的文件），以便分析结果时使用。2020年10月2日49 一般来说，程序中的错误可分为语法错误和逻辑错误两种类型。语法错误 所谓“语法错误”是指程序中某条（些）命令不符合Foxpro的语法规则而引起的错误。例如，命令动词拼写错误，引用的变量不存在，数据类型不匹配等。有时标点符号使用错误也会导致语法错误。一旦出现语法错误，Foxpro将中止程序的运行，并在屏幕上显示出错的命令及错误命令所在的程序名称，可根据出错信息去查改程序中的错误。2020年10月2日50 除了通过运行程序来检查语法错误外，也可以使用Foxpro提供的编译命令Compile 来编译指定的源程序（.PRG），以便查出其中的全部语法错误，并将错误信息存入同名的扩展名为.ERR的文件中。利用Foxpro的编辑器可以查看这个错误记录文件，并根据提供的信息来修改源程序中的错误。如果源程序中没有语法错误，则产生一个同名的扩展名为.FXP的目标文件（.FXP为Foxpro的伪编译文件）。在Foxpro命令窗口下运行源程序时，实际上执行的都是编译后的.FXP文件。2020年10月2日51 在Foxpro中编译一个源程序时，既可以选择系统菜单中Program 菜单项中的Compile选项来完成，也可以在命令窗口中直接使用Compile命令来完成。在编译源程序时，可以通过SET LOGERRORS ONOFF命令来控制是否生成错误记录文件。取ON时，则生成错误记录文件。取OFF时，则不生成错误记录文件。2020年10月2日52 逻辑错误 所谓“逻辑错误”是指程序中每条命令的书写都符合Foxpro的语法规则，程序也能够运行，但所得结果却是错误的。逻辑错误比较难查，一般采用分段排除的方法来查找。若查得程序本身无错，就得检查算法是否有误，对问题的理解是否有误等等。2020年10月2日53演讲完毕，谢谢观看！Thank you for reading!In order to facilitate learning and use,the content of this document can be modified,adjusted and printed at will after downloading.Welcome to download!汇报人：XXX汇报日期：20XX年10月10日54