реализуемо ли Опции

[.helga]

Реализуемо ли это в Делфи??


1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице
2 Найти наименьший из элементов, через которые не проходит ни одна прямая
3 Вычесть его из всех элементов, через которые не проходят прямые
4 Прибавить его ко всем элементам, лежащим на пересечении прямых
5 Элементы, через которые проходит только одна прямая, оставить неизменными

[Bokul]

Malice, можешь сделать небольшое пояснение алгоритма?

P.S. может кому надо - отформатированное чудо Malice-а (извиняюсь перед Malice-ом, просто так легче разобраться , имхо)
 10.pas ( 1.51 килобайт ) Кол-во скачиваний: 303


Сообщение отредактировано: Bokul - 4.01.2007 11:01

[Malice]

Malice, можешь сделать небольшое пояснение алгоритма?

Конечно Простой перебор, поясню немного:
1. x = 0..$FFFF - Вырианты зачеркиваний, в битовом представлении первые 8 бит - столбцы, вторые строки, 1-зачеркнут, 0 -нет
2. Зачеркиваем в соответствии с x
3. Проверяем все ли 0-ли зачеркнуты (там, где b)
4. считаем колво 1-ц в x
5. Сравниваем на минимум
Из типа x вытекает ограничение на размер матрицы (8 х 8), но перебор можно и иначе сделать, если что.
ps а что, хорошее форматирование, мне так, например, легче