Создание булевой функции, которая определяет, эквивалентны ли два массива сдвигу
Два массива:
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} а также array2 = {3 1 2} проверить эквивалентность смены. Они должны быть, но моя программа говорит, что нет.
Решение
Одна проблема, которую я вижу в вашем коде, заключается в том, что вы обращаетесь к памяти за пределами массива. Если вы добавляете два индекса, вы должны убедиться, что они «оборачиваются», если вы хотите обрабатывать свой массив циклически. Это можно сделать по модулю. Вместо
a[i + j]
ты должен написать
a[(i + j) % size]
Я бы разбил ваш алгоритм на две части: во-первых, напишите функцию, которая проверяет, a равняется b со смещением shift, Затем, во второй функции (финал equivalent функция), проверьте все возможные значения для 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;
}
Если вы присмотритесь, вы не увидите никакой локальной переменной для хранения (сохранения) значения, если массивы эквивалентны. Действительно, у вашего кода тоже есть проблема, поскольку вы всегда перезаписываете старый статус новым для каждой сравниваемой записи. Поэтому, если во время сканирования массивов где-либо происходит сбой, но последняя запись сравнивается с равной, вы возвращаете «да, они равны», так как вы перезаписали статус.
Теперь посмотри на мой equivalent реализация. Я сканирую на разные смещения (shift) если массивы сравниваются равными. Давайте сосредоточимся на этой функции, а не на том, как выполняется сравнение в другой функции. Дело в том, что мы должны вернуть истину, если для любой сдвиг они сравнивают равными, не для последний один и не для все.
Идея решить эту проблему состоит в том, чтобы разорвать петлю (остановить), если вы нашли решение. Вы даже можете вернуть всю функцию, так как вы знаете полное возвращаемое значение, а именно true,
Если для какого-либо возможного сдвига сравнение не имеет значения, мы не нашли никакого возможного сдвига, поэтому они не являются «эквивалентом сдвига».
Я использовал очень похожий подход для реализации сравнения двух массивов с фиксированным смещением (equivalentFixed). Можете ли вы объяснить, как это делается?
Другие решения
здесь вы получаете i+j>size
a[i]=a[i+j];
А здесь просто небольшая вариация, чтобы сделать целое только в одной функции: (это редкий случай, когда хорошо использовать переход к динозавру — выйти из внутреннего цикла, не вводя новые временные переменные)
#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;
}
РЕДАКТИРОВАТЬ: От: Язык программирования C ++. Третье издание. Бьярне Страуструп
6.3.4 Перейти к [expr.goto]
C ++ обладает печально известной возможностью:
goto identifier ;
identifier : statement
Эта программа имеет мало применений в общем программировании высокого уровня
…
Одно из немногих разумных применений
gotoв обычном коде это сломать
из вложенного цикла или оператора switch (abreakвырывается из
только внутренняя замкнутая петля или коммутационное устройство).Например:
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
}