Максимальное множество друзей Опции

[Jekaterina]

Доброй ночи! Не справляюсь с задачей: "В стране Н. пользуются порталом "Друзья". Во входном файле в первой строке дается номер максимально возмоной персоны, ниже приведены пары друзей, например:
15
2 4
6 11
2 13
13 2
4 14
Запись 2 4 означает, что персона 2 является другом персоны 4, и т. д. Друзья объединяются в множество друзей: например, из пар 2 4 и 2 13 образуется множество друзей {2, 4, 13}. Цель-отыскать наибольшее множество друзей и вывести его в выходной файл. Я думаю, здесь нужно использовать массив множеств, но не знаю, как правильно описать переменные (такая структура мне раньше не попадалась). Сам алгоритм мне тоже не ясен - может быть, кто-то из вас поймет, как использовать этот максимальный номер в первой строке? (надеюсь, динамические переменные здесь можно не использовать-я с ними пока крайне слабо знакома, а разобраться в решении хочется )Заранее благодарю за помощь!

[Bokul]

Во входном файле в первой строке дается номер максимально возмоной персоны

Т.е. все количество людей?

Пара вопросов:
1 Является ли дружба взаимной? Т.е. в твоем случае является ли 4 другом 2?
2 Какие множества будут в таком случае?

1 2
1 22

3 4
4 44

5 6

[Jekaterina]

В первой строке максимально возможный номер друга, который может быть указан в дружественных парах, напр.,
3
1 2
2 3
(друга с номером больше 3 указывать нельзя).
Дружба взаимна. В приведенном вами примере решение таково: 3 (т.к. имеются 2 одинаково длинных компании 1 2 22 и 3 4 44, больше компании создать нельзя)


(друга с номером больше тройки указывать нельзя)- т.е. в файле не будут друзья под номерами 4,5,6,...,а только 1,2,3 (не обязательно подряд или все номера) .При этом записи могут дублироваться.

[мисс_граффити]

такая структура делается без проблем:

type druzia=set of byte;
var ar: array[1..5] of druzia;

но толку от нее не много...
я поставила размерность массива 5, а у тебя она заранее неизвестно какой окажется.

видимо, все же придется работать с динамическими структурами, если вы их проходили...
или делать очень большой массив (чтобы наверняка хватило).

небольшой нюанс: входной файл - текстовый?

по алгоритму... можно так: считали из файла мн-во. есть пересечения с первым, записанным в массив? добавили считанное к первому. со вторым? ... если нет ни одного - записали в новую ячейку. если есть сразу с несколькими - объединили их.
а потом считаем кол-во эл-тов, входящих в множество. вот здесь нам и понадобится номер персоны.

[Jekaterina]

Файл текстовый, но с динамическими структурами не слажу - нет опыта.

[volvo]

А откуда, ты думаешь, он возьмется, опыт-то? Проснешься одним утром, и... "Вот он, опыт, во сне пришел!!" Так что-ли?

Пока не начнешь использовать динамику в своих программах - так и не будет понимания и опыта использования...

[Jekaterina]

Беда в том, что я программирую вообще только 5 месяцев и при этом работаю в школе учителем математики. Времени не хватает освоить все как следует. Пошла в университет - мне интересна информатика. Мне еще повезло. Рядом за партами сидят бывшие музыканты, биологи, почти все старше в 1,5-2 раза *(в Латвии большая нехватка учителей, потому такой бардак). Педагоги с одной стороны понимают уровень основной массы студентов, с другой - дают такие задания, которые человеку с никаким опытом программирования не решить. Я не жалуюсь-мне нравится паскаль, я сама пытаюсь ковыряться в с, питоне-просто чтоб хоть представление иметь. Проблема такова, что со своими 37 уроками в неделю,2 детьми,2 классными руководствами до динамических структур данных я смогу добраться только к лету-если буду заниматься как сейчас, ночью и на каникулах. Простите, что ответ длинный получился и немного личный.

Так пока я стараюсь четко основы понять, и все решаю с простыми циклами, массивами и т. д. -просто с этими задачамии месяц ничего не получалось, пришла к вам.

[Michael_Rybak]

Сначала сам алгоритм. Пусть есть N человек. Будем использовать N цветов. Изначально человека 1 покрасим в цвет 1, человека 2 - в цвет 2, и т.д. Все люди покрашены в разные цвета.

Дальше идем по списку пар друзей. Читаем очередную пару: А, В. Если цвета А и В совпадают, значит, они и так уже подружились. Если нет - смотрим, каких людей *меньше* - покрашенных в цвет А, или в цвет В. Меньшую группу перекрашиваем в цвет большей.

В конце остается выбрать наиболее часто встречающуюся краску.

Сложность такого решения, в оптимальной реализации, составит O(n log n), потому что каждый конкретный человек будет при каждом перекрашивании попадать в группу с как минимум в 2 раза большей численностью, и потому будет перекрашен не более [log n] + 1 раз.

Но в твоем случае, судя по всему, достаточно и O(n^2). Тогда можно пренебречь условием "Меньшую группу перекрашиваем в цвет большей", и просто перекрашивать А в В.

Достаточно объявить один массив:

const MAX_N = 128;
var color: array [1 .. MAX_N] of longint;

Решение будет выглядеть примерно так:

Read(n);
for i := 1 to n do
  color[i] := i;
while not SeekEof() do begin
  Read(a, b);
  t := color[a];
  for i := 1 to n do
    if color[i] = t then
      color[i] := b;
end;
//дальше делаем цикл по i от 1 до n, строя множество, покрашенное в цвет i, и выбирая наибольшее

[Jekaterina]

Спасибо, попробую разобраться.

[Michael_Rybak]

Упс, ошибочка вышла; вместо color[i] := b; нужно color[i] := color[b];

[Jekaterina]

Все-таки своего ума не хватает...

[Bokul]

Проблемы в реализации алгоритма Michael_Rybak-а?

[Jekaterina]

Большие проблемы

[Jekaterina]

Я пыталась решать так (см. внизу). Это чайниковский метод (перебор подряд, для 6 строчек, без входного-выходного файла, с обычным выводом на экран), и он работает верно не для все случаев, но какие-то результаты есть. Цвета для меня пока сложноваты.

[Bokul]

Вот, то как я понял алгоритм Michael_Rybak-а, только множества у меня не вышло присобачить.

const MaxN=128;
Var colors:array[1..MaxN] of integer;
    n:integer;

procedure WriteFile(s:string);//создаем файл
var f:file of integer;
begin
  assign(f,s);
  rewrite(f);
  write(f,44);
  write(f,5,6);
  write(f,4,44);
  write(f,1,3);
  write(f,4,2);
  close(f);
end;

function CountColor(color:integer):integer;//считаем сколько элементов в массиве colors имеют цвет color
var i,res:integer;
begin
  res:=0;
  for i:=1 to n do
      if colors[i]=color then
         inc(res);
  CountColor:=res;
end;

procedure Color(WhatColor,InColor:Integer);//закрашиваем все элементы массива colors цвета WhatColor в цвет InColor
var i:integer;
begin
  for i:=1 to n do
      if colors[i]=WhatColor then
         colors[i]:=InColor;
end;

function MaxColor:integer;//находим какого цвета большинство элементов
var i,j,res_color,buf_num,res_num:integer;
begin
  res_num:=0;
  res_color:=0;
  for i:=1 to n do
      begin
           buf_num:=0;
           for j:=i to n do
               if colors[i]=colors[j] then
                  inc(buf_num);
           if buf_num>res_num then
              begin
                   res_color:=colors[i];
                   res_num:=buf_num;
              end;
      end;
  MaxColor:=res_color;
end;

var   i,a,b,t:integer;
      f:file of integer;
begin
  WriteFile('friends.dat');
  assign(f,'friends.dat');
  reset(f);
  read(f,n);
  for i:=1 to n do
      colors[i]:=i;
  while not eof(f) do
        begin
             read(f,a,b);
             if colors[a]<>colors[b] then
                if CountColor(colors[a]) > CountColor(colors[b]) then
                   Color(colors[b],colors[a])
                else
                   Color(colors[a],colors[b]);
        end;
  close(f);
  t:=MaxColor;
  for i:=1 to n do
      if colors[i]=t then
         write(i,' ');
  readln;
end.

Сообщение отредактировано: Bokul - 2.01.2007 22:25

[Jekaterina]

Спасибо! В программе не идет запись в файл - паскаль требует переменную, но я постараюсь разобраться.

[Bokul]

Ты о чем?

[Jekaterina]

В процедуре записи чисел в файл у меня паскаль настоятельно требует 'variable identifier'

[Bokul]

Действительно так. Не знаю в чем проблема.. В FreePascal-е компилируется все на ура.
Вот файл, который создается процедурой WriteFile. Только поменяй расширение на .dat
 friends.pas ( 18 байт ) Кол-во скачиваний: 332

[volvo]

Действительно так. Не знаю в чем проблема..

Объясняю: в дословном следовании определениям...

Write (procedure)
For typed files, writes a variable into a file component.

Значит, должна быть переменная...