IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Максимальное множество друзей
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Женский
Реальное имя: Jekaterina Lauce

Репутация: -  0  +


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


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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


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

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

Это называется Система Непересекающихся Множеств.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Jekaterina   Максимальное множество друзей   2.01.2007 6:09
Bokul   Т.е. все количество людей? Пара вопросов: 1 Яв…   2.01.2007 7:06
Jekaterina   В первой строке максимально возможный номер друга,…   2.01.2007 15:10
мисс_граффити   такая структура делается без проблем: type druzia=…   2.01.2007 16:54
Jekaterina   Файл текстовый, но с динамическими структурами не …   2.01.2007 17:13
volvo   А откуда, ты думаешь, он возьмется, опыт-то? Просн…   2.01.2007 17:16
Jekaterina   Беда в том, что я программирую вообще только 5 мес…   2.01.2007 17:34
Michael_Rybak   Сначала сам алгоритм. Пусть есть N человек. Будем …   2.01.2007 18:34
Jekaterina   Спасибо, попробую разобраться.   2.01.2007 18:47
Michael_Rybak   Упс, ошибочка вышла; вместо color[i] := b; нужно c…   2.01.2007 19:33
Jekaterina   Все-таки своего ума не хватает... :mega_chok:   3.01.2007 0:55
Bokul   Проблемы в реализации алгоритма Michael_Rybak-а?   3.01.2007 1:06
Jekaterina   Большие проблемы   3.01.2007 1:54
Jekaterina   Я пыталась решать так (см. внизу). Это чайниковски…   3.01.2007 2:06
Bokul   Вот, то как я понял алгоритм Michael_Rybak-а, толь…   3.01.2007 2:19
Michael_Rybak   Вот, то как я понял алгоритм Michael_Rybak-а, тол…   3.01.2007 5:21
Jekaterina   Спасибо! В программе не идет запись в файл - п…   3.01.2007 2:40
Bokul   Ты о чем?   3.01.2007 2:42
Jekaterina   В процедуре записи чисел в файл у меня паскаль нас…   3.01.2007 2:51
Bokul   :blink: Действительно так. Не знаю в чем проблема…   3.01.2007 3:04
volvo   :blink: Действительно так. Не знаю в чем проблема…   3.01.2007 3:12
мисс_граффити   TP не дает писать непосредственно 44, 5 и т.д. а в…   3.01.2007 3:12
Bokul   Ну я сам методом тыка дошел до того, что требует э…   3.01.2007 3:19
volvo   P.S. кстати, почему Fpc, поставленный на совместим…   3.01.2007 3:28
Jekaterina   В с++ я дошла до заданий типа "Определить вре…   3.01.2007 5:24
Bokul   Да, но и немерено возрастёт количество строк ко…   3.01.2007 5:48
klem4   Еще вариант по поводу скорости думаю не особо быст…   3.01.2007 16:20
Jekaterina   Спасибо! Но почему же Free Pascal (ведь это Fr…   3.01.2007 19:54
klem4   Если ты о моей программе, то там и нету создания в…   3.01.2007 20:05
Jekaterina   Простите чайника! :yes2: Буду работать   3.01.2007 20:17
Jekaterina   Спасибо, дописла необходимое -сервер корректно про…   3.01.2007 22:55
Jekaterina   Убрала несколько строк-паразитов. Исправленный вар…   3.01.2007 23:14
Michael_Rybak   А что за сервер?   3.01.2007 23:22
Jekaterina   http://apts.cs.fmf.lu.lv/apts/index.php Это наш ун…   3.01.2007 23:26


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.01.2021 11:14
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name