Минимальное множество прямых (рекурсия с возвратом) Опции

[Даша]

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

[Lapp]

По коду в принципе всё понятно,

Даша, не обижайся, но.. не верится! )) Ответь на пару контрольных вопросов, чтоб меня в этом убедить..
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, если тебе нужна помощь.

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

А зачем? Чтоб растянуть удовольствие? )) Если чел начал изучать Delphi - пусть делает именно это, а не "как в Delphi рисовать _под_TP" ))