Помощь - Поиск - Пользователи - Календарь
Полная версия: Максимальное множество друзей
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Jekaterina
Доброй ночи! Не справляюсь с задачей: "В стране Н. пользуются порталом "Друзья". Во входном файле в первой строке дается номер максимально возмоной персоны, ниже приведены пары друзей, например:
15
2 4
6 11
2 13
13 2
4 14
Запись 2 4 означает, что персона 2 является другом персоны 4, и т. д. Друзья объединяются в множество друзей: например, из пар 2 4 и 2 13 образуется множество друзей {2, 4, 13}. Цель-отыскать наибольшее множество друзей и вывести его в выходной файл. Я думаю, здесь нужно использовать массив множеств, но не знаю, как правильно описать переменные (такая структура мне раньше не попадалась). Сам алгоритм мне тоже не ясен - может быть, кто-то из вас поймет, как использовать этот максимальный номер в первой строке? (надеюсь, динамические переменные здесь можно не использовать-я с ними пока крайне слабо знакома, а разобраться в решении хочется smile.gif )Заранее благодарю за помощь!
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
А откуда, ты думаешь, он возьмется, опыт-то? Проснешься одним утром, и... "Вот он, опыт, во сне пришел!!" Так что-ли? blink.gif

Пока не начнешь использовать динамику в своих программах - так и не будет понимания и опыта использования...
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
Все-таки своего ума не хватает... mega_chok.gif
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.


Jekaterina
Спасибо! В программе не идет запись в файл - паскаль требует переменную, но я постараюсь разобраться.
Bokul
Ты о чем?
Jekaterina
В процедуре записи чисел в файл у меня паскаль настоятельно требует 'variable identifier'
Bokul
blink.gif
Действительно так. Не знаю в чем проблема.. В FreePascal-е компилируется все на ура.
Вот файл, который создается процедурой WriteFile. Только поменяй расширение на .dat
Нажмите для просмотра прикрепленного файла
volvo
Цитата(Bokul @ 2.01.2007 22:04)
blink.gif
Действительно так. Не знаю в чем проблема..

Объясняю: в дословном следовании определениям...
Цитата(TP Help)
Write (procedure)
For typed files, writes a variable into a file component.
Значит, должна быть переменная...
мисс_граффити
TP не дает писать непосредственно 44, 5 и т.д.
а вот если
a:=44;
write(f,a);
- другое дело
Bokul
Ну я сам методом тыка дошел до того, что требует это старье smile.gif (извиняюсь за выражение), но не знал почему не принимает константу..

P.S. кстати, почему Fpc, поставленный на совместимость с Tp, не ловит этого?
volvo
Цитата(Bokul @ 2.01.2007 22:19)
P.S. кстати, почему Fpc, поставленный на совместимость с Tp, не ловит этого?
Читай
Цитата(User.PDF)
7.1.3 Turbo Pascal compatibility mode
, там есть полный список того, что ДА ловит установка режима совместимости с TP... Все остальное не будет приниматься во внимание - Write реализован по-другому в FPC...
Michael_Rybak
Цитата(Bokul @ 2.01.2007 21:19) *

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


Хочу уточнить, что для того, чтобы получилось O(n log n), нужно хранить связный список для каждого цвета, а также количество элементов каждого цвета; тогда перекрашивание будет занимать O(min(N_A, N_B)), а проверка, какая группа меньше - O(1).

Могу привести код, у меня на С++ в заготовках это есть.

Это называется Система Непересекающихся Множеств.
Jekaterina
В с++ я дошла до заданий типа "Определить время через секунду", не смогу разобраться mega_chok.gif
Bokul
Цитата
Хочу уточнить, что для того, чтобы получилось O(n log n), нужно хранить связный список для каждого цвета, а также количество элементов каждого цвета; тогда перекрашивание будет занимать O(min(N_A, N_B)), а проверка, какая группа меньше - O(1).

Да, но и немерено возрастёт количество строк кода.
Цитата
Могу привести код, у меня на С++ в заготовках это есть.

Если можешь/хочешь переведи на Pascal, хотел бы посмотреть.. smile.gif
klem4
Еще вариант по поводу скорости думаю не особо быстрый smile.gif

Jekaterina
Спасибо! Но почему же Free Pascal (ведь это Free Pascal, верно?) у меня не создает выходного файла?
klem4
Если ты о моей программе, то там и нету создания входного файла, создай сама, в чем проблема-то ?
Jekaterina
Простите чайника! yes2.gif Буду работать
Jekaterina
Спасибо, дописла необходимое -сервер корректно протестировал все варианты! Программу прилагаю (вдруг пригодится еще какому-нибудь чайнику ироде меня). Отдельное спасибо г-ну klem4 give_rose.gif
Jekaterina
Убрала несколько строк-паразитов. Исправленный вариант прилагаю
Michael_Rybak
А что за сервер?
Jekaterina
http://apts.cs.fmf.lu.lv/apts/index.php
Это наш университетский сервер для проверки правильности решений
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.