On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 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
Тест кейсы - не известны.
Посмотрите пожалуйста, мб я где-то что-то неучёл?

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 4 [только новые]





ссылка на сообщение  Отправлено: 30.09.14 01:09. Заголовок: Вы не нашли строку с..


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

Я бы посоветовал сначала написать функцию, которая ищет минимальный элемент
в одномерном массиве. Такая функция есть и называется она std::min_element.
Она объявлена в заголовке <algorithm>, но, как я понимаю, вам надо
самостоятельно написать аналогичную функцию для целочисленных массивов.

Используя эту функцию, будет проще найти строку с минимальным элементом.

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 30.09.14 01:45. Заголовок: Если использовать ст..


Если использовать стандартные алгоритмы, то функция может выглядеть следующим образом:

 
#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;
}


Эта реализация не эффективна, потому что для каждой строки минимум подсчитывается каждый раз,
когда вызывается предикат.

Тем не менее вы можете использовать ее как шаблон и написать более эффективную функцию.
Для этого, как я уже написал выше, вам нужно самостоятельно сначала написать функцию,
аналогичную std::min_element для числового массива. Ее определение может выглядеть
следующим образом:
 
const int * min_element( const int *a, size_t n );



Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 30.09.14 10:13. Заголовок: Вот как может выгляд..


Вот как может выглядеть ваша функция

 
#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;
}


Все, что вам осталось сделать самостоятельно, это написать функцию min_element
в соответствии с тем определением, которое я указал в предыдущем сообщении, правильно
вызывать ее из функции swap_min и заменить вызов std::iter_swap своим
кодом, который выполняет перестановку указателей.

Фактически, алгоритм функции swap_min представляет собой алгоритм,
который вы должны использовать в определении функции min_element.
То есть логика работы функций одна и та же.

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 30.09.14 14:04. Заголовок: Спасибо за советы) П..


Спасибо за советы) Помогло)

Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 31
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет