Como transformar um fluxograma em uma implementação? [fechadas]

EDIT: INTRODUÇÃO

Para alcançar um público mais amplo, reformulei minha pergunta original por meio de um exemplo da vida real elaborado (e um tanto tedioso). A pergunta original é mostrada (distante) abaixo.

Tom acaba de ser contratado (dependendo de seu desempenho durante os dois primeiros dias úteis) para a Acme Inc. como engenheiro de software júnior. Seu trabalho é implementar algoritmos projetados pelos desenvolvedores seniores de software, na linguagem de programação Acme ++. A empresa segue um rigoroso "nãogoto"por ordem exclusiva do CEO. Caso Tom possa ter um desempenho excepcional no período de liberdade condicional, ele terá um emprego em tempo integral na empresa.

No dia 1, Tom recebe o seguinte algoritmo a ser implementado.

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 acha que a tarefa é muito complicada e acha que se beneficiaria do estudo da estrutura abstrata do programa, representando-a como um fluxograma. Depois de desenhar o diagrama a seguirFluxograma do primeiro dia ele rapidamente percebe que foi solicitado a calcular o valor absoluto de x, e ele pode implementá-lo com uma simples declaração if-then-else. Tom está muito feliz e termina sua tarefa no final do dia.

No dia 2, Tom recebe o seguinte algoritmo a ser implementado.

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, sendo um novato, sente que seria melhor entender o algoritmo de uma maneira abstrata, então ele desenha o seguinte fluxogramaFluxograma do segundo dia.

A inspeção do fluxograma revela que foi solicitado a Tom que implementasse um loop while que aguarda a primeira entrada não negativa. Tom está muito feliz e termina sua tarefa até o final do dia.

Com base em seu excelente desempenho, Tom foi contratado para a empresa.

No dia 3, no entanto, Tom está sendo jogado no fundo do poço, quando recebe um algoritmo de 1000 linhas em 1996goto saltos, projetados por um ex-funcionário da empresa, e não resta mais ninguém que saiba o que o algoritmo faz, como ele faz e por que foi projetado dessa maneira em primeiro lugar. No entanto, isso não preocupa Tom, pois sua única tarefa é implementar o algoritmo independentemente do que seja. Armado com os dois dias de experiência anteriores, ele desenha o gráfico de fluxo em 1000 nós com arestas direcionadas em 1997. Tom, estando muito desesperado, pergunta no stackoverflow o que diabos fazer com essa bagunça, onde programadores experientes o aconselham repetidamente a

dividir o programa em pedaços menores; eele ficou seguro de que, em certos casos, é realmente bom usargoto; eele é instruído a "reestruturar" o programa.

Tom, sendo muito diligente, considera esses conselhos, e sua ideia é a seguinte:

ele percebe que, se um componente conectado ao fluxograma tem exatamente um grau e exatamente um grau externo, isso pode ser considerado como um "sub-algoritmo" que pode ser desenvolvido independentemente, para que ele possa terminar sua tarefa desta maneira. Ele, no entanto, não tem idéia de como encontrar esses componentes em primeiro lugar, e se existem outras maneiras inteligentes de resolver o problema ainda mais.Tom realmente não se importa se está usandogoto é uma prática boa ou ruim de programação (consulteGOTO ainda considerado prejudicial?), ele se preocupa com o fato de haver certas diretrizes de programação em sua empresa que ele precisa seguir o tempo todo.Tom pode de fato tocar no algoritmo no sentido de poder substituir certas instruções que levam a um algoritmo equivalente a seu próprio critério. Tom, no entanto, não tem idéia de qual parte do programa requer reestruturação e, mais importante, ele não entende por que a reestruturação é necessária. Tom olha nervoso para o gráfico de 1000 vértices e realmente não sabe como começar a implementá-lo.As perguntas sobre este post (editado) são as seguintes:

Você pode ajudar Tom a descobrir como começar a implementar algo que não é "óbvio em duas linhas"? Em particular, está claro que em que ordem se deve implementar as tarefas descritas pelos nós do fluxograma? Está claro que em que ordem deve ocorrer certos loops aninhados um após o outro?

