Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 14
1

Перечислить все различные максимальные подмножества точек, лежащих на одной прямой

08.12.2013, 13:47. Показов 2163. Ответов 9
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый день
Хочу попросить форумчан в составлении алгоритма, ибо самому не получается

Задача:
Задано множество точек на плоскости. Перечислить все различные максимальные подмножества точек, лежащих на одной прямой, которые содержат более 2х точек.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.12.2013, 13:47
Ответы с готовыми решениями:

Найти все подмножества точек, лежащих на одной прямой
на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой....

Найти в бинарном файле все пары точек, лежащих с точкой d на одной прямой
В файле заданы множество точек А и точка d вне его. Найти все пары точек, лежащих с точкой d на...

Из заданного мн-ва точек на плоскости выбрать две различные точки так, чтобы количества точек, лежащих по разные стороны прямой, было равно.
Программный модуль! Из заданного мн-ва точек на плоскости выбрать две различные точки так, чтобы...

Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н
Я подумала, что нужно будет написать класс Point. Немного написала, и остановилась на методе,...

9
Заблокирован
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
Насколько я понимаю то, что читаю:
Цитата Сообщение от siggy-sandro Посмотреть сообщение
максимальные подмножества точек, лежащих на одной прямой, которые содержат более 2х точек.
т.е., максимальное подмножество - любое, в котором больше 2-х точек.

Проблема не в этом. Проблема в выявлении (и уничтожении) повторяющихся множеств. Если ее решить, то останутся только уникальные максимальные подмножества.

Добавлено через 2 минуты
Цитата Сообщение от siggy-sandro Посмотреть сообщение
механизм перебора может быть такой
Этот алгоритм имеет порядок 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
Заблокирован
08.12.2013, 15:28 8
Цитата Сообщение от IrineK Посмотреть сообщение
При условии, что в строке более 3 единиц,
Поправочка: не менее 3 единиц.
0
Заблокирован
09.12.2013, 10:57 9
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/*Задано множество точек на плоскости. Перечислить все 
различные максимальные подмножества точек, лежащих на 
одной прямой, которые содержат более 2х точек.
*/
#include <stdio.h>
#include <stdlib.h>
 
struct POINT
{   int x,y;
};
 
/*============ создаем подмножества точек, лежащих на одной прямой ========*/
void FillSets (int **sets, POINT **p, int N, int M)
{   int i, j, m = 0, k;
    for (i = 0; i<N-1; i++)
        for (j = i+1; j<N; j++, m++)
        {   for (k = 0; k<N; k++)
                if((p[k]->x - p[i]->x) * (p[j]->y - p[i]->y) == (p[k]->y - p[i]->y)*(p[j]->x - p[i]->x))
                    sets[m][k] = 1;
        }
}
 
/*================= вывод всех подмножеств на консоль =====================*/
void ShowSets (int **sets, int N, int M)
{   int i,j;
    printf("Subsets created:\n");
    for (i = 0; i<M; i++)
    {   for (j = 0; j<N; j++)
            printf("%5d", sets[i][j]);
        printf("\n");
    }
    printf("\n");
}
 
/*================= проверка двух подмножеств на равенство ================*/
int SetsAreEqual (int *set1, int *set2, int N)
{   int i= 0;
    while (i<N)
        if (set1[i] != set2[i])
            return 0;
        else
            i++;
    return 1;
}
 
/*============= удаление подмножества (зануление всех членов) ==============*/
void EraseSet (int *set, int N)
{   int i = 0;
    while (i<N)
        set[i++] = 0;
}
 
/*======================= оставляем только уникальные наборы ================*/
void LeaveUniques (int **sets, int N, int M)
{   int i,j;
    for (i = 0; i<M-1; i++)
        for (j = i+1; j<M; j++)
            if (SetsAreEqual (sets[i], sets[j], N))
                EraseSet (sets[j], N);
}
 
/*========= выводим максимальные подмножества (к-во точек не менее трех) ======*/
void Results (int **sets, int N, int M)
{   int i, j, sum;
    printf("Maximum subsets found for these points:\n\n");
    for (i = 0; i<M; i++)
    {   for (j = 0, sum = 0; j<N; j++)
            sum += sets[i][j];
        if (sum > 2)
        {   for (j = 0; j<N; j++)
                if (sets[i][j])
                    printf("%5d", j);
            printf("\n");
        }
    }
}
 
 
int main() 
{   /*на входе - файл с данными: в первой строке N
    дальше - в каждой строке пара чисел - координаты точек
    */
    FILE *in = fopen("data.txt", "r");
    int N, i = 0, j, **sets, M;
    char buf[20];
    
    fgets(buf, 20, in);
    sscanf(buf, "%d", &N);
    POINT **p = (POINT**) malloc (N * sizeof(POINT*));
    while(i<N)
        p[i++] = (POINT*) malloc(sizeof(POINT));
    
    i = 0;
    while(i<N)
    {   fgets(buf, 20, in);
        sscanf(buf, "%d%d", &(p[i]->x), &(p[i]->y));
        i++;
    }
    
    /*данные считаны. Приступаем к созданию подмножеств точек, 
    лежащих на одной прямой
    */
 
    M = N*(N-1)/2;
    sets = (int**) malloc (M * sizeof(int*));
    i = 0;
    while(i<M)
        sets[i++] = (int*) malloc (N * sizeof(int));
 
    for (i = 0; i<M; i++)
        for (j = 0; j<N; j++)
            sets[i][j] = 0;
 
    FillSets (sets, p, N, M);
    ShowSets (sets, N, M);
    /*подмножества созданы. Удаляем повторяющиеся
    */
    LeaveUniques (sets, N, M);
 
    /*выводим результат
    */
    Results (sets, N, M);
 
    i = 0;
    while(i<M)
        free (sets[i++]);
    free (sets);
    
    i = 0;
    while(i<N)
        free (p[i++]);
    free (p);
 
    fclose (in);
    getchar();
    return 0;
}
Миниатюры
Перечислить все различные максимальные подмножества точек, лежащих на одной прямой  
Изображения
 
1
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 14
09.12.2013, 11:30  [ТС] 10
Спасибо огромное за программу, сейчас буду сидеть и разбираться
0
09.12.2013, 11:30
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.12.2013, 11:30
Помогаю со студенческими работами здесь

Перечислить все подмножества n элементного множества {1,2,.,n}
Помогите пожалуйста написать программу для этой задачи: Перечислить все подмножества n элементного...

Перечислить все K элементные подмножества n элементарного множества
Перечислить все K элементные подмножества n элементарного множества пример с вводом выводом

Перечислить все K элементные подмножества n элементного множества
Например: есть множество 1, 2, 3 N=3, k=2, на выводе должны получить: 1 2 1 3 2 3

Перечислить все K элементные подмножества n элементарного множества
Перечислить все K элементные подмножества n элементарного множества пример и объяснение по этой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru