algorithm - 如何将流程图转换为实现？

Closed. This question needs to be more focused。它当前不接受答案。












想要改善这个问题吗？更新问题，使它仅关注editing this post的一个问题。

4年前关闭。



Improve this question




编辑:简介

为了扩大读者群，我通过一个详尽的(有些乏味的)现实生活例子重新阐述了我的原始问题。原始问题如下所示。

Tom刚被聘为Acme Inc.(根据其在前两个工作日的表现而定)担任初级软件工程师。他的工作是用编程语言Acme++实现由高级软件开发人员设计的算法。公司按照首席执行官的独家命令严格执行“禁止goto”政策。如果汤姆在试用期间表现出色，他将在公司担任全职工作。

在第1天，Tom收到以下要实现的算法。

Step 1. START
Step 2. Input x
Step 3. In case x<0 goto Step 4 otherwise goto Step 5
Step 4. Set x=-x
Step 5. Output x
Step 6. END

Tom认为任务非常复杂，他认为通过将其表示为流程图，可以从研究程序的抽象结构中受益。在绘制下图Flow chart of day one之后，他很快意识到，他被要求计算x的绝对值，并且他可以使用简单的if-then-else语句来实现它。汤姆很高兴，他在一天结束时完成了任务。

在第2天，Tom收到以下要实现的算法。

Step 1. START
Step 2. Input x
Step 3. In case x<0 goto Step 2 otherwise goto Step 4
Step 4. Output x
Step 5. END

作为新手，汤姆再次感到最好还是以抽象的方式理解该算法，因此他绘制了以下流程图Flow chart of day two。

对流程图的检查表明，Tom被要求执行一个while循环，以等待第一个非负输入。汤姆很高兴，并在一天结束时完成了任务。

基于他出色的表现，Tom被聘请为该公司。

但是，在第3天，Tom陷入了深渊，因为他收到了由公司前雇员设计的具有1996 goto跳转的1000行算法，并且没有其他人知道算法的作用，它是如何做的以及为什么要以这种方式设计它。但是，这根本不涉及汤姆，因为汤姆的唯一任务是不管算法是什么都实现该算法。凭借前两天的专业知识，他在具有1997个有向边的1000个节点上绘制了流程图。汤姆非常绝望，在stackoverflow上询问如何处理这种困惑，有经验的程序员反复建议他这样做。

将程序分解为更小的部分；和

他确信在某些情况下使用goto实际上是可以的;和

被告知要“重组”该程序。

汤姆非常勤奋，考虑了这些建议，他的想法如下:

他认识到

，如果流程图的连接部分正好具有一个入度，而正好具有一个出度，则可以将其视为可以独立开发的“子算法”，因此他可以将其分解以这种方式完成任务。但是，他不知道如何首先找到这样的组件，也不知道是否还有其他聪明的方法可以进一步解决问题。

Tom并不十分在意使用goto是好的编程方法还是不好的编程方法(请参阅GOTO still considered harmful?)，他担心的是他的公司始终需要遵循某些编程准则。

Tom确实可以触及该算法，因为他可能会替换某些指令，从而根据自己的判断得出等效的算法。但是，汤姆不知道计划的哪一部分需要重组，更重要的是，他不理解为什么必须进行重组。汤姆紧张地盯着他的1000顶点图，并不真正知道如何一开始就实现它。

有关此(已编辑)帖子的问题如下:

您可以帮助汤姆弄清楚如何开始实现“两线制不明显”的东西吗？特别是，显然应该按照什么顺序执行流程图各节点所描述的任务？是否清楚某些嵌套循环应该以什么顺序依次出现？

流程图中最小的“原子”是什么，这些原子不能进一步分解为较小的部分？也就是说，Tom何时可以自信地对stackoverflow做出回应，“我已经将算法分解成较小的部分”？确实所有内容都是一个while循环和/或一个二进制分支点(第一天和第二天的任务)吗？

如何像汤姆在第一天和第二天那样自动地或多或少地实现这种“原子”？

Tom能否与CEO争论说在某些情况下使用goto是必不可少的，也就是说，他们要么使用goto来实现某种算法，要么完全没有其他方法可以按照公司的准则来实现(即，不使用goto)？

流程图的哪些部分存在问题，需要进行重组，为什么？例如，三路分支可以用嵌套的两路if-then-else语句代替，也就是说，Tom可以安全地假定流程图中的每个节点的出节点数最多为2。但是，应该采取什么其他重组措施来处理由goto语句引起的所有嵌套循环呢？什么样的图形属性使重组成为必要？也许，学位高？

(由软件开发团队提供)最初提出的算法的流程图背后的数学(图形)理论是什么，以及一个(例如Tom)实际对算法进行重组和分解的流程图是什么或多或少自动执行？

原始问题

假设我有一些使用二进制决策和goto语句的算法。该算法以以下高级方式在N> = 2(有限)步中进行描述，并且应按顺序执行(一个步骤一个接一个):

随便什么算法

