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

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

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

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Максимальное множество друзей
сообщение
Сообщение #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  +


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

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

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

1 2
1 22

3 4
4 44

5 6




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


Пионер
**

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

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


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


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


просто человек
******

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

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


такая структура делается без проблем:
type druzia=set of byte;
var ar: array[1..5] of druzia;

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

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

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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Пионер
**

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

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


Файл текстовый, но с динамическими структурами не слажу - нет опыта.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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

Пока не начнешь использовать динамику в своих программах - так и не будет понимания и опыта использования...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

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

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


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

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


Michael_Rybak
*****

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

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


Сначала сам алгоритм. Пусть есть 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, и выбирая наибольшее

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

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

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


Спасибо, попробую разобраться.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

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

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


Упс, ошибочка вышла; вместо color[i] := b; нужно color[i] := color[b];
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Пионер
**

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

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


Все-таки своего ума не хватает... mega_chok.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гуру
*****

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

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


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


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


Пионер
**

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

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


Большие проблемы
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Пионер
**

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

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


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


Прикрепленные файлы
Прикрепленный файл  DRAUGI1.PAS ( 2.67 килобайт ) Кол-во скачиваний: 209
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гуру
*****

Группа: Пользователи
Сообщений: 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 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Пионер
**

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

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


Спасибо! В программе не идет запись в файл - паскаль требует переменную, но я постараюсь разобраться.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гуру
*****

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

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


Ты о чем?


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


Пионер
**

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

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


В процедуре записи чисел в файл у меня паскаль настоятельно требует 'variable identifier'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гуру
*****

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

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


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


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


Гость






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

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

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

 





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