РЕДАКТИРОВАТЬ: ВВЕДЕНИЕ

Чтобы охватить более широкую аудиторию, я переформулировал свой первоначальный вопрос на сложном (и несколько утомительном) примере из реальной жизни. Оригинальный вопрос показан (далеко) ниже.

Том был нанят (в зависимости от его результатов в течение первых двух рабочих дней) в Acme Inc. в качестве младшего инженера-программиста. Его работа заключается в реализации алгоритмов, разработанных старшими разработчиками программного обеспечения, на языке программирования Acme ++. Компания следует строго "нетgoto«Политика по исключительному распоряжению генерального директора. В случае, если Том может выполнять исключительно в течение испытательного срока, ему будет предложена полная занятость в компании.

В первый день Том получает следующий алгоритм для реализации.

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

Том чувствует, что задача очень сложная, и он думает, что ему было бы полезно изучить абстрактную структуру программы, представив ее в виде блок-схемы. После рисования следующей диаграммыБлок-схема первого дня он быстро понимает, что его попросили вычислить абсолютное значение x, и он может реализовать его с помощью простого оператора if-then-else. Том очень счастлив, и он заканчивает свою задачу к концу дня.

На второй день Том получает следующий алгоритм для реализации.

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

Том, будучи новичком, снова чувствует, что было бы лучше понять алгоритм абстрактно, поэтому он рисует следующую схемуБлок-схема второго дня.

Изучение блок-схемы показывает, что Тому было предложено реализовать цикл while, который ожидает первого неотрицательного ввода. Том очень счастлив и заканчивает свою работу к концу дня.

Основываясь на его выдающейся работе, Том был нанят в компанию.

На третий день, однако, Том оказывается в глубоком конце, поскольку он получает алгоритм из 1000 строк с 1996 года.goto прыжки, разработанные бывшим сотрудником компании, и больше не осталось никого, кто бы знал, что делает алгоритм, как он работает и почему он был спроектирован таким образом. Однако это не касается Тома, так как его единственной задачей является реализация алгоритма независимо от того, чем он является. Вооружившись опытом двух предыдущих дней, он рисует потоковый график на 1000 узлов с направленными ребрами 1997 года. Том, будучи очень отчаявшимся, спрашивает на stackoverflow, что, черт возьми, делать с таким беспорядком, когда опытные программисты неоднократно советуют ему

разбить программу на более мелкие части; а такжеон заверил, что в некоторых случаях это действительно нормально использоватьgoto; а такжеему говорят «реструктурировать» программу.

Том, будучи очень прилежным, рассматривает эти советы, и его идея заключается в следующем:

он понимает, что если у связного компонента потокового графа есть ровно одна ступень и ровно одна ступень, то это можно рассматривать как «подалгоритм», который может быть разработан независимо, поэтому он может разбить свою задачу таким образом. Он, однако, не имеет ни малейшего представления о том, как найти такие компоненты и существуют ли другие разумные способы дальнейшего решения проблемы.Тому действительно все равноgoto хорошая или плохая практика программирования (см.GOTO все еще считается вредным?), его беспокоит то, что в его компании есть определенные руководящие принципы программирования, которым он должен следовать в любое время.Том действительно может коснуться алгоритма в том смысле, что он может заменить некоторые инструкции, которые приводят к эквивалентному алгоритму по его собственному усмотрению. Том, однако, не знает, какая часть программы требует реструктуризации, и, что более важно, он не понимает, почему реструктуризация необходима. Том нервно смотрит на свой 1000-вершинный граф и не знает, с чего начать.Вопросы относительно этого (отредактированного) сообщения следующие:

Можете ли вы помочь Тому выяснить, как начать реализацию чего-то, что не является «двухстрочным-очевидным»? В частности, ясно ли, что в каком порядке следует реализовывать задачи, описанные узлами блок-схемы? Понятно ли, что в каком порядке должны появляться определенные вложенные циклы один за другим?

Каковы самые маленькие «атомы» блок-схемы, которые не могут быть далее разбиты на более мелкие части? То есть, когда Том может с уверенностью ответить на стековый поток, что «я уже разбил свой алгоритм на более мелкие части»? Правда ли, что все по сути является циклом while и / или бинарной точкой ветвления (задачи первого и второго дней)?

Как реализовать такой «атом» автоматически, более или менее так же, как Том делал это уже в первый и второй дни?

Может ли Том спорить с генеральным директором, что с помощьюgoto в определенных случаях имеет важное значение, то есть, либо они используют его для реализации определенного алгоритма, либо нет абсолютно никакого другого способа реализовать его в соответствии с руководящими принципами компании (то есть без использованияgoto)?

Какие части потокового графа являются проблематичными и требуют реструктуризации и почему? Например, трехсторонняя ветвь может быть заменена вложенной двусторонней инструкцией if-then-else, то есть Том может смело предположить, что каждый узел в его блок-схеме имеет степень не более двух. Но какие еще реструктуризации нужно сделать, чтобы справиться со всеми вложенными циклами, вызваннымиgoto заявления? Какое графическое свойство делает реструктуризацию необходимой? Возможно, высшее образование?

Какова математическая (графическая) теория, лежащая в основе блок-схемы первоначально предложенного алгоритма (командой разработчиков программного обеспечения), и реструктурированной и разбитой блок-схемы алгоритмов алгоритма (ов), который (скажем Том) на самом деле больше -или менееавтоматически инвентарь?

ОРИГИНАЛЬНЫЙ ВОПРОС

Предположим, что у меня есть некоторый алгоритм, который использует двоичные решения и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

Вы поняли идею. Например, Кнут описывает алгоритмы в своих книгах таким независимым от языка программирования способом высокого уровня.

Теперь вопрос в том, как преобразовать такое высокоуровневое описаниеgoto операторы в реальной реализации с циклами while и if / else операторами? Можно ли полностью устранить всеgoto заявления, и заменить их циклом while? Если так, то как это сделать?в общем?

На основе описания алгоритма можно построить соответствующую блок-схему и, следовательно, (направленный) блок-график. Таким образом, вопрос другими словами: «Как реализовать код на основе его блок-схемы безgoto заявленияв общем?».

Есть два способа ответить на этот вопрос. Желательно и весьма надеюсь, что я ищу алгоритмический способ реализации ALGORITHM WHATEVER. Если ALGORITHM WHATEVERочень просто, тогда интуитивно понятно, что нужно делать, но мне кажется, что все усложняется после частого посещения шага (там прыгает много операторов goto), или, другими словами, когда один из узлов График потока имеет большую степень. Тогда я не совсем понимаю, в каком конкретном порядке должны быть вложены циклы while. С другой стороны, вполне возможно, что кто-то просто не может делать то, что я хочу в целом, и такой ответ должен быть подкреплен высокоуровневым описанием ALGORITHM IMPOSSIBLE, которое ясно демонстрирует, что, несмотря ни на что, человек просто не может избегать использованияgoto скачки в реальной реализации.

Мне кажется, что преобразование реализации в блок-схемы было задано несколько раз:Инструмент автоматической блок-схемы и здесьАлгоритм создания блок-схемы [Небольшое руководство ??], Программаcode2flow кажется хорошей отправной точкой для визуализации кода.

Однако здесь меня интересует другое направление. Простой поиск показал, чтоДРАКОН (смотрите такжеhttps://en.wikipedia.org/wiki/DRAKON а такжеhttp://drakon-editor.sourceforge.net/) может делать именно то, о чем я спрашиваю. С этой точки зрения вопрос заключается в том, как такая автоматическая программа, работающая с блок-схемами, может работать при допущении, что она не используетgoto заявление?