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

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

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

 
 Ответить  Открыть новую тему 
> Минимальное множество прямых (рекурсия с возвратом)
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

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


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


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

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

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


Цитата(Даша @ 17.04.2011 18:13) *
Всем доброго времени суток! Прошу помочь со следующей задачей: найти минимальное множество прямых, проходящих через все заданные точки. То есть заданы координаты точек и ответом должно быть число прямых. Не знаю как организовать перебор всех вариантов, очень прошу написать хотя бы в общем виде сам алгоритм.
И это нужно сделать с помощью рекурсии? В целом, ничего сложного, но есть непонятные моменты..

Допустим, точки заданы массивом (то есть, упорядочены). Делаешь процедуру, которая делает две вещи (либо/либо, как обычно в рекурсии):
1. Если точек 2 или больше, то берет следующую точку и проводит все прямые через нее и все остальные и добавляет их к списку, если их там еще нет; после этого "выкидывает" эту тучку из массива и вызывает себя же.
2. Если точка только одна - выходит.

Таким образом будут проведены все прямые. Смысл твоей задачи состоит в том, чтоб отсеять повторы, поэтому нужно всякий раз проверять, не включена ли прямая уже в список. А для этого нужно уметь уметь сравнивать прямые. Например, если две прямые заданы в виде y=ax+b, то они одинаковые, если a1 и b2 соответственно равны a2 и b2. Тут возникает оджин вопрос: как заданы координаты точек? Это действительные числа или целые? Действительные сравнивать несколько труднее..

Говори, что непонятно.


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


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

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


Цитата
Если точек 2 или больше, то берет следующую точку и проводит все прямые через нее и все остальные и добавляет их к списку, если их там еще нет;


Вот это как раз непонятно. Как организовать перебор ВСЕХ возможных вариантов расположения прямых?

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


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

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

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


Цитата(Даша @ 17.04.2011 23:10) *
Вот это как раз непонятно. Как организовать перебор ВСЕХ возможных вариантов расположения прямых?

Так рекурсия же! smile.gif Она все тебе переберет. Ты только сделай, как я написал выше.


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


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

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

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


Даша, я так понимаю, что у тебя особого прогресса нет - да?
Я вот набросал прожку. Посмотри ее..
Если честно, она мне не нравится. Что-то я к вечеру не смог ничего лучше придумать.. Рекурсия там в результате оказалась притянута за уши. Но все же она есть, и прога, вроде, считает. Я проверил на простых конфинурациях до 6 точек )). Проверь получше, если найдешь ошибки - говори.

const
m= 100;
e= 1e-7;

type
tPoint= record
x,y: double;
end;

var
p: array [1..m] of tPoint;
Lines,n: integer;
f: text;

function Eq(a,b: tPoint): boolean;
begin
Eq:= (a.x=b.x) and (a.y=b.y)
end;

function Aligned(a,b,c: tPoint): boolean;
var
d: tPoint;
begin
if a.x=b.x then begin
d:= a;
a:= c;
c:= d
end
else if a.x=c.x then begin
d:= a;
a:= b;
b:= d
end;
Aligned:=
Eq(a,b) or
Eq(b,c) or
Eq(c,a) or
(a.x=b.x) and (a.x=c.x) or
(Abs((b.y-a.y)/(b.x-a.x)-(c.y-a.y)/(c.x-a.x))<e)
end;

procedure Count(k: integer);
var
i,j: integer;
begin
for i:=k+1 to n do begin
j:= 1;
while (j<i) and not Aligned(p[k],p[i],p[j]) or (j=k) do Inc(j);
if j=i then begin
WriteLn(p[k].x:5:0,p[k].y:5:0,' ',p[i].x:5:0,p[i].y:5:0);
Inc(Lines)
end
end;
if k<n then Count(k+1)
end;

begin
Assign(f,'dasha.dat');
Reset(f);
n:= 0;
while not EoF(f) do begin
Inc(n);
ReadLn(f,p[n].x,p[n].y)
end;
Close(f);
Lines:= 0;
Count(1);
WriteLn(Lines);
ReadLn
end.

Входные данные задаются в текстовом файле dasha.dat, по одной точке на строку. Координаты можно задавать действительными числами, но я пока только целые давал. Вот пример:
0 0
4 0
0 4
4 4
2 2
3 3

Заметь, что в конце НЕ ДОЛЖНО быть пустых строк (то есть курсор стрелками дальше последней строки не должен заходить). На этом примере ответ 8.

Пиши, что непонятно, я попробую объяснить smile.gif.


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


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

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


Прощу прощения за то что долго не отвечала, не было возможности. Но вы правы, прогресса нет, ибо хотела задать вопрос: понятно что рекурсия будет перебирать все возможные варианты, но непонятно как она будет брать, допустим, четыре точки. Ведь у нас могут лежать четыре точки на одной прямой. И, например, программа возьмет первые две, а затем две другие. Получается надо будет каждый раз где нибудь в массиве запоминать K и B, а затем при высчитывании очередных коэффициентов сравнивать их с уже посчитанными?

За код больщущее спасибо smile.gif . Только вы наверное не до конца разобрались в условии. Необходимо найти МИНИМАЛЬНОЕ множество прямых, на которых будут лежать все точки. То есть, например, для ваших точек ответ должен быть не 8, а 2. Но, насколько я понимаю, необходимо просто в ваш код добавить дополнительную переменную min, и где нибудь в программе переменную Lines каждый раз сравнивать с min?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


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

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

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


Цитата(Даша @ 19.04.2011 22:20) *
Прощу прощения за то что долго не отвечала, не было возможности. Но вы правы, прогресса нет, ибо хотела задать вопрос: понятно что рекурсия будет перебирать все возможные варианты, но непонятно как она будет брать, допустим, четыре точки. Ведь у нас могут лежать четыре точки на одной прямой. И, например, программа возьмет первые две, а затем две другие. Получается надо будет каждый раз где нибудь в массиве запоминать K и B, а затем при высчитывании очередных коэффициентов сравнивать их с уже посчитанными?
Рекурсия - это в некотором смысле способ хранения большого множества параметров в стеке. Хотя, можно это сочетать и с глобальными массивами.

Цитата
За код больщущее спасибо smile.gif . Только вы наверное не до конца разобрались в условии. Необходимо найти МИНИМАЛЬНОЕ множество прямых, на которых будут лежать все точки. То есть, например, для ваших точек ответ должен быть не 8, а 2. Но, насколько я понимаю, необходимо просто в ваш код добавить дополнительную переменную min, и где нибудь в программе переменную Lines каждый раз сравнивать с min?
Да, ты права, я неверно понял условие.. Я думал, что надо провести прямую через каждую пару точек, но при этом не учитывать повторения. Оказывается, все иначе..

Нет, простой доделкой кода тут не обойтись. Нужно менять всю схему.. Надеюсь, можно будет по крайней мере использовать функции Eq и Aligned. Я немного еще освобожусь и попробую сделать (если никто раньше не сделает))..

А задачка оказалась интереснее, чем я думал! ))


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


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

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

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


Вот. Выстругал буратинку )).
Но снова она мне не по нутру.. Думаю, можно сделать намного красивее.. Может, кто-нить сделает. Я тоже еще подумаю..

Да, как я сказал, пришлось переделать всю схему перебора. Коротко могу изложить так..
Один вызов Draw (от слова рисовать линию) рисует одну линию в цикле по всем парам точек (в двойном цикле). Нарисовав линию, он проверяет, какие точки она еще задела. Все задетые точки заносит в массив Co (Covered). Затем вызывает вторую (следующую) копию. Когда массив Co заполнен до конца (это проверяется при входе в Draw), она смотрит, сколько проведено линий (Lin). Если это число меньше, чем MinLin - обновляет MinLin. Вот, примерно так.

