| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сумма элементов в строке и столбце |
| Автор: Sazor 3.12.2010, 20:30 |
| Есть двумерный массив размером SxS, число S задается во входном файле. Еще задаются координаты заполненных элементов(все остальные я заполняю 0). Заполненный элемент может содержать либо 1 либо -1. Надо расставить 1 и -1 таким образом, чтобы количество 1 и -1 в строке и в столбце разнилось не более чем на 1(т.е. сумма равна либо -1, либо 0, либо 1). Сумма в разных строках и столбцах может быть различна. Необходимо определить где 1, а где -1. Если расставить невозможно, то выводится "No". |
| Автор: Akina 3.12.2010, 21:16 | ||||
1) Поясните, надо расставить их в незаполненные (нулевые) элементы или надо перераспределить имеющиеся? Если расставить - во все незаполненные, или мождно часть оставить нулевыми? 2) Гарантировано ли то, что при исходных данных задача имеет решение? |
| Автор: Sazor 3.12.2010, 21:47 |
| 1) Только перераспределить имеющиеся (т.е. координаты которых нам даны в исходных данных). Все должны быть заполнены. 2) Данные по ограничениям подходят 100%, но "Если расставить невозможно, то выводится 'No'. " |
| Автор: sandland 3.12.2010, 23:36 |
| Фактически мы получаем квадратную матрицу. SxS Сложность алгоритма имеет значения? Идея 1: а) Проходим циклом по строкам, если в строке сумма не принадлежит {-1,0,1} - сдвигаем N необходимых "подходящих" элементов в строке на строку ниже. ( под понятием "сдвигаем" понимаем следующее: ищем в строке ниже 0-ой элемент, и меняем его с текущим, если 0 нету, ищем в строке еще ниже, если строки еще ниже нет, то идем вверх и пробуем обменять его уже на инвертированный элемент с сохранением требуемого диапазона сумм, т.е. -1 обмениваем с 1 и наоборот. Но повторю, необходимо проверять новую сумму в обоих строках. ) N=|SUM-1|, "Подходящий элемент" - зависит от суммы, если сумма>1 , то убираем единицы, если <-1 ,то сдвигаем -1 соответственно. Проходя последнюю строку, если сумма не удовлетворяет требованиям, то "подходящие элементы" раскидываем по оставшимся строчкам с 0 суммами, но возможен вариант, когда N>Кол-во строчек с sum=0 , тогда выводим "NO" б) Проделываем аналогичную операцию над столбцами матрицы. Условия, достигнутые на первом этапе нарушены не будут, т.к перестановки по столбцам их не нарушат. Другой вопрос - какие ограничения на модель? Очевидно, что результат может быть не один, а несколько, смотря в какой последовательности и как делать перестановки. + этот алгоритм очень медленный, как минимум, зная ненулевые позиции его уже можно ускорить. Пример: 1 0 1 0 0 1 -1 0 1 => -1 1 1 => "NO" 1 1 0 1 1 0 Еще 1 1 -1 1 1 -1 1 -1 -1 -1 => 1 -1 -1 => "DONE" 1 1 1 -1 1 1 На самом деле понимаю, что трудно понять описание выше написанного алгоритма по словам, алгоритм интересный, его нужно просто описать математически, но для этого нужно время, попробуйте просто логически записывать каждый шаг Вашей мысли при разборе конкретного примера , и на основе этого построить общую модель. |
| Автор: Akina 4.12.2010, 11:10 | ||
А нафига тогда начальные координаты? Куда как проще (и быстрее) расставлять "с нуля", имея размер матрицы и количества нулей и плюс-минус единиц. |
| Автор: Sazor 4.12.2010, 14:29 | ||
Распределить 1 и -1 нужно только по заданным координатам. Т.е. остальное пространство как бы дырки, которые изменять нельзя и они ни на что не влияют. |
| Автор: Akina 4.12.2010, 22:40 | ||
Т.е. обменивать местами до получения результата, что ли? |
| Автор: Sazor 5.12.2010, 12:35 | ||
Ну получается что так, только обменивать местами не надо, а надо изменять "статус" места с 1 на -1, и наоборот. |
| Автор: Akina 5.12.2010, 23:05 |
| А, то есть ещё и начальное количество плюс-минус единиц имеет право поменяться? |
| Автор: Sazor 6.12.2010, 08:37 | ||
Да. Более того, изначально там вообще ничего не стоит. Я просто помечаю его 1, например, чтобы знать, что здесь можно изменять статус. |
