Страница 1 из 1

Рекурсия с возратом

Добавлено: 22 мар 2009, 19:02
HoLToFF
Доброго времени суток :)

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

Изначально задача имела такой вид:
Рекурсия с возвратом.
Найти минимальное множество прямых, на которых можно разместить все точки заданного множества.
Сделать в консоли.

Но потом было решено задачу упростить и свести к такой:
Найти 2 прямые, проходящие через точку i, на которых размещаются наибольшее количество точек заданного множества.
Сделать в консоли.
Уравнение прямой взять как ах+ву=0
Вывести 2 массива, первый массив - точки, лежащие на одной прямой, второй - точки, лежащие на второй прямой.
Точки заданного множества вводятся пользователем. Можно решить с помощью массива записей.

Желательно сделать любой вариант.

Очень на вас надеюсь, с наилучшими пожеланиями :)

Re: Рекурсия с возратом

Добавлено: 26 мар 2009, 11:26
Хыиуду
Берем точку i и еще какую-нибудь точку, вычисляем a и b для уравнения прямой, смотрим, координаты каких точек еще попадают на эту прямую. Потом берем следующую точку из числа тех, которые не попали ни на какую из предыдущих прямых. Таким образом получаем несколько множеств точек, таких, что все точки одного множества лежат на одной прямой, содержащей точку i. Найти два самых больших множества, найти для них координаты прямых.

Re: Рекурсия с возратом

Добавлено: 26 мар 2009, 19:14
HoLToFF
Спасибо, алгоритм был уже придуман, а вот основная проблема в том, как это запрограммировать.

Re: Рекурсия с возратом

Добавлено: 26 мар 2009, 21:45
somewhere
Вот что будет нужно:

Код: Выделить всё

const nump = 10;

type
TPoint = record X,Y :D ouble; EqId: Integer; end;
TLineEq = record A,B: Double; refs: Integer; end;

var
I : TPoint;
Pts : Array[1..Nump] of TPoint;
Eqs : Array[1..Nump] of TLineEq;
EqID  : Integer;
NumEq : Integer;

function GetMeEqWithMaxRefCountLessThan(K:Integer):Integer;
begin
// do search max refs count through Eqs which ID <> K and puts it into result
end;

function GetEquationId(var E:TLineEq):Integer;
begin
// Do search through Eqs by E.A, E.B params, if they are identical then result = position, else result = 0;
end;

procedure CreateEquations;
var x, y:Integer; e: TLineEq;
begin
numeq := 0;
For x := 1 to nump do 
  begin
  e.A := .......... // Calc A
  e.B := .......... // Calc B
  e.Refs := 1;
  y := GetEquationID(E);
  If y = 0 then begin; inc(numeq); Eqs[numeq] := E; end
      else inc(Eqs[y].refs);
  end;
end;

begin
Clrscr;
InputPoints;
CreateEquations;
EqID := GetMeEqWithMaxRefCountLessThan(0);
DisplayEquation(Eqs[EqID]);
Eq := GetMeEqWithMaxRefCountLessThan(EqID);
DisplayEquation(Eqs[EqID]);
end;
Как все это работает:
1. Вводим значения точек.
2. Заполнеям Eqs в процедуре уравнениями прямых между точками из Pts и точкой I.
2.1. Если такое уравнение (А,В) уже есть, увеличим число ссылок на 1
3. Найдем ID уравнения с максимальным числом ссылок в Eqs
4. тоже самое, только чтобы ID <> предыдущему

Под ID уравнения подразумевается его позиция в массиве.
NumEq увеличивается динамически, и фактически отражает последний ID уравнения
Поле EqID оставлено в структуре TPoint если вдруг надо будет узнать точки, принадлежащие уравнению с заданным ID

Надеюсть недостающее без труда допишите сами, ибо там осталось, как бы не соврать, строк 10-15

Re: Рекурсия с возратом

Добавлено: 26 мар 2009, 21:52
HoLToFF
Большое спасибо!