Ты посмотри прогу и задавай конкретные вопросы. Работает она, похоже, верно, но.. оооочень медленно. То есть массив из 9 точек обсчитывался на моей тачке почти минуту. При этом время растет с числом точек стремительно (думаю, приблизительно по факториалу). Поэтому 10 точек будет считаться гораздо дольше.. Ускорить можно оптимизацией (возможностей куча), но от характера зависимоти не уйти, думаю (но подумаю еще)).

Короче, вот тебе код. Разбирайся и задавай вопросы.
const
m= 100;
e= 1e-7;

type
tPoint= record
x,y: double;
end;
tCo= array [1..m] of boolean;

var
p: array [1..m] of tPoint;
Co: tCo;
n,Lin,MinLin: integer;
f: text;


function Eq(a,b: tPoint): boolean;
begin
Eq:= (a.x=b.x) and (a.y=b.y)
end;


function Aligned(a,b,c: tPoint): boolean;
var
d: tPoint;
begin
if a.x=b.x then begin
d:= a;
a:= c;
c:= d
end
else if a.x=c.x then begin
d:= a;
a:= b;
b:= d
end;
Aligned:=
Eq(a,b) or
Eq(b,c) or
Eq(c,a) or
(a.x=b.x) and (a.x=c.x) or
(Abs((b.y-a.y)/(b.x-a.x)-(c.y-a.y)/(c.x-a.x))<e)
end;


procedure Draw;
var
i,j,k: integer;
b: boolean;
c: tCo;
begin
b:= false;
for i:=1 to n do b:= b or not Co[i];
if b then
for i:=1 to n do begin
b:= Co[i];
Co[i]:= true;
for j:=1 to n do if (i<>j) and not Co[j] then begin
c:= Co;
Co[j]:= true;
Inc(Lin);
for k:=1 to n do
if (k<>i) and (k<>j) then Co[k]:= Co[k] or Aligned(p[i],p[k],p[j]);
Draw;
Dec(Lin);
Co:= c
end;
Co[i]:= b
end
else
if Lin<MinLin then MinLin:= Lin
end;


begin
Assign(f,'dasha.dat');
Reset(f);
n:= 0;
while not EoF(f) do begin
Inc(n);
ReadLn(f,p[n].x,p[n].y);
Co[n]:= false
end;
Close(f);
MinLin:= MaxInt;
Lin:= 0;
Draw;
WriteLn(MinLin);
ReadLn
end.

Формат входного файла тот же. Вот на этом выдает 3.
0 0
4 4
0 4
4 0
3 3
2 2
1 1
3 1
4 1



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


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

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


Еще раз выражаю огромную благодарность smile.gif
По коду в принципе всё понятно, за исключением
e= 1e-7;

понятно что это константа, но почему она так задается, и вообще про подобное задание констант, если можно, расскажите, а то в университете про такое не рассказывали)
От роста времени думаю избавиться не удастся, хотя наверное, оптимизировать немного всё же можно, но для меня главное понимание принципа работы подобного алгоритма, а это с успехом достигнуто).

И еще небольшой вопросик не совсем в тему: мне необходимо сделать эту задачу на Delphi в визуальной среде, но решила для начала основу отладить в Паскале, а потом перенести всё это в визуальную среду. Не подскажите где можно прочитать про работу с компонентом TImage в Delphi 7? Мне необходимо будет нарисовать все точки, и собственно, сами прямые, которые покрывают все эти точки.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






А разве для быстрого переноса Паскальных программ на Дельфи не придумали модуль, который реализует все процедуры модуля Graph через создание формы нужного размера и рисование на ней?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


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

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

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