Step 1. START
Step 2. Do something. If condition in Step 2 holds goto Step X else goto Step Y.
Step 3. Do something. If condition in Step 3 holds goto Step U else goto Step V.
Step 4. Do something.
Step 5. Do something. If condition in Step 5 holds goto...
Step 6. ...
...
Step N. END

你明白了。例如，Knuth以这种与编程语言无关的高级方式在他的书中描述了算法。

现在的问题是，如何将带有goto语句的高级描述转换为带有while循环和if/else语句的实际实现？是否可以完全消除所有goto语句，并用while循环替换它们？如果是这样，一般应该怎么做？

基于算法的描述，可以构造相应的流程图，从而构造(定向)流程图。因此，换句话说，问题是“如何在没有goto语句的情况下基于其流程图实现代码？”。

有两种方法可以回答这个问题。最好且非常有希望的是，我正在寻找一种算法方法来实现算法。如果ALGORITHM WHATEVER非常简单，则可以直观地知道应该怎么做，但是在我看来，一旦频繁访问某个步骤(其中有许多goto语句在其中跳动)，或者换句话说，何时进行操作，事情就会变得相当复杂。流程图的节点之一具有较大的度数。然后，我不太清楚while循环应该以什么特定顺序嵌套。另一方面，一个人很可能根本无法完成我通常想要的事情，而这样的答案应该得到对算法不可能的高级描述的支持，该描述清楚地表明，无论如何，一个人根本无法做到避免在实际实现中使用goto跳转。

在我看来，多次询问将实现转换为流程图:Automatic flowchart tool和此处Algorithm to create flow chart [A little guidance??]。程序code2flow似乎是可视化代码的良好起点。

但是，在此我对另一个方向感兴趣。一个简单的搜索显示DRAKON(另请参阅https://en.wikipedia.org/wiki/DRAKON和http://drakon-editor.sourceforge.net/)可能完全在执行我要问的事情。从这个角度来看，问题是，在不使用ojit_code语句的额外假设下，这种自动流程图到代码程序将如何工作？

最佳答案

引用OP:最好，而且非常有希望，我正在寻找一种算法方法来实现任何算法

好吧，显而易见的答案是用目标语言为算法的每个步骤定义一个标签，在该标签上为每个步骤编写代码，并按照算法所描述的完全插入GOTO语句。这将为您提供一个工作程序，大多数人将其称为“意大利面条代码”。

OP进行了冗长的介绍，暗示他(或可能是Tom)宁愿以令人信服的匹配算法的方式编写goto-free版本。

好的，所以好消息是Bohm and Jocopini很久以前就表明，您可以使用序列， if-then-else 和这三个基本控制流操作来实现任何计算，同时循环，具有不错的属性一次进入，一次退出。因此，我们知道有一个“结构化程序”实现。

不好的消息是它们的构造性证明(从gotoful/流程图的版本构建这样的程序的过程)引入了一组 bool 变量和其他测试来控制循环。这些变量用于跳过循环迭代的其余部分，以强制退出循环，并告知循环调用者循环已退出。这个额外的
对我而言，即使您不反对管理这些变量所需的存储和执行时间，对于我来说，代码也会使所生成的程序在读取时变得更糟。 (请参阅Wikipedia链接以获取针对goto-ful COBOL程序执行此操作的算法)。

更好的消息是S. Rao Kosaraju演示了如果您可以摆脱任意嵌套深度的循环，则无需额外的控制变量即可构建此类程序。许多编程语言都提供了这样的功能。 C提供了一个脆弱的版本，其“break N”；从N个嵌套循环中跳出的语句(当有人在现有代码中插入一个额外的循环而没有注意到break语句时，使用此崩溃的著名的AT＆T东海岸电话系统)。 Ada和其他语言允许人们给循环加上标签，实际上是“leave”以指定的标签名称离开循环。对我来说，这是一个不错的解决方案。 [我更喜欢一种变体，其中有一个带有标签的开始-结束块，可以“离开”。
如果您的语言没有这样的标签离开结构，但您愿意以经过样式批准的方式使用GOTO语句(而不是临时方式)，则可以通过在每个循环后放置标签并编写“goto”来模拟离开语句。而不是离开。

因此，我们知道可以从干净的任意流程图/有信用的程序中构建结构化程序。

通过按照Sue Graham 1975年的论文，将原始流程图简化为结构化的子元素，可以实现此目的的算法，
A fast and usually linear algorithm for global flow analysis。

该算法的本质是在可能的情况下，逐步将原始流程图逐步简化为Bohm/Jacopini原语(序列/if-then-else/loop)构造，并减少“不可归约”构造(以流程图中的小结为例) )看起来并不特殊。在每个步骤中，流程图的一部分都被简化为该部分的单个摘要节点。最终，此过程将任意复杂度的原始流程图减少到单个节点中。此时，还原过程可以反向运行，每个摘要节点都可以扩展回原始节点。

出于OP的目的，摘要节点的扩展提供了以结构化的方式为简化的子图表编写代码的机会。重复进行直到产生原始流程图，然后使整个程序以结构化的方式编写。

[今天就这些。让我们看看我是否可以产生一个算法。关注此空间]。

关于algorithm - 如何将流程图转换为实现？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36647765/