|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rustam Ramazanov 2:5020/400 23 Oct 2002 14:48:32
To : Eugeny Tertishny
Subject : Re: Hайти покpытие столбцов стpоками
--------------------------------------------------------------------------------
Привет!
ET> Есть матpица 16х14, несимметpичная. Заполненная
ET> нyлями и единицами. Hеобходимо
ET> найти минимальное количество стpок, таких чтобы
ET> хоть в одном столбце была 1.
ET> Считается, что такие стpоки в любом слyчае есть
Упрощает жизнь, но не является решающим фактором.
ET> Хочется сделать не использyя пеp**оp.
А чем перебор плох? К тому же все перебирать не надо.
Можно сделать следующее:
1. Берем строку в которой максимальное число единиц.
Запомним столбцы в которых стоят единицы.
2. В оставшихся строках в запомненных столбцах ставим 0.
3. Переходим в п.1. Работа алгоритма заканчивается либо если во всех
строках остаются только нули, либо если перебрали все строки (это тот
самый худший вариант).
Реализовать можно как рекурсивно, так и итерациями.
От размера матрицы ничего не зависит.
Если на каждой итерации запоминать кол-во единиц в выбранных строках,
то можно проверить, заполняются ли все столбцы единицами или нет.
К сожалению я не могу строго доказать, что получим именно минимальное
число строк, но кажется, что это так и будет.
Рустам.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Hайти покpытие столбцов стpоками 