Цитата(Даша @ 20.04.2011 17:28) *
По коду в принципе всё понятно,
Даша, не обижайся, но.. не верится! )) Ответь на пару контрольных вопросов, чтоб меня в этом убедить..
1. Зачем каскадный IF (строки 28-37) в функции Aligned?
2. Зачем "if (i<>j) and not Co[j]" (оба условия) в строке 59?
3. Почему Co[i] вычисляется через OR с самим собой (строка 64)?
4. ...
Если ты можешь ответить - тогда да, понятно )). Если нет - то нет.. ((

Цитата
за исключением
e= 1e-7;

понятно что это константа, но почему она так задается, и вообще про подобное задание констант, если можно, расскажите, а то в университете про такое не рассказывали)
Это ОООЧЕНЬ странно, что вам не рассказывали про константы. Именованные константы - это очень распространенная и полезная концепция программирования. Я объясню на прмере..

Допустим, ты делаешь прогу.. ну, скажем, модель дорожного движения. Там у тебя машинки ездят всякие.. И у них есть такой параметр, как скорость - у каждого своя в каждый момент времени. Эта скорость должна контролироваться на предмет не превышения максимальной допустимой (я правлиьно сказал? короче, speed limit)). Эта проверка осуществляется в разных местах программы. Speed limit в городе - 60 км/ч. Ты можешь в каждой проверке употребить непосредственно это число, типа так:
  if (Speed>60) and CopIsAround  then Cite;

Но завтра Дума (депутаты которой очень любят кататься выпускать законы на эту тему) поднимет этот предел до 70 (или опустит до 50, что более вероятно). И тогда тебе придется отыскивать ВСЕ проверки и заменять в них 60 на 70 (или 50). Причем, нет гарантии, что ты что-то не пропустишь (или автоматом не заменишь название улицы "60 Street" на "70 Street")). Чтобы облегчить себе задачу и избежать таких казусов, существуют те самые константы. Ты объявляешь в разделе констант:
const
TownSpeedLimit = 60;

А потом, если потребуется изменить этот предел, тебе нужно это сделать только в одном месте - причем, оно в начале проги! А если одновремено нужно изменить и предел скорости на автобане - пожалуйта, константа FreewaySpeedLimit на следующей строчке!

Что происходит на самом деле на этапе компиляции (в Pascal)? Реально компилятор НЕ ЗАВОДИТ дополнительную память под константу (как под переменную), а просто подставляет вместо нее ее реальное значение при каждом вхождении. То есть, грубо говоря, скомпилированный код (выполняемый, то есть exe) будет неотличим в вариантах С константами и БЕЗ них.

Я понятно объяснил? По первости может показаться, что это пустая трата времени и тайпинга, но потом увидишь, что константы экономят очень много - как времени, так и всего остального. К тому же, если давать им значащие имена, то это сильно поможет тебе ориентироваться в коде.

В данном случае, константа e - это сокращение от Epsilon. Смысл ее - точность при стравлении действительных чисел. Ты же знаешь, что компьютер производит вычисления с определенной точностью. И в результате вычислений, например, Sqrt(Sqr(3)+Sqr(4)), получится не 5, а типа 5.0000002 или 4.9999997. Эти ответы - правильные. Но если ты будешь проверять их правильность так:
Correct:= Res=5;

- то ты получишь отрицательный ответ (т.е., неправильно). Поэтому нужно сравнивать так:
Correct:= Abs(Res-5)<e;

, где e - это та самая точность.
Именно это я и делаю в функции Aligned при проверке попадания точки на прямую.

Цитата
От роста времени думаю избавиться не удастся, хотя наверное, оптимизировать немного всё же можно, но для меня главное понимание принципа работы подобного алгоритма, а это с успехом достигнуто).
Оч.хор. ))
Попробуешь оптимизировать?

