Форум » C/C++ для начинающих (C/C++ for beginners) » Многомерные массивы в динамической памяти » Ответить
Многомерные массивы в динамической памяти
evsign: Здравствуйте) Это опять я) Было дано вот такое задание: [quote]Напишите функцию, которая принимает на вход прямоугольную матрицу размера m на n (двумерный массив в динамической памяти из m строк и n столбцов), ищет строку содержащую минимальный элемент и меняет ее местами с первой строкой матрицы. При решении задачи вы можете заводить любые вспомогательные функции. Sample Input: 3 3 2 3 5 7 0 3 4 8 6 Sample Output: 7 0 3 2 3 5 4 8 6 [/quote] Я написал вот такой вот код: [pre2] void swap_min(int **mt, int m, int n) { int min = pow(2,sizeof(min)*8-1)-1; //переменная для хранения максимума int *a = 0; for(size_t i = 0; i < m; i++){ //перебор строк for(size_t j = 0;j < n; j++) //перебор столбцов if(mt[ i ][ j ] < min){ // Нахождение минимума min = mt[ i ][ j ]; a = mt[0]; //копирования адреса нулевой строки во временный указатель mt[0] = mt[ i ]; //установка нулевой строке адрес с строкой содержащей минимальный элемент mt[ i ] = a; //возврат нулевой строки на новое место, т.е. туда где раньше была строка с минимальным элементом } } } [/pre2] Код рабочий, но почему-то стопарится на 11м тесте. Feedback: Wrong answer Тест кейсы - не известны. Посмотрите пожалуйста, мб я где-то что-то неучёл?
Ответов - 4
Сыроежка: Вы не нашли строку с минимальным элементом. Что вы делаете, так это следующее. Как только вы находите первый элемент, который меньше установленного вами минимального элемента, так вы сразу же переставляете строки. При этом цикл у вас продолжается. Поэтому при следующем нахождении элемента с меньшим значением вы снова переставляете строки. Я бы посоветовал сначала написать функцию, которая ищет минимальный элемент в одномерном массиве. Такая функция есть и называется она std::min_element. Она объявлена в заголовке <algorithm>, но, как я понимаю, вам надо самостоятельно написать аналогичную функцию для целочисленных массивов. Используя эту функцию, будет проще найти строку с минимальным элементом.
Сыроежка: Если использовать стандартные алгоритмы, то функция может выглядеть следующим образом: [pre2] #include <iostream> #include <algorithm> #include <memory> void swap_min( int **a, size_t m, size_t n ) { auto binary_predicate = [=]( int *a, int *b) { return ( *std::min_element( a, a + n ) < *std::min_element( b, b + n ) ); }; auto min = std::min_element( a, a + m, binary_predicate ); if ( a != min ) std::iter_swap( a, min ); } int main() { const size_t M = 3; const size_t N = 3; int **a = new int *[M]; a[0] = new int[N] { 2, 3, 5 }; a[1] = new int[N] { 7, 0, 3 }; a[2] = new int[N] { 4, 8, 6 }; for ( size_t i = 0; i < M; i++ ) { for ( size_t j = 0; j < N; j++ ) std::cout << a[j] << ' '; std::cout << std::endl; } std::cout << std::endl; swap_min( a, M, N ); for ( size_t i = 0; i < M; i++ ) { for ( size_t j = 0; j < N; j++ ) std::cout << a[j] << ' '; std::cout << std::endl; } std::cout << std::endl; std::for_each( a, a + M, std::default_delete<int[]>() ); delete []a; return 0; } [/pre2] Эта реализация не эффективна, потому что для каждой строки минимум подсчитывается каждый раз, когда вызывается предикат. Тем не менее вы можете использовать ее как шаблон и написать более эффективную функцию. Для этого, как я уже написал выше, вам нужно самостоятельно сначала написать функцию, аналогичную std::min_element для числового массива. Ее определение может выглядеть следующим образом: [pre2] const int * min_element( const int *a, size_t n ); [/pre2]
Сыроежка: Вот как может выглядеть ваша функция [pre2] #include <iostream> #include <algorithm> #include <memory> void swap_min( int **a, size_t m, size_t n ) { if ( m == 0 || n == 0 ) return; int **min = a; int min_value = *std::min_element( *min, *min + n ); for ( int **current = a + 1; current != a + m; ++current ) { int current_value = *std::min_element( *current, *current + n ); if ( current_value < min_value ) { min_value = current_value; min = current; } } if ( a != min ) std::iter_swap( a, min ); } int main() { const size_t M = 3; const size_t N = 3; int **a = new int *[M]; a[0] = new int[N] { 2, 3, 5 }; a[1] = new int[N] { 7, 0, 3 }; a[2] = new int[N] { 4, 8, 6 }; for ( size_t i = 0; i < M; i++ ) { for ( size_t j = 0; j < N; j++ ) std::cout << a[j] << ' '; std::cout << std::endl; } std::cout << std::endl; swap_min( a, M, N ); for ( size_t i = 0; i < M; i++ ) { for ( size_t j = 0; j < N; j++ ) std::cout << a[j] << ' '; std::cout << std::endl; } std::cout << std::endl; std::for_each( a, a + M, std::default_delete<int[]>() ); delete []a; return 0; } [/pre2] Все, что вам осталось сделать самостоятельно, это написать функцию min_element в соответствии с тем определением, которое я указал в предыдущем сообщении, правильно вызывать ее из функции swap_min и заменить вызов std::iter_swap своим кодом, который выполняет перестановку указателей. Фактически, алгоритм функции swap_min представляет собой алгоритм, который вы должны использовать в определении функции min_element. То есть логика работы функций одна и та же.
evsign: Спасибо за советы) Помогло)
полная версия страницы