4

以下のプログラムは、n×n行列の最初のすべてゼロの行を見つけることになっています。これは問題への正しいアプローチですか？Cまたは一般的な言語でのこのコードへの別の優れた構造化されたアプローチはありますか？私はgotoステートメントとそれらの適切な使用法/代替案についてもっと学ぼうとしています。助けてくれてありがとう！

int first_zero_row = -1; /* none */
int i, j;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        if (A[i][j]) goto next;
    }
    first_zero_row = i;
    break;
    next: ;
}
4

7 に答える 7

4

ループ内のコードを単純化するために、小さなヘルパー関数を使用するのはどうでしょうか。

bool is_zero_row(int* Row, int size)
{
    int j;

    for (j = 0; j < size; j++)
        if (Row[j] != 0)
            return false;

    return true;
}

その後

int first_zero_row = -1; /* none */
int i;
for (i = 0; i < n; i++) {
    if (is_zero_row(A[i], n))
    {
        first_zero_row = i;
        break;
    }
}
于 2012-12-02T09:01:13.683 に答える
4

場合によっては使用することに反対しているわけではありませんgotoが、これは次のように書き直すことができると思います。

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        if (A[i][j]) break;
    }
    if (j==n) { /* the row was all zeros */
        first_zero_row = i;
        break;
    }
}
于 2012-12-02T07:51:56.987 に答える
1

最初に: はい、あなたのアプローチは私には正しいように見えます。次のように書き換えることができます。

int first_zero_row = -1; /* none */
int i, j;
for (i = 0; i < n; i++) {
    int all_zeroes = 1;
    for (j = 0; j < n; j++) {
        if (A[i][j]) {
            all_zeroes = 0;
            break;
        }
    }
    if (all_zeroes) {
        first_zero_row = i;
        break;
    }
}

gotoしかし、実際にはバージョンよりも明確ではないと思います。ループ ラベルを提供する Perl のような言語では、次のようにすることができます。

my $first_zero_row = -1;  # none
ROW:
for my $i (0 .. $n-1) {
    for my $j (0 .. $n-1) {
        next ROW if $A[$i][$j];
    }
    $first_zero_row = $i;
    last ROW;
}
于 2012-12-02T07:57:55.500 に答える
1

あなたのコードは私にはかなり読みやすいように見えます。無差別な魔女狩りgotoはよくない。このテーマに関する興味深い考えについては、Donald E. Knuth のStructured Programming と go to Statementsを読んでください。

を使用した私のバージョンは goto、最大の効率と非常に読みやすいものです。

int i, j;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++)
        if (A[i][j]) goto not_this_row;
    goto row_found;
    not_this_row:
}
/* Not found case here */

row_found:
/* Found case, i is the first zero row. */
于 2012-12-02T09:45:47.960 に答える
0

最初の goto を使用して入れ子になったループから抜け出したので...まあ...今日は、これについて検討します。気分が悪くなったので、gotoが悪と見なされる理由を少し読みました。

Dijkstra (およびその他) が goto を悪と見なす理由は、各ブロックに事前条件と事後条件があるブロックでコードが構築されているためです。goto (または break) は、コード ブロックが次のブロックの有効な事後条件を前提条件として生成することを保証できないことを意味します (つまり、break/goto はコード ブロックの重要な部分をスキップする可能性があるため、「コードが正しいことを証明する」ことはできません)。

ただし、あなたの例で goto が問題ないと思う理由は、実際には完全に有効な事後条件 (first_zero_row = -1 ...つまり、「すべてゼロの行が見つかりません」) を設定していることです。したがって、ブロックが無効な事後条件状態になる可能性はありません。

ただし、読みやすさの問題は別のことです。Goto を使用すると、コードがかなり読みにくくなります。したがって、あなたの特定の例では、より良い選択肢があるかもしれません。

于 2013-07-29T14:22:29.787 に答える
0

として機能する 1 つの変数を使用できますflag。条件の場合if (A[i][j]) goto next;、フラグ値を ではなく他の値に変更しますgoto next。

そして、後でそのフラグ値をチェックして、他の操作を行います。これはnext、あなたのケースではラベルの後にあります。

int flag = 0;
for ( i = 0; i < n; i++ ) {
    for ( j = 0; j < n; j++ ) {
        if ( A[i][j] ){
            flag = 1;
            break;
        }
    }
    if( flag == 1 ){
        // do your stuff 
        continue;
    }
    if( flag == 0 ){
        first_zero_row = i;
        break;
    }

注 :gotoコードから削除するには、コード行の位置を調整する必要がある場合があります。

于 2012-12-02T07:45:40.287 に答える
-2

私の意見では、すべてGOTOは悪です。いずれにせよそれらが必要な場合は、「メソッドの抽出」リファクタリングを検討することをお勧めします。

「GOTO」を使用する必要があることは、メソッド (または関数) が複雑すぎて別の部分に分割する必要があることを示す非常に良い指標です。

たとえば、質問の例は次のようにリファクタリングできます (リファクタリングする必要があります)。

bool is_zero_row(int *row, int size){
    for(i = 0; i<size; ++i){
        if(row[i]) return false;
    }
    return true;
}

bool find_zero_row_in_array(int **A, int rows, int row_size){
    int i,j;
    for(i = 0; i < rows; ++i) {
        if(is_zero_row(A[i], row_size)) return true;
    }
    return false;
}

...
if(find_zero_row_in_array(A, n, n)){
    //Found
} else {
    //Not found
}
....

これはオリジナルよりもはるかに柔軟で読みやすいです。少なくとも、行と列の数が同じであると仮定するのではなく、異なる数の行と列を持つ任意の配列に対して機能する関数ができました。

于 2013-04-22T11:59:52.017 に答える