1

两个数组：

a[] = {1 2 3 4}
b[] = {3 4 1 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}andarray2 = {3 1 2}来测试班次等价性。他们应该是，但我的程序说他们不是。

4

2 回答 2

4

One problem which I see in your code is that you access memory beyond the array. If you add two indices, you have to make sure that they "wrap around" if you want to treat your array cyclic. This can be done with a modulo. Instead of

a[i + j]

you should write

a[(i + j) % size]

I'd split your algorithm into two parts: First, write a function which tests if a equals b with a shift of shift. Then, within a second function (the final equivalent function), test for all possible values for shift.

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;
}

If you look close, you don't see any local variable to hold (store) the value if the arrays are equivalent. Indeed, your code has a problem here, too, since you always overwrite the old status with the new one for each single entry you compare. So if the comparison fails anywhere during scanning the arrays, but the very last entry compares to equal, you return "yes, they are equal", since you have overwritten the status.

Now have a look at my equivalent implementation. I scan for different offsets (shift) if the arrays compare equal. Let's focus on this function, not how the comparison is done in the other function. The point is: We have to return true if for any shift they compare equal, not for the last one and not for all.

The idea to solve this is to break the loop (stop) if you found a solution. You can even return the whole function, since you know the complete return value, namely true.

If for no possible shift the comparison is true, we didn't find any possible shift, so they aren't "shift equivalent".

I used a very similar approach to implement the comparison of two arrays with a fixed shift (equivalentFixed). Can you explain how this is done?

于 2013-02-01T01:20:38.993 回答
0

here you get i+j>size

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

And here just a litte variation to make the whole in only one function: (this is a rare case when it is good to use a dynosaur goto - to get out of an internal loop, whithout introducing new temporal variables)

#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;
}

EDIT: From:The C+ + Programming Language. Third Edition. Bjarne Stroustrup

6.3.4 Goto [expr.goto] C++ possesses the infamous g o t o :

goto identifier ;
identifier : statement

The g o t o has few uses in general highlevel programming

…</p>

One of the few sensible uses of goto in ordinary code is to break out from a nested loop or switch statement (a break breaks out of only the innermost enclosing loop or switchstatement).

For example:

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 回答