Доброй ночи! Не справляюсь с задачей: "В стране Н. пользуются порталом "Друзья". Во входном файле в первой строке дается номер максимально возмоной персоны, ниже приведены пары друзей, например:
15
2 4
6 11
2 13
13 2
4 14
Запись 2 4 означает, что персона 2 является другом персоны 4, и т. д. Друзья объединяются в множество друзей: например, из пар 2 4 и 2 13 образуется множество друзей {2, 4, 13}. Цель-отыскать наибольшее множество друзей и вывести его в выходной файл. Я думаю, здесь нужно использовать массив множеств, но не знаю, как правильно описать переменные (такая структура мне раньше не попадалась). Сам алгоритм мне тоже не ясен - может быть, кто-то из вас поймет, как использовать этот максимальный номер в первой строке? (надеюсь, динамические переменные здесь можно не использовать-я с ними пока крайне слабо знакома, а разобраться в решении хочется )Заранее благодарю за помощь!
1 2
1 22
3 4
4 44
5 6
В первой строке максимально возможный номер друга, который может быть указан в дружественных парах, напр.,
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 месяцев и при этом работаю в школе учителем математики. Времени не хватает освоить все как следует. Пошла в университет - мне интересна информатика. Мне еще повезло. Рядом за партами сидят бывшие музыканты, биологи, почти все старше в 1,5-2 раза *(в Латвии большая нехватка учителей, потому такой бардак). Педагоги с одной стороны понимают уровень основной массы студентов, с другой - дают такие задания, которые человеку с никаким опытом программирования не решить. Я не жалуюсь-мне нравится паскаль, я сама пытаюсь ковыряться в с, питоне-просто чтоб хоть представление иметь. Проблема такова, что со своими 37 уроками в неделю,2 детьми,2 классными руководствами до динамических структур данных я смогу добраться только к лету-если буду заниматься как сейчас, ночью и на каникулах. Простите, что ответ длинный получился и немного личный.
Так пока я стараюсь четко основы понять, и все решаю с простыми циклами, массивами и т. д. -просто с этими задачамии месяц ничего не получалось, пришла к вам.
Сначала сам алгоритм. Пусть есть 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, и выбирая наибольшее
Спасибо, попробую разобраться.
Упс, ошибочка вышла; вместо color[i] := b; нужно color[i] := color[b];
Все-таки своего ума не хватает...
Проблемы в реализации алгоритма Michael_Rybak-а?
Большие проблемы
Я пыталась решать так (см. внизу). Это чайниковский метод (перебор подряд, для 6 строчек, без входного-выходного файла, с обычным выводом на экран), и он работает верно не для все случаев, но какие-то результаты есть. Цвета для меня пока сложноваты.
Прикрепленные файлы
DRAUGI1.PAS ( 2.67 килобайт )
Кол-во скачиваний: 209
Вот, то как я понял алгоритм 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.
Спасибо! В программе не идет запись в файл - паскаль требует переменную, но я постараюсь разобраться.
Ты о чем?
В процедуре записи чисел в файл у меня паскаль настоятельно требует 'variable identifier'
Действительно так. Не знаю в чем проблема.. В FreePascal-е компилируется все на ура.
Вот файл, который создается процедурой WriteFile. Только поменяй расширение на .dat
friends.pas ( 18 байт )
Кол-во скачиваний: 431
TP не дает писать непосредственно 44, 5 и т.д.
а вот если
a:=44;- другое дело
write(f,a);
Ну я сам методом тыка дошел до того, что требует это старье (извиняюсь за выражение), но не знал почему не принимает константу..
P.S. кстати, почему Fpc, поставленный на совместимость с Tp, не ловит этого?
В с++ я дошла до заданий типа "Определить время через секунду", не смогу разобраться
Еще вариант по поводу скорости думаю не особо быстрый
Прикрепленные файлы
friends.pas ( 1.19 килобайт )
Кол-во скачиваний: 201
Спасибо! Но почему же Free Pascal (ведь это Free Pascal, верно?) у меня не создает выходного файла?
Если ты о моей программе, то там и нету создания входного файла, создай сама, в чем проблема-то ?
Простите чайника! Буду работать
Спасибо, дописла необходимое -сервер корректно протестировал все варианты! Программу прилагаю (вдруг пригодится еще какому-нибудь чайнику ироде меня). Отдельное спасибо г-ну klem4
Прикрепленные файлы
draugi.pas ( 1.39 килобайт )
Кол-во скачиваний: 186
Убрала несколько строк-паразитов. Исправленный вариант прилагаю
Прикрепленные файлы
draugi.pas ( 1.34 килобайт )
Кол-во скачиваний: 193
А что за сервер?
http://apts.cs.fmf.lu.lv/apts/index.php
Это наш университетский сервер для проверки правильности решений