Quais são os "átomos" mais pequenos do fluxograma que não podem mais ser divididos em pedaços menores? Ou seja, quando Tom pode responder com confiança ao stackoverflow que "Já dividi meu algoritmo em partes menores"? É verdade que tudo é essencialmente um loop while e / ou um ponto de ramificação binário (as tarefas dos dias um e dois)?

Como implementar esse "átomo" automaticamente, mais ou menos da mesma maneira que Tom nos dias um e dois já?

Tom pode argumentar com o CEO que usargoto em certos casos, é essencial, ou seja, eles o utilizam para implementar determinado algoritmo ou não há outra maneira de implementá-lo de acordo com as diretrizes da empresa (ou seja, sem o uso degoto)?

Que partes do fluxograma são problemáticas e requerem reestruturação, e por quê? Por exemplo, uma ramificação de três vias poderia ser substituída por uma declaração de duas vias aninhadas se-então-outra, ou seja, Tom poderia assumir com segurança que cada nó em seu fluxograma possui grau no máximo dois. Mas que outras reestruturações devem ser feitas para lidar com todos os loops aninhados causados pelogoto afirmações? Que propriedade gráfica requer a reestruturação? Talvez alto grau?

Qual é a teoria matemática (gráfico) por trás do fluxograma de um algoritmo proposto originalmente (pela equipe de desenvolvimento de software) e o fluxograma reestruturado e dividido dos algoritmos que um (digamos Tom) realmente mais -ou menosautomaticamente implementa?

PERGUNTA ORIGINAL

Suponha que eu tenha algum algoritmo que use decisões binárias egoto afirmações. O algoritmo é descrito em N> = 2 etapas (finitas) da seguinte maneira de alto nível, e deve ser executado sequencialmente (uma etapa após a outra):

ALGORITMO O QUE QUER

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

Você entendeu a ideia. Por exemplo, Knuth descreve os algoritmos em seus livros de maneira independente e de alto nível, na linguagem de programação.

A questão agora é como transformar uma descrição de alto nível comgoto em uma implementação real com loops while e instruções if / else? É possível eliminar completamente todos osgoto e substituí-las por um loop while? Se sim, como fazer issoem geral?

Com base na descrição do algoritmo, é possível construir o fluxograma correspondente e, portanto, o fluxograma (direcionado). Portanto, a pergunta em outras palavras é "Como implementar um código com base em seu fluxograma semgoto afirmaçõesem geral? "

Existem duas maneiras de responder a essa pergunta. De preferência, e com sorte, estou procurando uma maneira algorítmica de implementar o ALGORITHM WHATEVER. Se ALGORITHM WHATEVER estivermuito simples, fica intuitivamente claro o que se deve fazer, mas parece-me que as coisas ficam bastante complicadas quando uma etapa é visitada com frequência (há muitas declarações goto pulando por lá) ou, em outras palavras, quando um dos nós da o gráfico de fluxo possui um grande grau. Então não vejo exatamente em que ordem específica os loops while devem ser aninhados. Por outro lado, é bem possível que alguém simplesmente não possa fazer o que eu quero em geral, e essa resposta deve ser apoiada por uma descrição de alto nível do ALGORITHM IMPOSSIBLE, que demonstra claramente que, não importa o que, simplesmente não é possível Evite usargoto salta em uma implementação real.

Parece-me que a transformação da implementação em fluxogramas foi solicitada várias vezes:Ferramenta de fluxograma automático e aquiAlgoritmo para criar fluxograma [Um pouco de orientação?]. O programacode2flow parece ser um bom ponto de partida para visualizar um código.

No entanto, aqui estou interessado na outra direção. Uma simples pesquisa revelou queDRAKON (Veja tambémhttps://en.wikipedia.org/wiki/DRAKON ehttp://drakon-editor.sourceforge.net/) pode estar fazendo exatamente o que estou perguntando. Nessa perspectiva, a questão é: como um programa automático de fluxograma para código funciona com a suposição extra de que ele não usa ogoto declaração?