Отправлено: 29.09.14 22:42. Заголовок: Многомерные массивы в динамической памяти
Здравствуйте) Это опять я)
Было дано вот такое задание:
цитата:
Напишите функцию, которая принимает на вход прямоугольную матрицу размера 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
Я написал вот такой вот код:
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; //возврат нулевой строки на новое место, т.е. туда где раньше была строка с минимальным элементом } } }
Код рабочий, но почему-то стопарится на 11м тесте. Feedback: Wrong answer Тест кейсы - не известны. Посмотрите пожалуйста, мб я где-то что-то неучёл?
Отправлено: 30.09.14 01:09. Заголовок: Вы не нашли строку с..
Вы не нашли строку с минимальным элементом. Что вы делаете, так это следующее. Как только вы находите первый элемент, который меньше установленного вами минимального элемента, так вы сразу же переставляете строки. При этом цикл у вас продолжается. Поэтому при следующем нахождении элемента с меньшим значением вы снова переставляете строки.
Я бы посоветовал сначала написать функцию, которая ищет минимальный элемент в одномерном массиве. Такая функция есть и называется она std::min_element. Она объявлена в заголовке <algorithm>, но, как я понимаю, вам надо самостоятельно написать аналогичную функцию для целочисленных массивов.
Используя эту функцию, будет проще найти строку с минимальным элементом.
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; }
Эта реализация не эффективна, потому что для каждой строки минимум подсчитывается каждый раз, когда вызывается предикат.
Тем не менее вы можете использовать ее как шаблон и написать более эффективную функцию. Для этого, как я уже написал выше, вам нужно самостоятельно сначала написать функцию, аналогичную std::min_element для числового массива. Ее определение может выглядеть следующим образом:
const int * min_element( const int *a, size_t n );
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; }
Все, что вам осталось сделать самостоятельно, это написать функцию min_element в соответствии с тем определением, которое я указал в предыдущем сообщении, правильно вызывать ее из функции swap_min и заменить вызов std::iter_swap своим кодом, который выполняет перестановку указателей.
Фактически, алгоритм функции swap_min представляет собой алгоритм, который вы должны использовать в определении функции min_element. То есть логика работы функций одна и та же.
Все даты в формате GMT
3 час. Хитов сегодня: 3
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет
- участник сейчас на форуме
- участник вне форума