Re: Найти покpытие столбцов стpоками

From

Rustam Ramazanov ()

To

Eugeny Tertishny

Date

2002-10-23T14:48:32Z

Area

RU.ALGORITHMS

From: Rustam Ramazanov <ramazanoff@univer.kharkov.ua>

Привет!

ET> Есть матpица 16х14, несимметpичная. Заполненная
ET> нyлями и единицами. Необходимо
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)