(C) Получение 3 минимальных элементов строки в матрице и выбор одного из них случайным образом

У меня есть матрица 8x8, и после выбора нужной строки я хочу получить три минимальных ее элемента и выбрать один из этих трех случайным образом. Дело в том, что я не знаю, как обращаться с этими тремя элементами. Я просто знаю, как получить минимальный элемент, то есть следующий код.

int piezas[8][8] = {
0, 2, 2, 5, 3, 2, 1, 1,
0, 4, 5, 2, 4, 3, 0, 0,
0, 4, 2, 2, 1, 2, 3, 2,
0, 3, 1, 5, 1, 2, 3, 4,
2, 5, 6, 5, 3, 1, 2, 7,
8, 2, 0, 0, 0, 2, 1, 1,
1, 2, 2, 1, 1, 6, 3, 4,
};

int myrow = 3; // the row I want to analyze
int index;
int min=0;

for (index=0;index<8;index++) {
    printf("%d", piezas[myrow][index] );
    if(piezas[myrow][index]<min)
        min=piezas[myrow][index];
    printf("\t\t");
}
printf("min: %d", min);

Результат, который я хочу получить, если исходная матрица:

int piezas[8][8] = {
0, 2, 2, 5, 3, 2, 1, 1,
0, 4, 5, 2, 4, 3, 0, 0,
0, 4, 2, 2, 1, 2, 3, 2,
0, 3, 1, 5, 1, 2, 3, 4,
2, 5, 6, 5, 3, 1, 2, 7,
8, 2, 0, 0, 0, 2, 1, 1,
1, 2, 2, 1, 1, 6, 3, 4,
};

И я выбираю строку номер 3:

0, 3, 1, 5, 1, 2, 3, 4,

Алгоритм должен выбрать

0, 1, 1

И выбрать случайным образом один из этих трех.

Может ли кто-нибудь дать мне какие-либо идеи о том, как я могу это сделать? Я застрял с этим с раннего утра. Спасибо


c row matrix minimum
person Avión    schedule 13.05.2013    source источник

Ответы (5)


arrow_upward
2
arrow_downward

Тогда я бы попробовал отсортировать строку и случайным образом выбрать один из трех первых элементов.

// integer comparator
int compare(int * a, int * b) {return *a - *b;}

// allocate memory to hold the copy
int rowCopy[sizeof(piezas[myrow])/sizeof(int)];
// copy the row
memcpy(rowCopy, piezas[myrow], sizeof(piezas[myrow]));
// sort it
qsort(rowCopy, sizeof(piezas[myrow])/sizeof(int), sizeof(rowCopy[0]), compare);
// initialize the random number generator
srand(time(NULL));
// return randomly one of the first 3 elements
return rowCopy[rand() % 3]
person Sergey L.    schedule 13.05.2013
comment
Вроде все нормально, но у меня проблемы со строкой qsort. Это ошибка, которую он показывает: main.cpp:64: error: invalid conversion from 'int (*)(int*, int*)' to 'int (*)(const void*, const void*)' main.cpp:64: error: initializing argument 4 of 'void qsort(void*, size_t, size_t, int (*)(const void*, const void*))' - person Avión; 13.05.2013
comment
ага, это предупреждение, что я определил компаратор не как реальный прототип. Если вы не работаете над какой-то странной встроенной системой, безопасно привести ее к типу int (*)(const void*, const void*). В противном случае определите его как int compare(void * a, void * b) {return *(int*)a - *(int*)b;}. Обычно я устанавливаю это как предупреждение в коде разработки и использую преобразование типа указателя функции в коде выпуска. На x84 это будет работать нормально, на некоторых встроенных архитектурах безопаснее определить функцию с двойным void* и привести аргументы внутри нее к типу. - person Sergey L.; 13.05.2013
comment
Называть ваше второе решение линейным временем... вводит в заблуждение. Это линейно только в том, что запрашиваемое число является фиксированной константой. Если вы хотите пойти туда, можно сказать, что, поскольку размер строки также фиксирован, все решение выполняется за постоянное время. Это больше O (N * M), что может быть хуже, чем ваше решение для сортировки, которое выполняется за время nlogn. - person xaxxon; 13.05.2013
comment
@xaxxon Да, в этом вы правы. Сначала я хотел жестко закодировать 3 в функцию, но позже отказался от этого. В итоге получилась более-менее дешевая сортировка вставками с ограничением по элементам. - person Sergey L.; 13.05.2013
comment
во второй раз через ваш второй j-цикл решения с вводом 2, 1, он переместит 2 в позицию [1], вставит 1 в [0] и увеличит j до j = 1, что не меньше, чем numfound ==1. затем он выполнит проверку numfound ‹ howmany, и это будет верно 1‹3, поэтому он установит result[1] = 1, перезаписав 2. ‹== Я думаю. Возможно, сделайте перерыв в цикле j после того, как вы достигнете своего условия, а затем также проверьте наличие j ›= numfound в дополнение к numfound ‹ howmany. В основном, чтобы сказать вам, добавили ли вы что-нибудь в j-loop или нет. Или просто используйте флаг. Или, может быть, просто вставьте первые 3 перед - person xaxxon; 13.05.2013
comment
На самом деле... ваше первое решение было настолько хорошим, что я просто удалил второе. - person xaxxon; 13.05.2013
comment
@xaxxon Да, вот что происходит, когда вы не тестируете свой код :) - person Sergey L.; 13.05.2013
comment
Я удалил часть в конце, в которой говорится, что вы можете сделать лучше :) Это для новичков, и ваше решение очень хорошее! - person xaxxon; 13.05.2013

arrow_upward
0
arrow_downward

Создайте копию одной строки в tmp_array (8 элементов), затем qsort(tmp_array) и, наконец, используйте rand() % 3 в качестве номера элемента ответа.

person mvp    schedule 13.05.2013

arrow_upward
0
arrow_downward

Простое решение: у вас есть три переменные min1, min2, min3 для хранения трех минимальных переменных.

person ganesshkumar    schedule 13.05.2013

arrow_upward
0
arrow_downward

возьмите массив number[3] и сохраните в нем эти три значения. Теперь

int length = sizeof(numbers) / sizeof(int);
int randomNumber = numbers[rand() % length];
person Dayal rai    schedule 13.05.2013
comment
Найти 3 наименьших намного сложнее, чем выбрать случайный. Как говорится в его комментарии, у него проблемы с поиском 3. - person xaxxon; 13.05.2013

arrow_upward
0
arrow_downward

Вообще говоря, вы можете использовать пирамидальную сортировку, чтобы получить минимум N элементов в массиве, таком как выбранная вами строка, вам не нужно сортировать все элементы. Но помните, что нельзя сохранять результат сортировки в самой строке. И используйте rand(), чтобы выбрать один из них.

person vvy    schedule 13.05.2013