Рекурсивная функция, которая принимает две матрицы одинакового размера и выводит, равны ли они

Question

Я пытаюсь написать рекурсивную функцию, которая принимает 2 матрицы одинакового размера и возвращает 1, если они равны, и 0 в противном случае.

int equal(int[][3], int[][3], int, int);
int main()
{
    int matrixOne[3][3] = { { 1, 2, 8 }, { 3, 4, 9 }, { 3, 3, 3 } };
    int matrixTwo[3][3] = { { 1, 2, 8 }, { 3, 4, 9 }, { 3, 3, 3} };
    cout << equal(matrixOne, matrixTwo, 2, 2);
    system("pause");
    return 0;
}
int equal(int matrixOne[][3], int matrixTwo[][3], int row, int column)
{
    if (row < 0)
        return 1;
    if (column < 0)
    {
        column = row;
        row--;
    }
    if (matrixOne[row][column] == matrixTwo[row][column])
        return equal(matrixOne, matrixTwo, row, column - 1);
    else
    {
        return 0;
    }
}

Это не работает так, как должно, потому что один столбецcount достигает нуля, мы должны сбросить его до первоначального максимального столбца count, это можно сделать в первый раз, сделав column = row;но после этого он просто не пересекает всю матрицу.

Возможно ли даже решить этот вопрос, используя этот прототип функции?

Answer 1

Вы можете легко сделать универсальную версию, которая позволяет матрицы с любым количеством измерений любого размера любого типа.Вы можете сделать размер массива параметром шаблона, чтобы вам не приходилось его передавать.

#include <type_traits>
#include <cstddef>

template<class T, std::size_t N>
typename std::enable_if<!std::is_array<T>::value, bool>::type
equal(T (&a)[N], T (&b)[N]) {
    for (std::size_t i = 0; i < N; ++i) {
        // T is not an array, (a is a single dimension array)
        // so just compare the values.
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

template<class T, std::size_t N>
typename std::enable_if<std::is_array<T>::value, bool>::type
equal(T (&a)[N], T (&b)[N]) {
    for (std::size_t i = 0; i < N; ++i) {
        // T is an array (So a is a multidimensional array)
        // recursively call the "equal" function on the
        // lower dimensional arrays.
        if (!equal(a[i], b[i])) {
            return false;
        }
    }
    return true;
}

Например:

#include <iostream>

int main() {
    // Modified the size so you can see it better
    int matrixOne[2][3] = { { 1, 2, 8 }, { 3, 4, 9 } };
    int matrixTwo[2][3] = { { 1, 2, 8 }, { 3, 4, 9 } };

    /*
    equal(matrixOne, matrixTwo)
    // bool equal<int[3], 2> equal(int[3][2], int[3][2]);
        is equivalent to:
    equal(matrixOne[0], matrixTwo[0]) && equal(matrixOne[1], matrixTwo[1])
    // bool equal<int, 3> equal(int[3], int[3]);
        And they just compare the 3 values per column
    */

    // prints 1
    std::cout << equal(matrixOne, matrixTwo) << '\n';
}

Но, поскольку функциипросто многомерный массив "int", вы можете просто std::memcmp.

#include <type_traits>
#include <cstddef>
#include <cstring>

// Change the above to
template<class T, std::size_t N>
typename std::enable_if<
    !std::is_array<T>::value && !std::is_trivially_copyable<T>::value, bool
>::type
equal(T (&a)[N], T (&b)[N]);

template<class T, std::size_t N>
typename std::enable_if<
    std::is_array<T>::value && !std::is_trivially_copyable<T>::value, bool
>::type
equal(T (&a)[N], T (&b)[N]);

// And the new one for trivial types
template<class T, std::size_t N>
typename std::enable_if<std::is_trivially_copyable<T>::value, bool>::type
equal(T (&a)[N], T (&b)[N]) noexcept {
    return std::memcmp(a, b, sizeof(a)) == 0;
}

Answer 2

Ваша функция будет работать, но я должен был внести некоторые изменения:

1. Замена column = row на column = 2. Обратите внимание, что в параметрах функции в предоставленном коде матрицы были объявлены как matrixOne[][3]. Поскольку 3 находится во втором измерении, мне пришлось присвоить 2 столбцу. Чтобы сделать функцию общей, вам придется изменить свой код.

2. Установка чека для row < 0 после проверки столбца. Вы можете выяснить причину этого после некоторой отладки; если этого не сделать, рекурсия не остановится в ожидаемой точке.

Вот модифицированный код:

int equal(int[][3], int[][3], int, int);
int main()
{
    int matrixOne[3][3] = { { 1, 2, 8 }, { 3, 4, 9 }, { 3, 3, 3 } };
    int matrixTwo[3][3] = { { 1, 2, 8 }, { 3, 4, 9 }, { 3, 3, 3} };
    cout << equal(matrixOne, matrixTwo, 2, 2);
    system("pause");
    return 0;
}
int equal(int matrixOne[][3], int matrixTwo[][3], int row, int column)
{
    if (column < 0)
    {
        column = 2;
        row--;
    }
    if (row < 0)
        return 1;
    if (matrixOne[row][column] == matrixTwo[row][column])
        return equal(matrixOne, matrixTwo, row, column - 1);
    else
    {
        return 0;
    }
}

Вот ссылка, по которой я тестировал код: https://ideone.com/4tBpJg