c++ - 不使用 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;
}

这个程序是教授发布的提示，供类(class)使用。

 #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 以通过直线执行到达标签的执行来查看控制流。

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

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

backtrack:
    if (…) return;
    goto NR;

print:
    goto backtrack;

现在，使用无条件 goto 并尝试移动 block ，使它们代表直线执行。

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

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

print:
    goto backtrack;

backtrack:
    if (…) return;
    goto NR;

现在消除直线gotos

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; 只是退出它，所以将那个 block 和条件移到循环中。

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

看起来不错，没有更多的 goto，也没有“可疑”的结构!但是，NC 应该是入口点。

这就是盲目的、机械的、类似编译器的转换失败的地方。我看到三种选择:

1. 引入变量以强制执行第一个循环迭代。在我看来，这比 goto 更难看。
2. 将 goto NC; 伪装成 switch(0) 并调用标签 NC: 作为 case 0:。老师可能不会接受这种妥协。
3. 将 block 从 NC 复制到循环的末尾并粘贴到循环开头的上方。然后，您可以将它们分解为函数。实际上，这是一种盲目的、机械的改造。万岁。我还将 NR 和 backtrack 表示为统一函数。

.

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

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

可能有一个更优雅的解决方案，涉及查看代码的内容，但这需要更少的思考。