0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 14
|
|
1 | |
Перечислить все различные максимальные подмножества точек, лежащих на одной прямой08.12.2013, 13:47. Показов 2163. Ответов 9
Метки нет (Все метки)
Добрый день
Хочу попросить форумчан в составлении алгоритма, ибо самому не получается Задача: Задано множество точек на плоскости. Перечислить все различные максимальные подмножества точек, лежащих на одной прямой, которые содержат более 2х точек.
0
|
08.12.2013, 13:47 | |
Ответы с готовыми решениями:
9
Найти все подмножества точек, лежащих на одной прямой Найти в бинарном файле все пары точек, лежащих с точкой d на одной прямой Из заданного мн-ва точек на плоскости выбрать две различные точки так, чтобы количества точек, лежащих по разные стороны прямой, было равно. Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н |
Заблокирован
|
|
08.12.2013, 14:20 | 2 |
Берем две точки (х0, у0) и (х1, у1). Через них проводим прямую, уравнение которой:
(х - х0)(у1 - у0) = (у - у0)(х1 - х0) Значит, проверить, лежит ли еще какая-то точка (хi, yi) на этой прямой (третьей буш? ) очень просто. Для нее должно выполняться соотношение: (хi - х0)(у1 - у0) = (уi - у0)(х1 - х0) Теперь нужно подумать о механизме перебора, чтобы не повторяться.
0
|
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 14
|
|
08.12.2013, 14:45 [ТС] | 3 |
Ну механизм перебора может быть такой:
Сначала берем 1 и 2 точки, для них составляем уравнение прямой и проверяем все точки от 3 до n на принадлежность к ней. Затем 1 и 3 и так далее. Но в задании сказано, что нужно вывести максимальные подмножества точек Т.е. я так понимаю, если есть подмножества из 3х точек и из 4х, то нужно вывести только из 4х. И тут начинается проблема...
0
|
Заблокирован
|
|
08.12.2013, 15:01 | 4 |
Насколько я понимаю то, что читаю:
т.е., максимальное подмножество - любое, в котором больше 2-х точек. Проблема не в этом. Проблема в выявлении (и уничтожении) повторяющихся множеств. Если ее решить, то останутся только уникальные максимальные подмножества. Добавлено через 2 минуты Этот алгоритм имеет порядок N3. Это вас не смущает? Какое максимальное к-во точек планируется обрабатывать?
0
|
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 14
|
|
08.12.2013, 15:09 [ТС] | 5 |
Механизм сложный, но решение вполне может быть методом "перебора", это разрешается
Добавлено через 2 минуты Максимальное количество точек: не более 10-15.
0
|
Заблокирован
|
|
08.12.2013, 15:20 | 6 |
Для пары десятков точек можно себе позволить и куб )
Механизм при простом переборе не сложный. Если N - кво точек, то к-во пар при переборе C2N = N*(N-1)/2 При этом для каждой пары формируется подмножество, выбираемое из N-2 точек Получаем необходимость создать матрицу размерностью: N*(N-1)/2 (строки) на N (столбцы) Заполняем ее нулями. Нумерация столбцов соответствует нумерации точек. Если точка входит в данное подмножество, то в данной строке в соответствующем столбце выставляем 1. На этом формирование подмножеств закончено. Затем обрабатываем строки на уникальность. Повторения уничтожаем. При условии, что в строке более 3 единиц, выводим результат.
0
|
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 14
|
|
08.12.2013, 15:23 [ТС] | 7 |
Хм, ну вроде ясно
Спасибо, буду пытаться реализовать)
0
|
Заблокирован
|
||||||
09.12.2013, 10:57 | 9 | |||||
Сообщение было отмечено Памирыч как решение
Решение
1
|
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 14
|
|
09.12.2013, 11:30 [ТС] | 10 |
Спасибо огромное за программу, сейчас буду сидеть и разбираться
0
|
09.12.2013, 11:30 | |
09.12.2013, 11:30 | |
Помогаю со студенческими работами здесь
10
Перечислить все подмножества n элементного множества {1,2,.,n} Перечислить все K элементные подмножества n элементарного множества Перечислить все K элементные подмножества n элементного множества Перечислить все K элементные подмножества n элементарного множества Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |