理解流程图和算法

忘是亡心i 2023-10-04 01:18 26阅读 0赞

流程图使我们能够可视化应用程序如何从一条指令流向下一条指令，从开始到结束。在开始编写程序之前构建流程图有助于确保我们不会跳过程序本身的任何步骤，并为我们提供了一个工具来轻松地将这些步骤传达给他人。

**学习目标**

在本课结束时，您将能够：

*  解释什么是算法
 *  描述开发人员如何在软件开发过程中使用流程图
 *  识别流程图中的基本形状
 *  将算法映射到流程图

流程图基础

编程的有趣之处之一是计算机和程序真的非常简单。尽管我们可以创建执行复杂任务的大规模程序，但程序实际上只能做三件事。需要编程解决的问题逻辑纷繁复杂，程序设计语言里面为什么只有三种基本的程序结构就够用了？

对于程序设计语言中的三种基本结构：顺序、选择、循环，大家应该都比较熟悉了，确实也只有这些。

其实，这个问题是经过严格证明过的。1966年，计算机科学家 Bohm 和 Jacopini 证明了这样的事实：任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。所以，这三种结构就被称为程序设计的三种基本结构。也是 结构化程序设计 必须采用的结构。想详细了解的可以去看下论文：*Bohm C., Jacopini G. "Flow diagrams, Turing machines and languages with only two formation rules." Communications of the Association for Computing Machinery, Vol.9, pp. 366--371. 1966.*

荷兰学者Dijkstra1968年提出了“结构化程序设计”的思想，它规定了一套方法，使程序具有合理的结构，以保证和验证程序的正确性，这种方法要求程序设计者不能随心所欲地编写程序，而要按照一定的结构形式来设计和编写程序，它的一个重要目的是使程序具有良好的结构，使程序易于设计，易于理解，易于调试修改，以提高设计和维护程序工作的效率。

结构化程序规定了以下三种基本结构作为程序的基本单元： 以上三种基本结构可以派生出其它形式的结构.由这三种基本结构所构成的算法可以处理任何复杂的问题.所谓结构化程序就是由这三种基本结构所组成的程序.可以看到,三种基本结构都具有以下特点:①有一个入口.②有一个出口.③结构中每一部分都应当有被执行到的机会,也就是说,每一部分都应当有一条从入口到出口的路径通过它(至少通过一次).④没有死循环(无终止的循环).

按结构化程序设计方法设计出的程序优点是：结构良好、各模块间的关系清晰简单、每一模块内都由基本单元组成。这样设计出的程序清晰易读，可理解性好，容易设计，容易验证其正确性，也容易维护。同时，由于采用了“自顶向下、逐步细化”的实施方法，能有效地组织人们的智力，有利于软件的工程化开发。

*  **顺序**：按**顺序**执行一系列语句
 *  **选择**：根据定义的条件遵循特定路径
 *  **循环**：重复一系列指令，直到满足条件

我们使用术语*控制流*来定义程序从一条指令到下一条指令的路径，我们使用流程图来可视化控制流。

另一个重要术语是*算法*。虽然电视节目和电影让算法听起来像是只有软件开发人员才能理解的非常技术性的东西，但术语*算法*实际上只是一组定义明确的指令，计算机或类似机器可以遵循这些指令来达到所需的输出。换句话说，我们使用流程图来绘制算法。

**顺序**

默认情况下，算法中最简单的路径是从一个语句顺序移动到下一个语句。如下图所示，包含两条语句，依次执行，程序结束。这种控制结构称为*顺序*。

![20210609210602611.png][]

顺序流程图

顺序是最容易理解的控制结构，因为它们只是按照给定的顺序执行语句。计算机从左到右、从上到下读取代码，就像看书一样。

最终，实际完成所需工作的程序指令将被组织成序列。序列可能会变得非常大，因为方法可以调用其他方法，并且对象可能需要将它们的某些工作分给其他对象。

例如，考虑在电子商务网站上结账的工作流程。当您点击结帐按钮时，程序将完成一系列需要跨多个对象完成的步骤。顶部对象通常控制结帐流程的工作流程，但子序列可能包括以下内容：

1.  登录
2.  输入付款信息
3.  将支付信息发送到支付处理方/银行
4.  通知仓库订单
5.  通知船公司取货
6.  通过电子邮件向客户发送确认

等等。

熟练的开发人员会在开始编写代码之前详细列出这些流程中的每一个。他们将代码分成将相关事物组合在一起的方法和对象，同时牢记易于维护和可测试性。因此，序列中的每个步骤最终可能会调用其他序列。

**选择**

在*选择*情况下，程序到达有两个或更多可能的后续步骤的点，并且它必须评估条件以确定要采取哪条路径。分支总是基于一个可以回答为真或假的问题，并且在大多数情况下，真实情况决定了程序将遵循的顺序。但是，也可能存在可以遵循不同序列的错误情况。

分支案例可以像登录网站一样简单。如下图所示，在分支流程图中，菱形代表决定控制流将遵循哪个分支的条件，例如，“用户名和密码是否正确？” 如果条件为真，则程序将用户带到主页。如果为假，程序将显示错误并提示用户重试。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70][]

分支流程图

**循环**

在循环情况下，我们继续运行一系列指令，直到满足某个条件。我们在日常生活中经常这样做。洗手时，我们的条件是，“我的手干净了吗？” 如果没有，那么我们将继续擦洗，直到它们干净为止。

在软件开发中有几种不同种类的循环。某些循环会运行特定的次数，例如遍历文本字符串中的字符数。如果我们知道字符串中有多少个字符，我们就知道要循环多少次。

在其他情况下，我们事先不知道需要循环多少次。在前面的网站示例中，用户可能第一次正确输入用户名和密码，但由于人类是不完美的生物，他们可能要到第二次或第十次才能正确输入信息。在这些情况下，我们希望构建循环以继续直到他们正确为止。

一个循环包括一个分支，但分支之后的序列返回到分支，类似下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 1][]

循环流程图

循环将继续，直到满足指定的条件。一旦满足条件，循环结束，控制流移动到程序中的下一个指令块。

开发人员必须注意的一件事是无限（或无限）循环。很可能定义一个循环的条件，使得该条件永远不会被满足（例如定义一个登录循环来要求用户名和密码，但没有要求用户输入密码）。在这种情况下，循环将无限期地运行，直到其他东西停止它。

**流程图**

使用我们的控制结构和分支语句流，我们可以想出一些有趣的算法。事实上，正如我们之前指出的，即使是最复杂的场景也必须最终分解为这三种结构。

虽然流程图中有许多可用的符号，但最常见的包括以下符号：

*  **椭圆形或圆角矩形**：表示算法的起点和终点
 *  **矩形**：表示计算机必须完成的指令
 *  **平行四边形**（倾斜的矩形）：表示输入和输出
 *  **菱形**：表示条件

我们还使用单向箭头指示完成步骤的顺序。从技术上讲，流程图可以以任何方式定向，因为箭头定义了完成步骤的顺序，但它们最常见的是从上到下定向（因此程序从顶部开始，在底部结束）或左到右边。较大的流程图可以包括从上到下和从左到右方向的组合。

流程图当然可以用手写出来，但通常最好使用铅笔或其他可擦除介质来更容易更正。还有几个软件选项，包括 Draw.io（一个免费的在线图表工具）和 LucidChart（一个包含免费选项的付费程序）。Microsoft Office 产品（包括 Visio、Word 和 PowerPoint）也包括流程图工具，Google Drive 中的绘图也是如此。

**提示**

*  Draw.io 可以在您操作系统的应用商店或在[drawio.com][]和 找到[app.diagrams.net][]。
 *  LucidChart 可以在网上找到[www.lucidchart.com][]。
 *  可以在 Google Chrome 商店中找到 Google 绘图。

**流程图示例**

现在让我们看看我们如何使用流程图来绘制一个简单的算法。考虑一种要求用户输入奇数的方法。执行此操作的步骤可能包括以下内容：

1.  声明变量来存储键盘输入和解析的数字。
2.  开始循环。
    
    1.  提示用户输入奇数。
    2.  从键盘读取输入。
    3.  如果输入是数字
        
         *  如果数字是奇数
            
             *  退出循环
         *  如果数字不是奇数
            
             *  通知用户数字不是奇数
             *  重新开始循环
    4.  如果输入不是数字，请执行以下操作：
        
         *  通知用户输入的不是数字
         *  重新开始循环
3.  返回号码。

所以，我们有一个循环，它应该一直运行到输入一个奇数为止。检查奇数需要两个检查：首先它是一个数字条目，其次解析的数字是奇数。

前面的列表是*伪代码的*一种形式，可以用来补充（甚至替换）早期开发过程中的流程图。伪代码听起来很技术（就像*算法*），但它实际上是指使用任何人都可以理解的更自然的人类语言写出程序步骤的过程。一旦我们确定我们已经确定了所有必需的步骤，我们就可以将伪代码翻译成选择的编程语言（例如 C\#、Java 或 Python）。

在伪代码中，文本中的每个缩进代表一个代码块，并且这些块中的每一个都将是流程图中的一个形状。表示该算法步骤的流程图可能如图 9.4 所示。

**提示**

您现在拥有程序的伪代码和流程图。作为本课的练习，编写此程序的代码。

概括

流程图是一种强大的工具，用于可视化程序中的逻辑将如何流动并将其传达给他人。根据我们在本课中学到的知识，我们可以构建可读的流程图来帮助我们编写更好的代码。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 2][]

示例流程图

我们建议您在打开 IDE 以创建程序之前，通过绘制流程图或写出伪代码中的步骤（如果不是两者）来启动您编写的任何程序。

最重要的是，如果你不能在纸上或白板上解决一个问题，那么你就无法用代码解决它。确保你能用通俗易懂的英语解释你的程序试图做什么，至少对你自己来说，是思考编码逻辑的重要第一步。花时间预先计划事情是值得的。以后会省去很多痛苦和挫折。

**提示**

在建筑中，他们说，“测量两次，切割一次。” 创建流程图就像测量，编码就像切割。在绘制流程图或测量时进行调整比在削减代码时容易得多。

练习

现在我们了解了控制语句（例如语句和循环）的类型、变量和流程if，事情变得有趣了。这些构建块可用于构建更复杂的代码。我们在本课中了解到，刚开始编码的人犯的最大错误之一就是直接投入编码，而没有计划他们想要做什么。

作为本课的练习，您将看到一个游戏。您将创建流程图，然后编写代码。我们为此练习提供了一种可能的解决方案，因此在您自己尝试之前不要向前看。

*  **练习 1**：猜谜游戏

**练习 1：猜谜游戏**

就像一个优秀的作家创建一个大纲和一个家庭建设者制定蓝图一样，一个优秀的程序员在开始编程之前规划他们的逻辑。在本练习中，您将写出绘制猜谜游戏所需的步骤，然后构建流程图。

在这个版本的猜谜游戏中，程序开始时向第一个玩家请求一个指定范围内的数字，比如 1 到 20。一旦你有了这个数字，第二个玩家应该被要求尝试猜这个数字。然后程序给出更高或更低的线索，直到玩家 2 最终猜对。您需要考虑以下几点：

*  我们需要跟踪哪些数据？
 *  我们需要有一个过程，让玩家 1 输入数字，让玩家 2 猜测。
 *  用户需要猜多少次？从游戏到游戏不一定都一样。
 *  我们需要提示用户输入。
 *  我们需要从键盘读取用户的输入。
 *  用户是否猜对了数字？如果他们猜错了怎么办？
 *  用户是否甚至在正确的范围内猜测？
 *  如果猜测在范围内，是否正确？猜测是否高于答案？是不是更低？
 *  我们需要显示消息吗？
 *  我们需要让他们输入另一个猜测吗？

考虑所有这些问题并创建流程图。

**笔记**

专注于这个游戏的流程图。如果您考虑编写代码，您可能会注意到这款游戏的运行方式存在缺陷。

如果玩家 2 可以看到玩家 1 输入的提示和答案，那么猜出答案将非常容易。在下一课中，我们将学习如何更新这个程序，让计算机随机生成要猜测的数字。

**一个可能的流程图解决方案**

在您创建流程图之前，请勿进一步阅读或查看以下内容。以下是一种可能的流程图解决方案的详细信息以及本练习的代码。

**猜谜游戏流程图**

开始我们的流程图，我们首先需要弄清楚我们需要跟踪哪些数据。我们需要一个变量作为答案。我们还需要一个用户输入，我们将其称为*guess*。最后，我们需要一个扫描器来从控制台读取输入。所以，就我们的流程而言，我们需要做的前三件事就是声明这三个变量。

接下来，我们需要有一个过程来提示玩家 1 输入要猜的数字。提示后，我们希望从键盘读取他们的输入。这是一个输入/输出过程，因此我们将使用平行四边形来表示获取该数字。我们将该值存储在我们的 answer 变量中。这在下图第 1 节中显示。

**笔记**

请注意，我们没有进行任何错误检查以确保输入的数字在我们设置的范围内。这是您可以自己添加到流程图中的内容。

玩家 2 现在可以开始猜测了。玩家 2 猜测的次数取决于玩家的幸运程度。游戏之间的猜测次数不一定相同。这听起来像是一个循环的工作while。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 3][]

猜谜游戏流程图

在循环中，我们将提示玩家输入（他们的猜测）并再次从键盘读取他们的输入。这在上面流程图的第 2 节中显示。

收到输入后，我们想知道的第一件事是用户是否猜对了。如果玩家确实输入了正确的猜测，我们可以显示胜利信息并结束程序。

如果他们猜错了怎么办？然后我们需要执行我们的假条件。此时，我们将想看看他们是否在给定的范围内猜测。在我们的例子中，该范围在 1 到 20 之间。如果用户没有在该范围内进行猜测，我们将显示一条消息，然后我们将返回到输入提示。

如果猜测在范围内，我们可以查看猜测是否高于答案。如果是，那么我们将打印一条消息，告诉他们猜测更低，然后我们将返回提示他们再次猜测。

最后，如果猜测不等于答案并且在范围内并且不高于答案，那么唯一可能的选择是猜测太低，我们需要打印一条消息告诉玩家在将他们发送回要求他们输入猜测的提示之前猜测更高的数字。

**猜谜游戏代码**

在这一点上，我们对猜谜游戏的工作原理有了很好的理解，并且我们已经考虑了它的基本需求和可能性。现在轮到您将流程图转换为代码。在进一步阅读之前，请自行完成此操作。

当我们将流程图转换为代码时，我们需要做的第一件事是声明我们的变量并将它们设置为初始值。正如你在前面的教训，为此与适当的类型Scanner，int以及int分别申报您的扫描仪，答案和猜测。

int answer = 0;

int guess = 0;

Scanner myScanner = new Scanner(System.in);

接下来，您需要从用户那里获取答案并将其放入 answer 变量中。您在之前的课程中了解到，这可以通过多种方式完成。让我们使用System.out.println和nextInt方法来做到这一点。

System.out.println("Player 1: Please enter a number between 1 and 20:");

answer = myScanner.nextInt();

一旦我们有了答案，我们就开始我们的循环。我们想循环直到玩家 2 猜到正确答案。这可以通过创建一个无限循环来打破，所以我们将使用“while true” ?? 诡计。