Цитата
И еще небольшой вопросик не совсем в тему: мне необходимо сделать эту задачу на Delphi в визуальной среде, но решила для начала основу отладить в Паскале, а потом перенести всё это в визуальную среду. Не подскажите где можно прочитать про работу с компонентом TImage в Delphi 7? Мне необходимо будет нарисовать все точки, и собственно, сами прямые, которые покрывают все эти точки.
Во первых, компонент TImage тут не совсем при чем.. Для рисования с использованием примитивов (точки, линии..) тебе лучше для начала посмотреть в сторону TCanvas, мне кажется, чтобы прочувствовать все на низком уровне доступа к окну. А где прочитать - думаю, в книжке )). В России книг по Delphi на порядок больше, чем тут, так что конкретнее советовать не буду.

И еще: ты права, это выходит за пределы и темы, и раздела. Создай новую тему в разделе про Delphi, если тебе нужна помощь.

Цитата(-TarasBer- @ 20.04.2011 20:19) *
А разве для быстрого переноса Паскальных программ на Дельфи не придумали модуль, который реализует все процедуры модуля Graph через создание формы нужного размера и рисование на ней?
А зачем? Чтоб растянуть удовольствие? )) Если чел начал изучать Delphi - пусть делает именно это, а не "как в Delphi рисовать _под_TP" ))


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


Гость






> А зачем? Чтоб растянуть удовольствие?

Для быстрого переноса Паскальных программ, и чтобы при этом не забивать голову ВинАПИ и не портить себя формошлёпством.

> Это ОООЧЕНЬ странно, что вам не рассказывали про константы. Именованные константы - это очень распространенная и полезная концепция программирования. Я объясню на прмере..

Мне кажется, она удивлена экспоненциальной записью.

На самом деле, 1e-7 это 10^(-7) = 1/10 000 000

То есть если в конце числа стоит "е" а потом ещё число, значит то, что до этого "е" надо умножить на 10 в степени того, что после этого "е".
Например: 2е-3 = 2*10^(-3) = 2/1000 = 0.002
1.0034e4 = 1.0034 * 10^4 = 1.0034 * 10000 = 10034
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

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


Что же, попробую ответить на ваши вопросы:

1. Чтобы при выполнении первого условия, т.е a.x=b.x, второе условие a.x=c.x не проверялось
2. Чтобы брать те точки, которые не были задеты массиве Co[i] и Со[j]
3. Вот тут да, честно, не очень понятно, хотелось бы объяснений немного.

Цитата
Попробуешь оптимизировать?

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

Цитата
Мне кажется, она удивлена экспоненциальной записью.

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


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

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

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


Цитата(-TarasBer- @ 21.04.2011 14:35) *
Для быстрого переноса Паскальных программ, и чтобы при этом не забивать голову ВинАПИ и не портить себя формошлёпством.
Я сомневаюсь, чтоб у Даши было много програм для переноса.. А к Graph'овская графике тоже не следует себя приучать, мне кажется.

Цитата
Мне кажется, она удивлена экспоненциальной записью.
Садовая моя башка lol.gif. Я все не так понял..

Цитата(Даша @ 21.04.2011 18:13) *
1. Чтобы при выполнении первого условия, т.е a.x=b.x, второе условие a.x=c.x не проверялось
Это ты просто описала действие поля else в операторе if. Ну и что? А зачем нужно это? С точки зрения алгоритма решения.

Цитата
2. Чтобы брать те точки, которые не были задеты массиве Co[i] и Со[j]
Я не понял, что ты хотела сказать. Не задеты в массиве? Но почему присутствуют индексы i и j?.. Выражайся точнее, пожалуйста.

Цитата
3. Вот тут да, честно, не очень понятно, хотелось бы объяснений немного.
Будет не объяснение, а совет. Если тебе что-то непонятно в программе - экспериментируй. Возьми очень простую конфигурацию входных данных (сначала просто две точки, если не прояснится - 3, и т.д.) и попробуй УБРАТЬ условие, которое тебе неясно, что делает. И посмотри, как это отразится на результатах работы программы. Проанализируй эти результаты.

Цитата
Ды с удовольствием бы попробовала, ..
Ладно, я не настаиваю )). Хорошо, что у тебя вообще есть интерес.


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

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

 





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