算法和流程图（及N-S流程图）
算法和流程图
2.1.1算法
计算机语⾔只是⼀种⼯具。光学习语⾔的规则还不够，最重要的是学会针对各种类型的问题，拟定出有效的解决⽅法和步骤即算法。有了正确⽽有效的算法，可以利⽤任何⼀种计算机⾼级语⾔编写程序，使计算机进⾏⼯作。因此，设计算法是程序设计的核⼼。
并⾮只有“计算”的问题才有算法。⼴义地说，为解决⼀个问题⽽采取的⽅法和步骤，称为“算法”。不要把“计算⽅法”（computational method）和“算法”（algorithm）这两个词混淆。前者指的是求数值解的近似⽅法，后者是指解决问题的⼀步⼀步的过程。在解⼀个数值计算问题时，除了要选择合适的计算⽅法外，还要根据这个计算⽅法写出如何让计算机⼀步⼀步执⾏以求解的算法。对于计算机外⾏来说，他们可以只使⽤别⼈已设计好的现成算法，只需根据算法的要求给以必要的输⼊，就能得到输出的结果。对他们来说，算法如同⼀个“⿊箱⼦”⼀样，他们可以不了解“⿊箱⼦”中的结构，只是从外部特性上了解算法的作⽤，即可⽅便地使⽤算法。但对于程序设计⼈员来说，必须会设计算法，并且根据算法编写程序。
对同⼀个问题，可以有不同的解题⽅法和步骤。例如，求1+2+3+…+100，可以先进⾏1+2，再加3，再加
4，⼀直加到100，也可采取100+ (1+99)+(2+98)+…+(49+51)+50＝100+50+49×100＝5050。还可以有其它的⽅法。当然，⽅法有优劣之分。有的⽅法只需进⾏很少的步骤，⽽有些⽅法则需要较多的步骤。⼀般说，希望采⽤⽅法简单，运算步骤少的⽅法。因此，为了有效地进⾏解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。
⼀个计算问题的解决过程通常包含下⾯⼏步:
确⽴所需解决的问题以及最后应达到的要求。必须保证在任务⼀开始就对它有详细⽽确切的了解，避免模棱两可和含混不清之处。
分析问题构造模型。在得到⼀个基本的物理模型后，⽤数学语⾔描述它，例如列出解题的数学公式或联⽴⽅程式，即建⽴数学模型。
选择计算⽅法。如定积分求值问题，可以⽤矩形法、梯形法或⾟普⽣法等不同的⽅法。因此⽤计算机解题应当先确定⽤哪⼀种⽅法来计算。专门有⼀门学科“计算⽅法”，就是研究⽤什么⽅法最有效、最近似地实现各种数值计算的，换句话说，计算⽅法是研究数值计算的近似⽅法的。
确定算法和画流程图。在编写程序之前，应当整理好思路，设想好⼀步⼀步怎样运算或处理，即为“算法”。把它⽤框图画出来，⽤⼀个框表⽰要完成的⼀个或⼏个步骤，它表⽰⼯作的流程，称为流程图。它能使⼈们思路清楚，减少编写程序中的错误。
编写程序。
程序调试，即试算。⼀个复杂的程序往往不是⼀次上机就能通过并得到正确的结果的，需要反复试算修改，才得到正确的可供正式运⾏的程序。
正式运⾏得到必要的运算结果。
2.1.2流程图
为了表⽰⼀个算法，可以⽤不同的⽅法。常⽤的有：⾃然语⾔；传统流程图；结构化流程图；伪代码；PAD图等。这⾥我们主要介绍流程图。
a)    传统流程图
⽤图表⽰的算法就是流程图。流程图是⽤⼀些图框来表⽰各种类型的操作，在框内写出各个步骤，然后⽤带箭头的线把它们连接起来，以表⽰执⾏的先后顺序。⽤图形表⽰算法，直观形象，易于理解。
美国国家标准化协会ANSI曾规定了⼀些常⽤的流程图符号，为世界各国程序⼯作者普遍采⽤。最常⽤的流程图符号见图。
处理框（矩形框），表⽰⼀般的处理功能。
判断框（菱形框），表⽰对⼀个给定的条件进⾏判断，根据给定的条件是否成⽴决定如何执⾏其后的操作。它有⼀个⼊⼝，⼆个出⼝。
输⼊输出框（平⾏四边形框）。
起⽌框（圆弧形框），表⽰流程开始或结束。
连接点（圆圈），⽤于将画在不同地⽅的流程线连接起来。如图中有两个以1标志的连接点(在连接点圈中写上“l”)则表⽰这两个点是连接在⼀起的，相当于⼀个点⼀样。⽤连接点，可以避免流程线的交叉或过长，使流程图清晰。
流程线（指向线），表⽰流程的路径和⽅向。
注释框, 是为了对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的⼈更好地理解流程图的作⽤。它不是流程图中必要的部分，不反映流程和操作。
程序框图表⽰程序内各步骤的内容以及它们的关系和执⾏的顺序。它说明了程序的逻辑结构。框图应该⾜够详细，以便可以按照它顺利地写出程序，⽽不必在编写时临时构思，甚⾄出现逻辑错误。流程图不仅可以指导编写程序，⽽且可以在调试程序中⽤来检查程序的正确性。如果框图是正确的⽽结果不对，则按照框图逐步检查程序是很容易发现其错误的。流程图还能作为程序说明书的⼀部分提供给别⼈，以
便帮助别⼈理解你编写程序的思路和结构。
例：对⼀个⼤于或等于3的正整数，判断它是不是⼀个素数。
所谓素数，是指除l和该数本⾝之外，不能被其它任何整数整除的数。例如，13是素数，因为它不能被2，3，4，…，12整除。
判断⼀个数N(N＞3)是否素数的⽅法是很简单的：将N作为被除数，将2到(N—1)各个整数轮流作为除数，如果都不能被整除，则N为素数。算法可以表⽰如下：
①输⼊N的值。
② I＝2。
③ N被I除。
④如果余数为0，表⽰N能被I整除，则打印N“不是素数”，算法结束。否则继续。
⑤ I＝I+1。
⑥如果I≤N－l，返回③。否则打印N“是素数”。然后结束。
实际上．N不必被2到(N⼀1)的整数除，只需被2到N/2间整数除即可，甚⾄只需被2到之间的整数除即
可。例如，判断13是否素数，只需将13被2，3除即可，如都除不尽，N必为素数。步骤⑥可改为：
⑥：如果I≤，返回③。否则算法结束。
Fortran代码⽂件为。
a)    三种基本结构
传统的流程图⽤流程线指出各框的执⾏顺序，对流程线的使⽤没有严格限制。因此，使⽤者可以毫不
受限制地使流程随意地转来转去，使流程图变得毫⽆规律，阅读者要花很⼤精⼒去追踪流程，使⼈难以理解算法的逻辑。如果我们写出的算法能限制流程的⽆规律任意转向，⽽像⼀本书那样，由各章各节顺序组成，那样，阅读起来就很⽅便，不会有任何困难，只需从头到尾顺序地看下去即可。
为了提⾼算法的质量，使算法的设计和阅读⽅便，必须限制箭头的滥⽤，即不允许⽆规律地使流程乱转向，只能按顺序地进⾏下去。但是，算法上难免会包含⼀些分⽀和循环，⽽不可能全部由⼀个⼀个框顺序组成。如上例不是由各框顺序进⾏的，包含⼀些流程的向前或向后的⾮顺序转移。为了解决这个问题，⼈们设想，如果规定出⼏种基本结构，然后由这些基本结构按⼀定规律组成⼀个算法结构，就如同
⽤⼀些基本预制构件来搭成房屋⼀样，整个算法的结构是由上⽽下地将各个基本结构顺序排列起来的。1966年，Bohra和Jacoplni提出了以下三种基本结构，⽤这三种基本结构作为表⽰⼀个良好算法的基本单元。
顺序结构：如图所⽰的虚线框内，A和B两个框是顺序执⾏的。顺序结构是最简单的⼀种基本结构。
选择结构：如图所⽰的虚线框中包含⼀个判断框。根据给定的条件p是否成⽴⽽选择执⾏A和B。p条件可以是“x＞0”或“x＞y”等。注意，⽆论p条件是否成⽴，只能执⾏A或B之⼀，不可能既执⾏A⼜执⾏B。⽆论⾛哪⼀条路径，在执⾏完A或B之后将脱离选择结构。A或B两个框中可以有⼀个是空的，即不执⾏任何操作。
循环结构：⼜称重复结构，即反复执⾏某⼀部分的操作。有两类循环结构：
当型(While)：当给定的条件p成⽴时，执⾏A框操作，然后再判断p条件是否成⽴。如果仍然成⽴，再执⾏A框，如此反复直到p条件不成⽴为⽌。此时不执⾏A框⽽脱离循环结构。
直到型(Until)：先执⾏A框，然后判断给定的p条件是否成⽴。如果p条件不成⽴，则再执⾏A，然后再对p条件作判断。如此反复直到给定的p条件成⽴为⽌。此时脱离本循环结构。
注意两种循环结构的异同：(1)两种循环结构都能处理需要重
复执⾏的操作。(2)当型循环是“先判断(条件是否成⽴)，后执
⾏(A框)”。⽽直到型循环则是“先执⾏(A框)，后判断(条件)”。
(3)当型循环是当给定条件成⽴满⾜时执⾏A框，⽽直到型循
环则是在给定条件不成⽴时执⾏A框。
同⼀个问题既可以⽤当型循环来处理，也可以⽤直到型循环来处理。对同⼀个问题，如分别⽤当型循环结构和直到型循环结构来处理的话，则两者结构中的判断框内的判断条件恰为互逆条件。Fortran77和90/95标准都不提供do until语句，Compaq Visual Fortran也不提供此扩展（但有些计算机系统则提供），因此需要将直到型循环转换成⼀个当型循环结构：直到型循环等于⼀个A框加上⼀个当型循环，同时将给定的判断条件“取反”。
b)    结构流程图
1973年美国学者I.Nassi和B.Shneiderman提出了⼀种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在⼀个矩形框内。在该框内还可以包含其它的从属于它的框，即可由⼀些基本的框组成⼀个⼤的框。这种适于结构化程序设计的流程图称N-S结构化流程图，它⽤以下的流程图符号：
(1)顺序结构：A和B两个框组成⼀个顺序结构。
(2)选择结构：当p条件成⽴时执⾏A操作，p不成⽴则执⾏B操作结构。
(3)循环结构：当型循环结构下，图符表⽰先判断后执⾏，当p条件成⽴时反复执⾏A操作，直到p条件不成⽴为⽌。
直到型循环结构下，图符表⽰先执⾏后判断，当p条件不成⽴时反复执⾏A操作，直到p条件成⽴为⽌。
⽤以上三种N-S流程图中的基本框．可以组成复杂的N-S流程图，以表⽰算法。
例：将判别素数的算法⽤N-S流程图表⽰。
上⾯的⾮结构化流程图不是由三种基本结构组成的：图中间的循环部分有两个出⼝，不符合基本结构的特点。由于不能直接分解为三种基本结构，应当先作必要的变换再⽤N-S流程图的三种基本结构的符号来表⽰。即将第⼀个菱形框的两个出⼝汇合在⼀点。其⽅法是设⼀个标志值K，它的初始状态为0(表⽰N为素数)，当K≠0时为⾮素数。注意当型和直到型的判断条件。
Fortran代码⽂件为。
N-S图表⽰算法的优点是：⽐传统流程图紧凑易画，尤其是它废除了流程线。整个算法结构是由各个基本结构按顺序组成的，其上下顺序就是执⾏时的顺序。写算法和看算法只需从上到下进⾏就可以了，⼗分⽅便。归纳起来，⼀个结构化的算法是由⼀些基本结构顺序组成的；在基本结构之间不存在向前或向后的跳转，流程的转移只存在于⼀个基本结构范围之内(如循环中流程的跳转)；⼀个⾮结构化的算法可以⽤⼀个等价的结构化算法代替，其功能不变。如果⼀个算法不能分解为若⼲个基本结构，则它必然不是⼀个结构化的算法。
c)    伪代码表⽰的算法
画出while语句的流程图
⽤传统的流程图和N-S图表⽰算法直观易懂，但画起来⽐较费事，在设计⼀个算法时，可能要反复修改，⽽修改流程图是⽐较⿇烦的。因此，流程图适宜于表⽰⼀个算法，但在设计算法过程中使⽤不是很理想的(尤其是当算法⽐较复杂、需要反复修改时)。为了设计算法时⽅便，常⽤⼀种称为伪代码的⼯具。伪代码是⽤介于⾃然语⾔和计算机语⾔之间的⽂字和符号来描述算法。它如同⼀篇⽂章⼀样，⾃上⽽下地
写下来。每⼀⾏(或⼏⾏)表⽰⼀个基本操作。它不⽤图形符号，因此书写⽅便、格式紧凑，易懂也便于向计算机语⾔算法(即程序)过渡。
可以⽤英⽂、汉字、中英⽂混合表⽰算法，以便于书写和阅读为原则。⽤伪代码写算法并⽆固定的、严
格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。例如，对于电⼦在特殊⼏何构型材料中的散射问题：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。