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

[Даша]

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

[Даша]

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

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

[Lapp]

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

Рекурсия - это в некотором смысле способ хранения большого множества параметров в стеке. Хотя, можно это сочетать и с глобальными массивами.

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

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

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

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