Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: помогите написать программу  (Прочитано 7665 раз)
0 Пользователей и 1 Гость смотрят эту тему.
evgenia
Гость
« : 18-01-2006 11:18 » 

очень нужна помощь, не могу написать программу. Если кто-нибудь знает java, спасите меня.
На праздник приглашено N гостей, про некоторых из них известно, что они между собой родственники. Существуют связи: если А и В родственники, то В и А родственники; если А и В родственники, и В и С родственники, то А и С родственники. Написать программу, которая найдет из количества гостей максимальную по величине группу, в которой по крайней мере 2 члена между собой не родственники.
Содержание: в текстовом файле SUG.SIS в первой строчке через пробел написаны числа N и К(1<=N<=100, 0<=K<=N(N-1)/2), где N число гостей и К количество выявленных фактов родства. Все гости пронумерованы 1...N. В следующих К строчках файла написаны с пробелами целые числа А и В(1<=A<=N, 1<=B<=N), что значит, что А и В родственники.
В текстовом файле SUG.VAL в первой строчке выводится размер группы не родственников М и на второй строчке М с пробелом целые числа- номера членов группы, которые между собой не родственники. Если групп максимальных по величине несколько, то вывести все равно какую из них.
Пример SUG.SIS
5 3
1 2
3 4
5 1
SUG.VAL
2
1 3
SUG.SIS первая строчка 5-количество гостей, 3-количество родственников. Остальные строчки- номера родственников, 1 и 2 родственники...
SUG.VAL 2- количество не родственников, 1 и 3 номера не родственников.
Пожалуйста помогите, мне очень-очень надо
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 18-01-2006 12:13 » 

evgenia, в несколько мест одно и то же не постить!
Не ты ли писала нечто подобное пару недель назад?!
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Serega
Гость
« Ответ #2 : 20-02-2006 15:20 » 

тебе не java нужна а теория графов или теория множеств (что по сути одно и тоже)

отношение эквивалентности(родственники) делит множество гостей на классы эквивалентности(все гости в одном классе родственники)

формулировка "группу, в которой по крайней мере 2 члена между собой не родственники" мне не ясна, видимо твоя задача найти классы эквивалентости и взять из каждого по одному представителю

числа в примере похожи решение такой задачи, но вот комментарии явно странные,
1-3 это не родственники, но и 1-4 тоже, поэтому количество не родственников будет равняться количеству всех возможных пар гостей из разных классов

уточни условие
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 20-02-2006 16:16 » new

Судя по ответу, надо найти максимальную группу, в которой любые два человека не родственники

Способ решения: отношение родства задаёт отношение эквивалентности. Надо построить множества родственников и из каждого множества взять по одному родственнику.  В результате получится максимальное множество человек, в котором каждая пара - не родственники.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines