Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Максимальное множество друзей

Автор: Jekaterina 2.01.2007 6:09

Доброй ночи! Не справляюсь с задачей: "В стране Н. пользуются порталом "Друзья". Во входном файле в первой строке дается номер максимально возмоной персоны, ниже приведены пары друзей, например:
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 2.01.2007 7:06

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

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

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

1 2
1 22

3 4
4 44

5 6



Автор: Jekaterina 2.01.2007 15:10

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


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

Автор: мисс_граффити 2.01.2007 16:54

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

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

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

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

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

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

Автор: Jekaterina 2.01.2007 17:13

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

Автор: volvo 2.01.2007 17:16

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

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

Автор: Jekaterina 2.01.2007 17:34

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

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

Автор: Michael_Rybak 2.01.2007 18:34

Сначала сам алгоритм. Пусть есть 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 2.01.2007 18:47

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

Автор: Michael_Rybak 2.01.2007 19:33

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

Автор: Jekaterina 3.01.2007 0:55

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

Автор: Bokul 3.01.2007 1:06

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

Автор: Jekaterina 3.01.2007 1:54

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

Автор: Jekaterina 3.01.2007 2:06

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


Прикрепленные файлы
Прикрепленный файл  DRAUGI1.PAS ( 2.67 килобайт ) Кол-во скачиваний: 209

Автор: Bokul 3.01.2007 2:19

Вот, то как я понял алгоритм 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 3.01.2007 2:40

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

Автор: Bokul 3.01.2007 2:42

Ты о чем?

Автор: Jekaterina 3.01.2007 2:51

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

Автор: Bokul 3.01.2007 3:04

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

Автор: volvo 3.01.2007 3:12

Цитата(Bokul @ 2.01.2007 22:04)
blink.gif
Действительно так. Не знаю в чем проблема..

Объясняю: в дословном следовании определениям...
Цитата(TP Help)
Write (procedure)
For typed files, writes a variable into a file component.
Значит, должна быть переменная...

Автор: мисс_граффити 3.01.2007 3:12

TP не дает писать непосредственно 44, 5 и т.д.
а вот если

a:=44;
write(f,a);
- другое дело

Автор: Bokul 3.01.2007 3:19

Ну я сам методом тыка дошел до того, что требует это старье smile.gif (извиняюсь за выражение), но не знал почему не принимает константу..

P.S. кстати, почему Fpc, поставленный на совместимость с Tp, не ловит этого?

Автор: volvo 3.01.2007 3:28

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

Автор: Michael_Rybak 3.01.2007 5:21

Цитата(Bokul @ 2.01.2007 21:19) *

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


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

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

Это называется Система Непересекающихся Множеств.

Автор: Jekaterina 3.01.2007 5:24

В с++ я дошла до заданий типа "Определить время через секунду", не смогу разобраться mega_chok.gif

Автор: Bokul 3.01.2007 5:48

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

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

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

Автор: klem4 3.01.2007 16:20

Еще вариант по поводу скорости думаю не особо быстрый smile.gif




Прикрепленные файлы
Прикрепленный файл  friends.pas ( 1.19 килобайт ) Кол-во скачиваний: 201

Автор: Jekaterina 3.01.2007 19:54

Спасибо! Но почему же Free Pascal (ведь это Free Pascal, верно?) у меня не создает выходного файла?

Автор: klem4 3.01.2007 20:05

Если ты о моей программе, то там и нету создания входного файла, создай сама, в чем проблема-то ?

Автор: Jekaterina 3.01.2007 20:17

Простите чайника! yes2.gif Буду работать

Автор: Jekaterina 3.01.2007 22:55

Спасибо, дописла необходимое -сервер корректно протестировал все варианты! Программу прилагаю (вдруг пригодится еще какому-нибудь чайнику ироде меня). Отдельное спасибо г-ну klem4 give_rose.gif


Прикрепленные файлы
Прикрепленный файл  draugi.pas ( 1.39 килобайт ) Кол-во скачиваний: 186

Автор: Jekaterina 3.01.2007 23:14

Убрала несколько строк-паразитов. Исправленный вариант прилагаю


Прикрепленные файлы
Прикрепленный файл  draugi.pas ( 1.34 килобайт ) Кол-во скачиваний: 193

Автор: Michael_Rybak 3.01.2007 23:22

А что за сервер?

Автор: Jekaterina 3.01.2007 23:26

http://apts.cs.fmf.lu.lv/apts/index.php
Это наш университетский сервер для проверки правильности решений