Переписать программу без использования операторов goto

Question

Мне пришлось запрограммировать подобную проблему с помощью операторов goto. Теперь нас просят переписать наш код без использования оператора goto. Я не знаю, как начать делать эту программу. Я вставляю в предыдущий код программы, используя goto.

// Eight Queens problem using one dimesional array and goto statement

#include "stdafx.h"
#include <iostream>
using namespace std;


int main()
{
    int q[8];
    q[0] = 0;
    int c = 0;
    int count = 0;

NC: //cout  << "Next column\n" << "Column = " << c << endl;
    c++;
    if (c == 8) goto print;
    q[c] = -1;

NR: //cout << "Next row\n" << "Row = " << q[c] << "\nColumn = " << c << endl;
    q[c]++;
    if (q[c] == 8) goto backtrack; 
    for(int i = 0; i < c; i++){
        if(q[i] == q[c] || abs(q[c] - q[i]) == (c - i))
            goto NR;
    }
    goto NC;

backtrack:
    //cout << "Backtrack" << endl;
    //cout <<"Column = " << c << endl;
    c--;
    if(c == -1) return 0;
    goto NR;

print:
    //cout << "print" << endl;
    ++count;
    cout << count << endl;
    for(int i = 0; i <= 7; i++){
            cout << q[i];
    }
    cout << endl;
    goto backtrack;


    return 0;
}

Эта программа - подсказка, которую профессор написал для класса.

 #include <iostream>
    #include<cstdlib>
    #include <cmath>
    using namespace std;

    bool ok(int q[], int col){
    if the configuration is “bad” return false;
    else
    return true;
    }

    void backtrack(int &col){
    col--;
    if(col==-1) exit(1);
    }

    void print(int q[]){
    static int count =0;
    print the array q
    }

    int main(){
    int q[8]; q[0]=0;
    int c=1;
    // from_backtrack keeps track if we need to reset the row to the
    // top of the current colum or not.

    bool from_backtrack=false;
    // The outer loop keeps looking for solutions
    // The program terminates from function backtrack
    // when we are forced to backtack into column -1
    while(1){
    while(c<8){ //this loop goes across columns
    // if we just returned from backtrack, use current value of row
    // otherwise get ready to start at the top of this column
    if(!from_backtrack) // we did not just return from backtrack
    Code goes here
    from_backtrack=false;
    while(q[c]<8){ // place queen in this column
    q[c]++;
    // if row=8, there is no valid square in this column
    // so backtrack and continue the loop in the previous column
    Code goes here
    //if this position is ok, place the queen
    // and move on (break) to the next column,
    // otherwise keep looking in this column
    Code goes here
    }
    c++; // placed ok, move to the next column
    }
    // one complete solution found, print it.
    print(q); // board completed, print it out
    backtrack(c);
    from_backtrack=true;
    }
    }

И это попытка завершить программу

// NoGoto.cpp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;



bool attack(int q[], int col){
    if(q[i] == q[c] || abs(q[c] - q[i]) == (c - i)) return false;
    else
        return true;
} // Attack

void backtrack(int & col){
    col--;
    if(col == -1) exit(1);
} // Backtrack

void print(int q[]){
    static int count = 0;
    ++count;
    cout << count << endl;
    for(int i = 0; i < 8; i++)
        cout << q[i];
    cout << endl;
}
int main()
{
    int q[8];
    q[0] = 0;
    int c = 1;

    bool from_backtrack = false;

    while(1){
        while(c < 8){ // this loops across columns

            if(!from_backtrack)
                attack(q[c],c)

            from_backtrack = false;

            while(q[c] < 8){ // place queen in this column
                q[c]++;

    return 0;
}

«У меня проблемы с написанием кода. Как [можно] вызвать каждую функцию, чтобы она правильно находила решения?»

Answer 1

Во-первых, просто посмотрите на поток управления, убрав все остальное и добавив явные goto s для выполнения, которое достигает метки при прямом выполнении.

NC: if (…) goto print;
    goto NR;

NR: if (…) goto backtrack;
    if (…) goto NR;
    goto NC;

backtrack:
    if (…) return;
    goto NR;

print:
    goto backtrack;

Теперь возьмите безусловные переходы и попробуйте переместить блоки, чтобы они представляли прямолинейное выполнение.

NR: if (…) goto backtrack;
    if (…) goto NR;
    goto NC;

NC: if (…) goto print;
    goto NR;

print:
    goto backtrack;

backtrack:
    if (…) return;
    goto NR;

Теперь исключите прямолинейные переходы

NR: if (…) goto backtrack;
    if (…) goto NR;

NC: if (…) goto print;
    goto NR;

print:

backtrack:
    if (…) return;
    goto NR;

Обратите внимание, что метка со всеми обратными goto является циклом:

for (;;) {
NR: if (…) goto backtrack;
    if (…) continue;

NC: if (…) goto print;
    continue;

print:

backtrack:
    if (…) return;
}

Хм, мы можем изменить смысл NC: if() и устранить goto print. И goto backtrack просто перепрыгивает через некоторые утверждения, что эквивалентно другому перевернутому if.

for (;;) {
NR: if (! …) {
        if (…) continue;
NC:     if (! …) continue;
print:
    }
backtrack:
    if (…) return;
}

У цикла нет условия, но backtrack: … if(…) return; просто выходит из него, поэтому переместите этот блок и условие в цикл.

for (;…; /* backtrack */ …) {
NR: if (! …) {
        if (…) continue;
NC:     if (! …) continue;
print:
    }
}

Выглядит довольно хорошо, больше никаких gotos и никакой "подозрительной" структуры! Тем не менее, NC должен быть точкой входа.

Вот где слепые, механистические преобразования компилятора завершаются неудачей. Я вижу три альтернативы:

1. Ввести переменные для принудительного выполнения там для первой итерации цикла. На мой взгляд, это хуже, чем goto.
2. Маскировка goto NC; как switch(0) и вызов метки NC: как case 0:. Учитель, вероятно, не примет этот компромисс.
3. Скопируйте блоки из NC в конец цикла и вставьте над началом цикла. Затем вы можете выделить их в функции. На самом деле, это слепая, механистическая трансформация. Ура. Я также буду представлять NR и backtrack как функции для единообразия.

.

NC();
if (…) {
    print();
}

while ( backtrack(), … ) { // <- note comma operator
    NR();
    if (! …) {
        if (…) continue;
        NC();
        if (! …) continue;
        print();
    }
}

Вероятно, есть более элегантное решение, которое включает просмотр содержимого кода, но для этого нужно меньше думать.