1

2つのアレイ：

a[] = {1 2 3 4}
b[] = {3 4 1 2}

一番下の配列は、単に一番上の配列を右に2か所シフトしたものです。上の配列を右シフトして下の配列を作成できる場合は、それらをシフト等価と呼びます。

2つの配列が「シフト等価」であるかどうかを判断するための関数（ブール関数を使用する必要があります）を作成する試みは次のとおりです。

#include <iostream>
using namespace std;

bool equivalent(int a[], int b[], int size) {

    int value; // if 1 returns as truth
    int k; // counter to compare both arrays

    for (int j = 0; j <= size; j++) {
        for (int i = 0; i <= size; i++) {
            a[i] = a[i + j];
        }
    }

    for (k = 0; k <= size; k++) {
        if (a[k] != b[k]) {
            value = 0;
        } else value = 1;
    }

    return (value == 1);
}

int main() {
    int n;
    cout << "Please input a size " << endl;
    cin >> n;

    int *mtrx = new int[n];
    int *mtrx1 = new int[n];
    int x;
    for (x = 0; x < n; x++) {
        cout << "Please make entries for the first array: " << endl;
        cin >> mtrx[x];
    }
    x = 0;
    for (x = 0; x < n; x++) {
        cout << "Please make entries for the 2nd array: " << endl;
        cin >> mtrx1[x];
    }

    bool answr = equivalent(mtrx, mtrx1, n = n - 1);

    if (answr) {
        cout << "They are shift equivalent." << endl;
    } else {
        cout << "They are not shift equivalent." << endl;
    }

    delete[] mtrx;
    delete[] mtrx1;

    system("PAUSE");
    return 0;
}

プログラムを実行するときは、シフトの同等性をテストするためにarray1 = {1 2 3}とを使用します。array2 = {3 1 2}彼らはそうなるはずですが、私のプログラムはそうではないと言っています。

4

2 に答える 2

4

私があなたのコードで見ている問題の1つは、配列を超えてメモリにアクセスすることです。2つのインデックスを追加する場合、配列を循環的に処理する場合は、それらが「ラップアラウンド」することを確認する必要があります。これは、モジュロを使用して実行できます。それ以外の

a[i + j]

あなたは書くべきです

a[(i + j) % size]

アルゴリズムを2つの部分に分割します。最初に、シフトが。とa等しいかどうかをテストする関数を記述します。次に、2番目の関数（最後の関数）内で、のすべての可能な値をテストします。bshiftequivalentshift

bool equivalentFixed(int a[], int b[], int size, int shift) {
    for (int i = 0; i < size; ++i) {
        if (a[i] != a[(i + shift) % size])
            return false;
    }
    return true;
}

bool equivalent(int a[], int b[], int size) {
    for (int shift = 0; shift < size; ++shift) {
        if (equivalentFixed(a, b, size, shift))
            return true;
    }
    return false;
}

よく見ると、配列が同等である場合、値を保持（格納）するローカル変数はありません。実際、ここでもコードに問題があります。これは、比較する単一のエントリごとに、常に古いステータスを新しいステータスで上書きするためです。したがって、配列のスキャン中にどこかで比較が失敗したが、最後のエントリが等しいと比較された場合、ステータスが上書きされているため、「はい、等しい」と返されます。

次に、私のequivalent実装を見てください。shift配列が等しい場合は、異なるオフセット（）をスキャンします。他の関数で比較が行われる方法ではなく、この関数に焦点を当てましょう。重要なのは、シフトが同じである場合、最後のシフトではなく、すべてのシフトではない場合、trueを返す必要があるということです。

これを解決するためのアイデアは、解決策を見つけた場合にループを中断（停止）することです。完全な戻り値、つまりを知っているので、関数全体を返すこともできますtrue。

可能なシフトがない場合、比較が真である場合、可能なシフトは見つからなかったため、「シフト相当」ではありません。

非常によく似たアプローチを使用して、固定シフト（equivalentFixed）を使用して2つの配列の比較を実装しました。これがどのように行われるか説明できますか？

于 2013-02-01T01:20:38.993 に答える
0

ここであなたは得るi+j>size

a[i]=a[i+j];

そして、ここでは、全体を1つの関数だけにするためのほんの少しのバリエーションです:(これは、新しい時間変数を導入せずに、内部ループから抜け出すために、恐竜のgotoを使用するのが良い場合のまれなケースです）

#include <iostream>
using namespace std;

bool equivalent(int a[], int b[], int size) 
{
    for (int j = 0; j < size; j++) 
    {
        for (int i = 0; i < size; i++) 
        {
            if (a[i] != b[(i + j)%size]) goto next_shift;
        }
        return true;
        next_shift: ;
    }
    return false;
}

int main() {
    int n;
    cout << "Please input a size " << endl;
    cin >> n;

    int *mtrx = new int[n];
    int *mtrx1 = new int[n];
    int x;
    for (x = 0; x < n; x++) {
        cout << "Please make entries for the first array: " << endl;
        cin >> mtrx[x];
    }
    x = 0;
    for (x = 0; x < n; x++) {
        cout << "Please make entries for the 2nd array: " << endl;
        cin >> mtrx1[x];
    }

    bool answr = equivalent(mtrx, mtrx1, n );

    if (answr) {
        cout << "They are shift equivalent." << endl;
    } else {
        cout << "They are not shift equivalent." << endl;
    }

    delete[] mtrx;
    delete[] mtrx1;

    system("PAUSE");
    return 0;
}

編集： From：C++プログラミング言語。第3版。ビャーネ・ストロヴルプ

6.3.4 Goto [expr.goto] C ++には悪名高いgotoがあります：

goto identifier ;
identifier : statement

gotoは、一般的な高レベルのプログラミングではほとんど使用されません

…</p>

通常のコードでのいくつかの賢明な使用法の1つはgoto、ネストされたループまたはswitchステートメントから抜け出すことです（break最も内側の囲んでいるループまたはswitchステートメントからのみ抜け出します）。

例えば：

voidf ()
{
int i ;
int j ;
for (i = 0 ; i <n ; i ++)
for (j = 0 ; j <m ; j ++) i f (nm [i ][j ] == a ) goto found ;
// not found
// ...
found :
// nm[i][j] == a
}
于 2013-02-01T01:20:10.300 に答える