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

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

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

 
 Ответить  Открыть новую тему 
> Задача на графы, Очень срочно!
сообщение
Сообщение #1


Новичок
*

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

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


Помогите пожалуйста!! Завтра сдавать, я в графах ни бум-бум...очень прошу!
23. На плоскости заданы 2n точек своими координатами. Найдите уравнение какой-либо прямой, делящей данное множество точек на два подмножества по n точек.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

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

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


Условие не совсем понятно.А что если некоторые точки будут лежать на искомой прямой,то к какому подмножеству они буду относиться?Как можно задачать координаты точек?(целые или вещественные числа?)И самое главное,как множество точек,которые как таковой между собой никак не связаны, относится к графам?Если есть какие то конретные предписания,как это делать,то желательно о них упомянуть.И в каком виде нужно найти уравнение прямой?Можно например, как функцию у от х ,можно как точку и угол наклона.....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

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

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


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

Сообщение отредактировано: klik1602 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(klik1602 @ 3.03.2011 23:07) *
23. На плоскости заданы 2n точек своими координатами. Найдите уравнение какой-либо прямой, делящей данное множество точек на два подмножества по n точек.

Допустим, координаты точек содержатся в массиве/массивах.
1. Упорядочиваем этот/эти массив/массивы по возрастанию X.
2. Если xn <> xn+1, то искомое равнение есть x = (xn + xn+1) / 2;
3. Если xn = xn+1, то..
4. найти минимальный ненулевой угол, опирающийся на точки из данного множества (назовем его A);
5. произвести поворот системы координат на A/2 (вокруг произвольной точки).
6. Перейти к 1.

Решение, правда, не имеет особого отношения к графам.. И еще: пункты 4 и 5, возможно, можно заменить на что-то попроще, немного менее детерминированное - например, поворот на случайный угол до тех пор, пока не выполнится условие в п.2.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

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

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


ммм, попробую завтра утром сделать, если успею, ночью голова не варит совсем, спасибо большое вам..
не понимаю как вот это реализовать
4. найти минимальный ненулевой угол, опирающийся на точки из данного множества (назовем его A);
5. произвести поворот системы координат на A/2 (вокруг произвольной точки).

Сообщение отредактировано: klik1602 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(klik1602 @ 4.03.2011 1:15) *
не понимаю как вот это реализовать

Реализовать это можно полным перебором по всем точкам, примерно так:

aMin:= Pi;
for i:=1 to 2*n do
for j:=1 to 2*n do
if i<>j then
for k:=i+1 to 2*n do begin
a:= Angle(j,i,k);
if (a>Eps) and (a<aMin) then aMin:=a
end;

Тут Angle(x,y,z) - это величина угла между лучами, проведенными из точки с номером y в точки с номерами x и z (надо написать такую функцию); Eps - просто очень малое число (скажем, 1E-7).

Но для начала лучше вращать на случайный угол (см. конец моего первого мессаджа). Угол генерировать так:
a:= Random*Pi;

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

Получается несколько громоздко, если честно.. Можно попробовать придумать что-то более элегантное )). Но геометрия будет все равно та же, я думаю.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Злостный любитель
*****

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

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


1. Нам надо найти прямую, которая не параллельная ни одной a[i]a[j].
2. Пусть её уравнение M*x+N*y+k=0. Сортируем массив чисел M*a[i].x + N*a[i].y + k (то есть для каждой точки берём такое число, потом сортируем массив таких чисел). Получили массив b[i]. Берём c := (b[n]+b[n+1])/2 - ну то есть число из середины массива. В качестве ответа берём M*x+N*y+(k-c): ведь у ровно половины точек число M*a[i].x + N*a[i].y + k-c будет строго положительно, а у другой половины - строго отрицательно.

Вот по поводу пункта 1 что я думаю.
Метод взятия случайной прямой вида

a:=random*2*pi;
cos(a)*x + sin(a)*y = 0;

с высокой вероятностью быстро найдёт ответ, если он есть. А его может не быть.
Если есть совпадающие точки, то мы уже обламываемся, всё резко усложняется. Детерминированный алгоритм придумать для такого случая я вообще не могу.

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

Можно взять минимальное ненулевое dx := a[i].x-a[j].x (для этого надо отсортировать координаты x и перебрать пары соседних). Взять максимальное dy := a[i].y-a[j].y (для этого надо вычесть максимум из минимума)

Взять x*2*dy - y*dx = 0 в качестве искомой прямой: ведь вектор (dx; 2*dy) не параллелен ни одному отрезку a[i],a[j], потому что его тангенс наклона вдвое превышает все возможные тангенсы наклона отрезков, соединяющих точки из набора.

правка: увеличил буквы в уравнении прямой, а то тавтология

Сообщение отредактировано: TarasBer -


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


Новичок
*

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

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


добрый вечер, снова возвращаюсь к этой программе, которую я так и не сдала. Большое спасибо, за предложенные алгоритмы Lapp и TarasBer, хотела бы разобраться в вашем варианте TarasBer. Я так понимаю последовательность действий такая:
1. записываем координаты точек в массивы X и Y
2. далее нужно найти прямую,
Цитата
которая не параллельная ни одной a[i]a[j]
, вот что такое a[i]a[j] не совсем понятно,
далее
Цитата
Пусть её уравнение M*x+N*y+k=0.
, я так понимаю, М=cos(a), N=sin(a), где a:=random*2*pi;
подставим всё это мы получаем значения k, которые записываем в массив b[i] ????? или я не так понимаю, помогите разобраться пожалуйста..
3.
Цитата
Берём c := (b[n]+b[n+1])/2

4.
Цитата
В качестве ответа берём M*x+N*y+(k-c)


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


Профи
****

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

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


a[i]a[j]-это 2 точки нашего исходного массива,принципи это то, что нужно чтобы задать любую прямую на плоскости(пространстве))Но так же учтите,что решение TarasBer не универсально.
Цитата
Если есть совпадающие точки, то мы уже обламываемся, всё резко усложняется


Сообщение отредактировано: Krjuger -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Я думаю, что в условии должно быть требование, что никакие две точки не слвпадают, иначе задача просто нерешаема.

a[i] и a[j] - две точки.
a[i]a[j] - прямая, проходящая через a[i] и a[j]


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

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

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


Цитата
Пусть её уравнение M*x+N*y+k=0.
, я так понимаю, М=cos(a), N=sin(a), где a:=random*2*pi;
подставим всё это мы получаем значения k, которые записываем в массив b[i] - так значит вот этот пункт верный?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Профи
****

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

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


Цитата
я так понимаю, М=cos(a), N=sin(a), где a:=random*2*pi;

Не совсем,смотрите его тождества.
Цитата

cos(a)*x + sin(a)*y = 0;
M*x+N*y+k=0

Если к равно 0,то да будет так,как вы написали,а так все не так просто получается.

Цитата

Я думаю, что в условии должно быть требование, что никакие две точки не слвпадают, иначе задача просто нерешаема.

Почему не решаема??Мне кажется она усхожнится,возможно в разы,но будет решаема,первое,что я вижу,это появится зависимость от того сколько точек в 1 позиции,ну и соотвественно усложнятся некоторые моменты,такие как c := (b[n]+b[n+1])/2 уже некоректно.

А вообще у данного решения есть 1 маленький нюанс,что если уравнение прямой магическим образом по стечению обстоятельств будет проходить через нашу точку a[i],к какому множеству ее тогда причислять?

Скорее всего,когда студенту дается так мало условий,он имеет право,сам сузить задачу,приведя соответствующие аргументы,почему он не рассматривает этот случай и эту возможность.

Сообщение отредактировано: Krjuger -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

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

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


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


Профи
****

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

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


Вы можете взять и скопировать этот алгоритм суда,если хотите,и да,здесь можно давать ссылки на сторонние ресурсы,по крайней мере,админы переодически помогают,давая ссылки на нужную информацию с сторонних ресурсов.

Сообщение отредактировано: Krjuger -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

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

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


Отсортировав координаты точек в порядке неубывания Х-овых координат, а в случае одинаковых Х-овых координат в порядке неубывания У-овых координат, находим координаты средней точки (находящуюся в позиции n div 2+1), пусть это точка (Х0,У0). При этом множество точек оказалось разбито на 3 части: точки, лежащие на прямой х=Х0; точки, лежащие левее прямой х=Х0; точки, лежащие правее прямой х=Х0. Представим, что точки, лежащие левее прямой х=Х0 ( точки, лежащие правее прямой х=Х0) лежат в пределах некоторого прямоугольника, где Х1 (Х2) координаты его правого (левого) края. Тогда легко понять, что существует прямая с достаточно большим углом наклона, которая разделяет эти части. Осталось разделить только точки на прямой, чтобы количество точек в получившихся частях было соответствующим (т.е. пересечение прямой с прямой х=Х0). Если количество точек нечетно, то искомая линия проходит через среднюю точку, иначе над средней точкой (но под предыдущей, если она лежит па прямой х=Х0).

Определим:

Х1 - может быть легко найдена просмотром массива Х-овых координат справа налево от средней точки до нахождения первой координаты, отличной от Х0. Если такая координата не найдена, то Х1=Х0-1.

Х2 - может быть легко найдена просмотром массива Х-овых координат слева направо от средней точки до нахождения первой координаты, отличной от Х0. Если такая координата не найдена, то Х1=Х0+1.

У1 - это У-овая координата точки, предшествующей средней точке, если Х-ая ее координата равна Х0, или равна У0-1, если Х-овая координата точки, предшествующей средней точке, не равна Х0.

После того, как Х0,У0,Х1,У1 найдены, осталось написать уравнение прямой через точки с координатами (Х2,У2) (Х3,У3), определяемыми по следующему правилу:

если N - четно

то Х2=Х0; У2=(У0+У1)/2, Х3=Х0+Z/2,У3=У0-Ymax+Ymin

иначе Х2=Х0; У2=У0, Х3=Х0+Z/2,У3=У0-Ymax+Ymin

где Ymax- максимальная У-овая координата, Ymin - минимальная У-овая координата, Z=min(Х0-Х1,Х2-Х0).

кстати я всё сделала по этому алгоритму, всё работает) но уверенности в том что правильно нету, не согласитесь его посмотреть))?

Сообщение отредактировано: klik1602 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(klik1602 @ 27.03.2011 19:29) *
но уверенности в том что правильно нету, не согласитесь его посмотреть))?

И хорошо, что нет уверенности. Алгоритм неверный. Но рациональное зерно в нем есть, и он может быть довольно просто исправлен.


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


Новичок
*

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

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


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


Профи
****

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

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


Ну чтобы проверить,правильно или нет,нарисуйте на бумажке пару примеров, вбейте в вашу программу и посмотрите результаты ,которые вы получили,и сравните с вашими результатами.Во вторых,выложите код того, как вы это реализовали,люди не телепаты, может быть вы доработали алгоритм под вашу задачу,а может и нет,а если и изменили,то как.

Чем отличается алгоритм от нужной вам задачи.
Цитата
При этом множество точек оказалось разбито на 3 части: точки, лежащие на прямой х=Х0; точки, лежащие левее прямой х=Х0; точки, лежащие правее прямой х=Х0

Для вашей задачи недопустимо,чтобы точки лежали на прямой,иначе как определять к какому множеству они будут относиться.
Цитата
Если количество точек нечетно, то искомая линия проходит через среднюю точку.

Этот вариант тоже рассматривать не нужно,потому что у вас всегда четное количество точек.
Цитата
иначе над средней точкой (но под предыдущей, если она лежит па прямой х=Х0).

Возможно я что то напутал или неверно понял,но это утверждение не верно(точнее оно не полное).Если надо могу привести пример.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Новичок
*

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

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


вот код:
program L15_23;
const
maxn=100;
type
koardinat=array[1..maxn] of real;
var
x,y:koardinat;
k,n:integer;
x0,y0,x1,x2,y1,miny,maxy:real;

procedure VvodKoardinat (n:integer; var x,y:koardinat);
{procedura vvoda koardinat tochek}
var
i:byte;
fin:text;
begin
assign(fin,'L15_IN.txt');
reset(fin);
for i:=1 to n do
begin
read(fin,x[i]);
end;
readln(fin);
for i:=1 to n do
begin
read(fin,y[i]);
end;
close(fin);
end;

procedure VivodKoardinat (n:integer; x,y:koardinat);
{procedura vivoda koardinat tochek}
var
i:byte;
fout:text;
begin
assign(fout,'L15_23_OUT.txt');
rewrite(fout);
for i:=1 to n do
begin
write(fout,x[i]2.gif2,' ');
end;
writeln(fout);
for i:=1 to n do
begin
write(fout,y[i]2.gif2,' ');
end;
close(fout);
end;

procedure sortirovka(var x,y:koardinat; n:integer);
{procedura sortirovki koardinat tochek v poryadke neubivaniya x-vih
koardinat, esli x odinakovi, to v poryadke neubivaniya y-vih koardinat,
ispol'zuem lineinuyu sortirovku po nevozrastaniyu}
var
i,j:byte;
buf,buf1,buf2:real;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if x[i]<x[j] then
begin
buf:=x[i];
x[i]:=x[j];
x[j]:=buf;
buf1:=y[i];
y[i]:=y[j];
y[j]:=buf1;
end;
if (x[i]=x[j]) and (y[i]<y[j]) then
begin
buf2:=y[i];
y[i]:=y[j];
y[j]:=buf2;
end;
end;
end;

procedure srednyaya_tochka(var x0,y0:real; var k:integer; x,y:koardinat;n:integer);
{pricedura nahogdeniya koardinati srednei tochki}
begin
k:=n div 2+1;
x0:=x[k];
y0:=y[k];
end;

procedure tochki(var x1,x2,y1:real; x,y:koardinat; n,k:integer; x0,y0:real);
{procedira nahogdeniya dopolnitelnih tochek}
var
i,j,l:integer;
begin
i:=k;
if x[i-1]<>x0 then {nahodim x1}
x1:=x0-1
else
begin
while x[i]=x0 do
i:=i-1;
if i=0 then
x1:=x0-1
else
x1:=x[i];
end;
j:=k; {nahodim x2}
if x[j+1]<>x0 then
x2:=x0+1
else
begin
while x[i]=x0 do
i:=i+1;
if i=n+1 then
x2:=x0+1
else
x2:=x[i];
end;
{nahodim y1}
l:=k;
if x[l-1]<>x0 then
y1:=y0-1
else
y1:=y[l-1];
end;


procedure MinMaxY (var maxy,miny:real; y:koardinat; n:integer);
{procedura nahogdeniya min i max y koardinati}
var
i:integer;
begin
maxy:=y[1];
miny:=y[1];
for i:=1 to n do
begin
if y[i]>maxy then
maxy:=y[i]
else
if y[i]<miny then
miny:=y[i];
end;
end;

procedure uravnenie_pryamoi(x1,x2,y1,x0,y0,miny,maxy:real);
{nahogdenie uravneniya pryamoi i vivod ego v fail}
var
z,a,b,m1,m2,l1,l2:real;
fout:text;
begin
a:=x0-x1;
b:=x2-x0;
if a<=b then
z:=a
else
z:=b;
m1:=x0;
l1:=(y0+y1)/2;
m2:=x0+z/2;
l2:=y0-maxy+miny;
assign (fout,'L15_23_OUT.txt');
append (fout);
writeln(fout,' ');
writeln(fout,'Uravnenie pryamoi zadannoe dvumya tochkami');
writeln (fout,'x-',m1:2:0,'/',m2:2:0,'-',m1:2:0,'= y-',l1:2:0,'/',l2:2:0,'-',l1:2:0);
close(fout);
end;

begin
writeln ('vvedite n - chetnoe kolichestvo tochek');
repeat
readln(n);
until n mod 2=0;
x1:=0;x2:=0;y1:=0;miny:=0;maxy:=0;k:=0;
VvodKoardinat (n,x,y);
Sortirovka(x,y,n);
VivodKoardinat (n,x,y);
srednyaya_tochka(x0,y0,k,x,y,n);
tochki(x1,x2,y1,x,y,n,k,x0,y0);
MinMaxY (maxy,miny,y,n);
uravnenie_pryamoi(x1,x2,y1,x0,y0,miny,maxy);
end.

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

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

 





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