If you’re taking Jerry Waxman’s 211 course on C++, a required course for anyone majoring in Computer Science at Queens College-CUNY, the following is the second homework problem.

The problem here asks you to write out a function that will take two arrays of the same size and determine whether or not they are “shift equivalent,” which means if I moved one of the arrays a certain number of times clockwise, that array will transform into the first array. Does that make sense, if not leave a comment below.

For example, array b can be transformed into array a by shifting members of array b 2 positions to the right:

b: 3 – 4 – 5 – 1 – 2

b: 2 – 3 – 4 – 5 – 1

b: 1 – 2 – 3 – 4 – 5

Let’s get started on writing this program. Let’s get the basic stuff typed into our file.

#include <iostream>

using namespace std;

Next, I am going to type in the function prototype before introducing the main function.

#include <iostream>

using namespace std;

bool equivalent(int a[ ], int b[ ], int n);

int main( )

{

return 0;

}

Now, I am going to take the requirements of the function given to me in the problem description and translate them into code.

So, I’m going to be given two arrays and if one of the arrays can be *shifted* a certain amount of times to the right and becomes equivalent to the other, then the two arrays are “shift equivalent” arrays. Ok, the first thing I need to determine is to find the shift. To do this, I am going to pick one of the arrays and select the first element in the array, then, using a for loop, compare that element to the elements of array b until a[0] is equal to b[i]. When this is the case, we have found the shift.

// Going to need a variable to store the shift

int shift = 0;

// To process through the elements of an array, I’m going to need a for loop

// For the conditional i < n, n is the size of the array

for (int i = 0; i < n; i++) {

if (a[0] == b[i]) shift = i;

}

Now that we *think* we have the shift, we need to test it out. We need to apply the shift to the second array, b, and see if it is equivalent to the first array, a. I am also going to need a variable to hold the boolean true or false, which is why I am going to start out with initializing a variable called answer to false. Then, once again, to process through any array we will be needing a for loop. Now that we know of the shift, we won’t have to process i until it’s less than n, instead, our for loop will start at 0 and loop until i is less than n – shift. Why? Let’s think about that after the block of code.

bool answer = false;

for (int i = 0; i < n – shift; i++) {

if (a[i] == b[ i + shift ]) answer = true;

else return false;

}

The question now is, why is the array being processed until i is less than n – shift? Let’s use the example of array a and array b from earlier above. The shift was 3. Now let’s see what happens when we process that for loop:

= n – shift

= 5 – 3

= 2

a[i] == b[i+shift]

a[0] == b[0 + 3]

a[0] == b[3]

1 == 1

a[1] == b[1 + 3]

a[1] == b[4]

2 == 2

a[2] == b[2 + 3]

a[2] == b[5]

3 =? b[5]?

b[5] doesn’t exit in this array

Arrays in C++ are zero-based indexed. This means the first element is accessed in the 0th position, not in the 1st position. With that in mind it makes sense why the conditional in our for loop has to be i < n – shift, because that will be where our second array’s index will fall off. This situation requires us to include a second test for our function:

for (int j = n – shift; j < n; j++) {

if ( a[j] == b[ (j+shift) % n] ) answer = true;

else return false;

}

return answer;

In this second test, I am using the modulo operator. This modulo operator works to move the last element of the array to the first element, moving it clockwise to the other side. It’s sort of like in Pac Man, when you went through a gate on the right side of the screen, you reappeared on the left side of the screen.

Another thing to recognize is that I am initializing j as equal to (n – shift), so that we can cycle through all five positions of the array. On top of that, we make up for the subtraction by adding the j to the b array shift value.

Finally, since we passed our arguments through two levels of testing, we can finally send back an answer to the function call from the main function. Speaking of main, lets code that up now:

int main( ){

// Going to need two arrays of size 5

int a[5], b[5];

// Let’s nicely ask the user to give us five integers

cout << “Yo, enter five integers: “;

// Going to need for loops to plug the inputs into the array

for (int i = 0; i < 5; i++) cin >> a[i];

// Ask for another 5

cout << “5 mo: “;

// Another for loop:

for(int i = 0; i < 5; i++) cin >> b[i];

// Flush the iostream buffer with an endl

cout << endl;

// Now let’s initialize a variable to hold the boolean value

// from function call to equivalent

bool answer = equivalent(a, b, 5);

// If answer == true, then the shift equivalent exists!

// Else, none

if ( answer == true ) cout << “Shift Equivalent!” << endl;

else cout << “Nope, not equivalent.” << endl;

return 0;

}

Did all of that make sense? Try it out on your computer and let me know if it works.

If the code doesn’t work, leave a comment below detailing where the code failed. Or, if you have suggestions on how to make this program more efficient, let me know kindly in a comment below.

### Like this:

Like Loading...