EDIT: EINFÜHRUNG

Um eine breitere Leserschaft zu erreichen, habe ich meine ursprüngliche Frage anhand eines ausführlichen (und etwas langweiligen) Beispiels aus dem wirklichen Leben umformuliert. Die ursprüngliche Frage wird (weit) unten angezeigt.

Tom wurde soeben (abhängig von seiner Leistung in den ersten beiden Arbeitstagen) als Junior Software Engineer bei Acme Inc. eingestellt. Seine Aufgabe ist die Implementierung von Algorithmen, die von erfahrenen Softwareentwicklern in der Programmiersprache Acme ++ entwickelt wurden. Das Unternehmen folgt einem strengen "nogotoenn Tom seine Probezeit in Ausnahmefällen ausüben kann, wird ihm eine Vollzeitstelle im Unternehmen angebote

An Tag 1 erhält Tom den folgenden zu implementierenden Algorithmus.

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 ist der Meinung, dass die Aufgabe sehr kompliziert ist und er denkt, dass er davon profitieren würde, die abstrakte Struktur des Programms zu studieren, indem er es als Flussdiagramm darstellt. Nach dem Zeichnen des folgenden DiagrammsFlussdiagramm des ersten Tages er erkennt schnell, dass er aufgefordert wurde, den absoluten Wert von x zu berechnen, und kann ihn mit einer einfachen if-then-else-Anweisung implementieren. Tom ist sehr glücklich und beendet seine Aufgabe am Ende des Tages.

An Tag 2 erhält Tom den folgenden zu implementierenden Algorithmus.

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

Tom, ein Neuling, fühlt sich wieder wie es besser wäre, den Algorithmus auf abstrakte Weise zu verstehen, also zeichnet er das folgende FlussdiagrammFlussdiagramm des zweiten Tages.

Inspektion des Flussdiagramms zeigt, dass Tom gebeten wurde, eine while-Schleife zu implementieren, die auf die erste nicht negative Eingabe wartet. Tom ist sehr glücklich und beendet seine Aufgabe am Ende des Tages.

ufgrund seiner herausragenden Leistung wurde Tom für das Unternehmen eingestell

m dritten Tag wird Tom jedoch in die Tiefe geworfen, als er 1996 einen 1000-Zeilen-Algorithmus erhälgoto jumps, entworfen von einem ehemaligen Mitarbeiter des Unternehmens, und es ist niemand mehr da, der wissen würde, was der Algorithmus macht, wie er es macht und warum er überhaupt so entworfen wurde. Dies betrifft Tom jedoch überhaupt nicht, da seine einzige Aufgabe darin besteht, den Algorithmus unabhängig von seiner Beschaffenheit zu implementieren. Ausgerüstet mit dem Fachwissen der letzten beiden Tage zeichnet er das Flussdiagramm auf 1000 Knoten mit 1997 gerichteten Kanten. Tom, der sehr verzweifelt ist, fragt beim Stackoverflow, was zum Teufel mit einem solchen Durcheinander zu tun hat, wo erfahrene Programmierer ihm wiederholt raten,

Brechen Sie das Programm in kleinere Teile auf. uner wurde beruhigt, dass es in bestimmten Fällen tatsächlich in Ordnung ist, @ zu verwendgoto; unr wird angewiesen, das Programm zu "restrukturieren"

Tom ist sehr fleißig und bedenkt diese Ratschläge. Seine Idee lautet wie folgt:

he erkennt, dass, wenn eine zusammenhängende Komponente des Flussdiagramms genau ein In-Grad und genau ein Out-Grad hat, dies als ein "Sub-Algorithmus" betrachtet werden kann, der unabhängig entwickelt werden kann, so dass er sein eigenes zerlegen kann Aufgabe auf diese Weise. Er hat jedoch keine Ahnung, wie man solche Komponenten überhaupt findet und ob es andere intelligente Möglichkeiten gibt, das Problem weiter zu löse Tom ist es egal, ob mitgoto ist eine gute oder schlechte Programmierpraxis (sieheGOTO immer noch als schädlich angesehen?), was ihn beunruhigt, ist, dass es in seinem Unternehmen bestimmte Programmierrichtlinien gibt, die er jederzeit befolgen muss.Tom kann den Algorithmus tatsächlich in dem Sinne berühren, dass er nach eigenem Ermessen bestimmte Anweisungen ersetzen kann, die zu einem äquivalenten Algorithmus führen. Tom hat jedoch keine Ahnung, welcher Teil des Programms umstrukturiert werden muss, und vor allem versteht er nicht, warum die Umstrukturierung notwendig ist. Tom starrt nervös auf sein 1000-Vertex-Diagramm und weiß nicht, wie er es überhaupt implementieren soll. Die Fragen zu diesem (bearbeiteten) Beitrag lauten wie folgt:

Können Sie Tom dabei helfen, herauszufinden, wie mit der Implementierung von etwas begonnen werden kann, das nicht "Zwei-Zeilen-Tot-Offensichtlich" ist? Ist insbesondere klar, in welcher Reihenfolge die von den Knoten des Flussdiagramms beschriebenen Aufgaben auszuführen sind? Ist klar, in welcher Reihenfolge bestimmte verschachtelte Schleifen nacheinander auftreten sollen?

