Попытка найти наименьшее число в двумерном массиве с помощью рекурсии

Question

Я пытаюсь найти наименьшее число в массиве 2D (указатель на указатель) с помощью рекурсии, пока вот код:

int smallest(int **arr, int row_size, int column_size)
{   
    if (row_size == 0 && column_size == 0)
    {
        return *(*(arr + 0) + 0);
    }

    row_size--;
    column_size--;

    if ((*(*(arr + 0) + 0)) < (*(*arr + row_size) + column_size))
    {
        return smallest(arr, row_size, column_size);
    }
    else
    {
        *(*(arr + 0) + 0) = *(*(arr + row_size) + column_size);
        return smallest(arr, row_size, column_size);
    }
}

Это работает, но имеет 2 недостатка:

1- Обрабатывает только квадратные массивы.

2- Обрабатывает только индексы с одинаковыми номерами строк и столбцов (например,1,1 2,2 и 3,3 и т. Д.)

Я пытаюсь также обрабатывать неквадратные массивы, но для этого потребуется уменьшать число строк и столбцов в разное время, я неуверен, как это сделать.Есть какие-нибудь подсказки?

Answer 1

Я не мог с собой поделать.Это реализация, которая разделит входной массив на четыре меньших массива и вызовет для них iself (если только они не имеют нулевого размера):

int smallest(int **arr, int row_begin, int row_end, int column_begin, int column_end)
{
    if (row_end - row_begin == 1 && column_end - column_begin == 1) return *(*(arr + row_begin) + column_begin);

    int row_mid = (row_begin + row_end) / 2;
    int column_mid = (column_begin + column_end) / 2;

    int minimum = smallest(arr, row_mid, row_end, column_mid, column_end);
    if (column_mid > column_begin) {
        int m = smallest(arr, row_mid, row_end, column_begin, column_mid);
        if (m < minimum) minimum = m;
    }
    if (row_mid > row_begin) {
        int m = smallest(arr, row_begin, row_mid, column_begin, column_end);
        if (m < minimum) minimum = m;
    }
    if (column_mid > column_begin && row_mid > row_begin) {
        int m = smallest(arr, row_begin, row_mid, column_begin, column_mid);
        if (m < minimum) minimum = m;
    }
    return minimum;
}

Назовите его так: cout << smalllest (test_array, 0,строки, 0, столбцы); </p>

Answer 2

Я бы сделал что-то вроде:

int smallest(int **arr, int row_size, int column_size)
{
if (row_size > 0 && column_size > 0)
{
int minRow = arr[0][0];

for (int j = 0; j < row_size; ++j)
{
const int *row = arr[j];
minRow = std::min(minRow, *std::min_element(row, row + column_size));
}
return minRow;
}
else return INT_MAX;
}

Answer 3

Скучающие профессионалы перебивают вводные задачи, том 3!Эта версия:

• Использует вторичную функцию для обхода каждой строки (это может быть запрещено правилами вопроса, но вы можете объединить их и включить, если в массиве указателей есть только одна строка)
• Работает с пустыми массивами (и возвращает максимальное значение int)
• Не использует индексную нотацию
• Является чисто рекурсивным

int smallest(int const * const array, int const length) {
    return length == 0
        ? std::numeric_limits<int>::max()
        : std::min(*array, smallest(array + 1, length - 1));
}

int smallest(int const * const * const array, int const rows, int const columns) {
    return rows == 0
        ? std::numeric_limits<int>::max()
        : std::min(
            smallest(*array, columns),             // Minimum from the current row
            smallest(array + 1, rows - 1, columns) // Minimum from the rest of the rows
        );
}

Смотрите его в прямом эфире на Колиру

Answer 4

не проверено, но я думаю, что это будет работать.

#include <algorithm>
#include <limits>

//call with row = row_size-1, column = column_size -1
int smallest(int **arr, int row, int column)
{
    if( row<0 || column<0 )return std::numeric_limits<int>::max();
    return std::min( {arr[row][column], smallest(arr,row-1,column), smallest(arr,row,column-1)} );
}

---

Рекурсия

Answer 5

Предполагаемые требования :

• Невозможно изменить сигнатуру функции (может быть проще, если это не так)
• Может иметь только одну функцию (то же самое)
• Должен быть чисто рекурсивным (то есть без циклов)
• Необходимо использовать разыменование указателя (*(arr + 1) вместо arr[1])

Процедура

• Выполняется только по первому ряду (настройка rows в 1)
• Пройдите через все другие строки (уменьшение rows)

Код

int smallest(int **arr, int rows, int columns)
{   
    // invalid input
    if (rows <= 0 || columns <= 0)
        return INT_MAX;

    // top-left element
    int m = **arr;

    // single row recursion
    if (rows == 1) {
        *arr++; // increment the temporary pointer from below
        return min(m, smallest(arr, 1, columns - 1));
    }

    // create a temporary pointer to the first row
    // and start recursion in this single row
    int* row = *arr;
    m = min(m, smallest(&row, 1, columns));

    // rest of array
    return min(m, smallest(arr + 1, rows, columns - 1));
}

---

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

int smallest(int **arr, int rows, int columns, int column_index = 0)
{   
    // invalid input
    if (rows <= 0 || column_index >= columns)
        return INT_MAX;

    // single row recursion
    if (rows == 1)
        return min(*(*arr + column_index),       // first element of row
                   smallest(arr, 1, columns - 1, 
                            column_index + 1));  // rest of row

    // rest of array
    return min(smallest(arr, 1, columns),        // start on first row
               smallest(arr + 1, rows - 1, columns));
}

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

Answer 6

Вам нужно будет передать границы матрицы функции, чтобы вы могли «двигаться» в одном измерении, когда достигнете конца другого.

Примерно так (мне кажется более естественным считать вверх, чем вниз):

int smallest(int **arr, int row, int column, int row_last, int column_last)
{   
    if (row == row_last && column == column_last)
    {
        return arr[row][column];
    }
    else if (column == column_last)
    {
        return min(arr[row][column], smallest(arr, row+1, 0, row_last, column_last));
    }
    else
    {
        return min(arr[row][column], smallest(arr, row, column+1, row_last, column_last));
    }
}

(Это одно из тех упражнений, которое вводит потенциально полезные понятия в ситуации, когда они нене служит какой-либо цели. Неправильно использовать рекурсию или арифметику указателей.)

Answer 7

Хотя вы можете уйти без рекурсии, если это чисто обучающее упражнение для рекурсии, вы можете попробовать DFS подход.Имейте точку входа, чтобы начать поиск (i,j), из каждой точки исчерпайте все возможные области, которые вы могли бы пройти, (i+1,j)(i-1,j)(i,j+1)(i,j-1).Каждый шаг рекурсии также проверяет, находитесь ли вы в пределах массива, который будет i < 0 || i >= rows || j < 0 || j >= cols || visited[i][j], который вы просто вернете в этот момент.

Обратите внимание на массив visited.Таким образом, в каждой точке рекурсии может быть шанс, что вы вернетесь обратно в ту же ячейку, верно?это сделало бы бесконечное возвращение, чтобы избежать этого, вы отслеживаете, какие ячейки вы уже посетили, visited[i][j].Отметьте их.Каждый вызов recrusion отслеживает минимальный элемент, записанный по ссылке, который будет вашим минимальным элементом.

void findMinElement(vector<vector<int>>& array, int& minelement, int i, int j, vector<vector<bool>>& visited)
{
    if(i < 0 || i >= array.size() || j < 0 || j >= array[0].size() || visited[i][j]) return;

    minelement = min(minelement,array[i][j]); // is this the best minimum?

    visited[i][j] = true; // done visiting this cell

    //lets visits others
    findMinElement(array, minelement, i+1, j, visited);
    findMinElement(array, minelement, i-1, j, visited);
    findMinElement(array, minelement, i, j+1, visited);
    findMinElement(array, minelement, i, j-1, visited);
}

int main()
{
    vector<vector<int>> array =
    {
        {9,8,6,4},
        {13,4,6,11},
        {3,8,3,100}
    };

    int minElement = INT32_MAX;
    //same dimensions as array
    vector<vector<bool>> visited(array.size(), vector<bool>(array[0].size(),false));
    //start from (0,0)
    findMinElement(array,minElement,0,0,visited);
    cout << minElement;
}

Теперь это дает вам возможность начать поиск также из любого места в массиве.Это может быть немного, но это поможет вам решить многие проблемы в дальнейшем.