while (true) \{

// program code that will need a break to exit!

循环开始后，是时候提示玩家 2 从控制台进行猜测了。我们可以按照我们要求答案的方式来做到这一点。

System.out.println("Please guess a number between 1 and 20: ");

guess = myScanner.nextInt();

现在让我们看看我们如何处理输入的数字。首先，我们检查猜测是否等于答案。如果他们猜对了，我们想离开循环。我们可以用关键字来做到这一点break。如果他们没有正确回答，那么我们可以继续该程序。我们的程序可以确定要遵循流程图的哪一部分。

if ( guess == answer)

break; // they've solved the problem, so exit loop!

else

// continue with program

让我们遵循胜利的逻辑。在这种情况下，使用break，我们跳出while循环并告诉用户他们猜对了。到那时，程序就完成了，可以结束了。

如果猜测不是答案，那么根据流程图，我们看看他们是否猜测在 1 到 20 之间。如果猜测小于 1 或大于 20，那么我们知道它不在我们想要的范围内，所以我们将给玩家一条消息并使用continue关键字重新开始循环并提示用户再次输入猜测。如果它在范围内，我们将继续前进。

if (guess < 1 || guess> 20)

System.out.println("Enter a guess between 1 and 20.");

continue;

在这一点上，我们有一个范围的猜测，所以我们可以看看猜测是否大于答案。如果是，那么他们需要猜得更低，所以我们告诉他们。然后我们再次使用关键字返回顶部continue。

if (guess> answer)

System.out.println("Guess is too high. Pick a lower number!");

continue;

如果前面的条件都不成立，那么我们可以打印一条消息，说他们需要猜得更高，让循环回到顶部。请注意，continue这里不需要，因为我们已经在循环的底部，无论如何它都会回到顶部。

如您所见，每一段编码都适合流程图的每一部分。像我们的流程图一样遵循逻辑图可以使应用程序的编写更加容易且不易出错。您可以将练习清单 9.1 中的完整代码与图 9.5 中的流程图进行比较，看看它们是否一致。

**小费**

当您是一名专业程序员时，您不仅要创建流程图，还要创建列出所有字段和方法的对象图，甚至是前端屏幕的模型。这不仅可以帮助您组织您的想法，还可以为其他开发人员阐明您的逻辑和流程，他们以后可能会被要求审查和编辑您的代码。

**The GuessingGame.java**

import java.util.Scanner;
    
    class GuessingGame {
    
    	public static void main(String[] args) {
    		// declare the number variables and initialize to 0
    		int answer = 0;
    		int guess = 0;
    		// declare and initialize a Scanner object
    		Scanner myScanner = new Scanner(System.in);
    
    		// ask player 1 to enter a number from 1 to 20
    		System.out.println("Player 1: Please enter a number between 1 and 20:");
    		// now wait until a number is entered
    		answer = myScanner.nextInt();
    		// Note that there should be error checking here!
    
    		// Now start getting guesses!
    		while (true) {
    			// Get a guess!
    			System.out.println("Please guess a number between 1 and 20: ");
    			guess = myScanner.nextInt();
    
    			// Does the guess equal the answer?
    			if (guess == answer) {
    				break; // they've solved the problem!
    			} else if (guess < 1 || guess > 20) {
    				System.out.println("Enter a guess between 1 and 20.");
    				continue;
    			}
    
    			if (guess > answer) {
    				System.out.println("Guess is too high. Pick a lower number!");
    				continue;
    			}
    			System.out.println("Guess is too low. Pick a higher number!");
    		}
    
    		System.out.println("You got it! The answer was: " + answer);
    
    	}
    }

[20210609210602611.png]: https://img-blog.csdnimg.cn/20210609210602611.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210609210623335.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210609210635987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70
[drawio.com]: http://drawio.com
[app.diagrams.net]: http://app.diagrams.net
[www.lucidchart.com]: http://www.lucidchart.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210609210654629.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210609211332114.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70