Was sind die kleinsten "Atome" des Flussdiagramms, die nicht weiter in kleinere Teile zerlegt werden können? Das heißt, wann kann Tom sicher auf Stackoverflow reagieren, dass "ich meinen Algorithmus bereits in kleinere Teile zerlegt habe"? Stimmt es, dass alles im Wesentlichen eine while-Schleife und / oder ein binärer Verzweigungspunkt ist (die Aufgaben der Tage eins und zwei)?

Wie kann man ein solches "Atom" automatisch mehr oder weniger so implementieren, wie es Tom bereits an den Tagen eins und zwei getan hat?

ann Tom mit dem CEO argumentieren, dass mitgoto ist in bestimmten Fällen unabdingbar, das heißt, sie verwenden es entweder, um einen bestimmten Algorithmus zu implementieren, oder es gibt absolut keine andere Möglichkeit, ihn gemäß den Unternehmensrichtlinien zu implementieren (d. h. ohne die Verwendung von @goto)?

Welche Teile des Flussdiagramms sind problematisch und erfordern eine Umstrukturierung und warum? Zum Beispiel könnte eine Drei-Wege-Verzweigung durch eine verschachtelte Zwei-Wege-If-Then-else-Anweisung ersetzt werden. Das heißt, Tom könnte mit Sicherheit davon ausgehen, dass jeder Knoten in seinem Flussdiagramm einen Grad von höchstens zwei hat. Aber welche anderen Umstrukturierungen sollten vorgenommen werden, um alle durch das @ verursachten verschachtelten Schleifen zu behandelgoto Anweisungen? Welche Graph-Eigenschaft macht die Umstrukturierung notwendig? Vielleicht hochgradig?

Was ist die mathematische (grafische) Theorie hinter dem Flussdiagramm eines ursprünglich vorgeschlagenen Algorithmus (vom Software-Entwicklungsteam) und das restrukturierte und aufgeschlüsselte Flussdiagramm (die Flussdiagramme) des Algorithmus (der Algorithmen), das (sagen wir Tom) tatsächlich ist? mehr oder wenigerautomatisc Utensilien?

URSPRÜNGLICHE FRAGE

Angenommen, ich habe einen Algorithmus, der binäre Entscheidungen verwendet undgoto Anweisungen. Der Algorithmus wird in N> = 2 (endlichen) Schritten auf folgende Weise beschrieben und sollte sequentiell (einen Schritt nach dem anderen) ausgeführt werden:

ALGORITHMUS WAS AUCH IMMER

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

Du hast die Idee. Zum Beispiel beschreibt Knuth die Algorithmen in seinen Büchern auf solch programmiersprachenunabhängige Weise.

Die Frage ist nun, wie man eine solche Beschreibung auf hoher Ebene mit @ transformiergoto Anweisungen in eine tatsächliche Implementierung mit while-Schleifen und if / else-Anweisungen? Ist es möglich, alle @ vollständig zu beseitiggoto -Anweisungen und Ersetzen durch eine while-Schleife? Wenn ja, wie soll man das machenallgemei?

asierend auf der Beschreibung des Algorithmus ist es möglich, das entsprechende Flussdiagramm und damit den (gerichteten) Flussgraphen zu konstruieren. Die Frage ist also mit anderen Worten: "Wie man einen Code basierend auf seinem Flussdiagramm ohne @ implementiergoto Aussagenallgemei? ".

Diese Frage kann auf zwei Arten beantwortet werden. Vorzugsweise und hoffentlich suche ich nach einem algorithmischen Weg, um ALGORITHMUS JEDOCH zu implementieren. Wenn ALGORITHMUS WHATEVER istseh simple, dann ist intuitiv klar, was man tun soll, aber es scheint mir, dass die Dinge ziemlich kompliziert werden, wenn ein Schritt häufig besucht wird (es springen viele goto-Anweisungen dorthin), oder mit anderen Worten, wenn einer der Knoten des Flussdiagramms hat einen großen Grad. Dann sehe ich nicht ganz, in welcher bestimmten Reihenfolge die while-Schleifen verschachtelt werden sollen. Andererseits ist es durchaus möglich, dass man einfach nicht tun kann, was ich im Allgemeinen will, und eine solche Antwort sollte durch eine allgemeine Beschreibung des ALGORITHMUS UNMÖGLICH untermauert werden, die deutlich zeigt, dass man, egal was ist, einfach nicht kann vermeide das Benutzengoto springt in eine aktuelle Implementierung.

Es scheint mir, dass die Umsetzung in Flussdiagramme mehrmals gefragt wurde:Automatisches Flussdiagramm-Tool und hierAlgorithmus zum Erstellen eines Flussdiagramms [Eine kleine Anleitung?]. Das Programm code2flow scheint ein guter Ausgangspunkt für die Visualisierung eines Codes zu sein.

Jedoch hier interessiert mich die andere richtung. Eine einfache Suche ergab, dass DRAKON (siehe auchhttps: //en.wikipedia.org/wiki/DRAKO undhttp: //drakon-editor.sourceforge.net) könnte genau das tun, wonach ich frage. Aus dieser Perspektive stellt sich die Frage, wie ein solches automatisches Flussdiagramm-zu-Code-Programm unter der zusätzlichen Annahme funktionieren könnte, dass es das @ nicht verwendegoto Erklärung