[C++] Найти в матрице наибольший набор строк, удовлетворяющ - Форум
Среда, 07.12.2016, 11:32
Задачи по информатике
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Модератор форума: ignorer, KOT_B_MEIIIKE, PASCAL26, atvrider 
Форум » Решение задач по информатике » Задачи по программированию + блок-схемы » [C++] Найти в матрице наибольший набор строк, удовлетворяющ
[C++] Найти в матрице наибольший набор строк, удовлетворяющ
VorkulskyДата: Суббота, 27.11.2010, 13:27 | Сообщение # 1
Сержант
Группа: Новичок
Сообщений: 5
[ 1 ]
Статус: Offline
Описание темы: [09.12.2010] Двумерные массивы
В матрице bool найти наибольший набор строк, никакие две из которых не имеют true в одинаковых столбцах.

Например для матрицы 4*5:

0| 0 0 1 1
1| 0 1 1 1
2| 1 1 0 0
3| 1 0 0 0
4| 0 1 0 0
Ответ: 0, 3, 4

Решение за деньги даже не предлагайте!

Словесное описание алгоритма тоже приветствуется.

Сообщение отредактировал Vorkulsky - Суббота, 27.11.2010, 13:31
 
BinaryWolfДата: Четверг, 02.12.2010, 15:48 | Сообщение # 2
Генерал-лейтенант
Группа: Новичок
Сообщений: 51
[ 0 ]
Статус: Offline
Здесь нужен перебор по сочетаниям, сам написать не могу, давно такое делал

Луна, единственная спутница моя, отведи меня домой, залечи раны мои и помоги забыть всё.
 
VorkulskyДата: Суббота, 04.12.2010, 09:11 | Сообщение # 3
Сержант
Группа: Новичок
Сообщений: 5
[ 1 ]
Статус: Offline
Спасибо, уже сам сделал.
Взял двоичное число и каждый раз прибавляю к нему единицу. Где в двоичном числе стоят единицы, те наборы строк проверяю. Если сошлось, запоминаю двоичное число в max, и проверяю дальше. Если сошлись строки, выбранные другим двоичным числом, у которого больше единиц, записываю его вместо max.
Работает за n!
Быстрее можно сделать рекурсивной функцией или деревом. Но мне главное, чтоб работало.
 
Форум » Решение задач по информатике » Задачи по программированию + блок-схемы » [C++] Найти в матрице наибольший набор строк, удовлетворяющ
Страница 1 из 11
Поиск:

Copyright MyCorp © 2016