Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.69
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
#1

Разбиения множества - C++

18.05.2012, 19:38. Просмотров 4817. Ответов 82
Метки нет (Все метки)

Добрый вечер.
У меня есть множество точек в трехмерном пространстве, которые я считала и занесла в двухмерный массив. Задача состоит в том, чтобы рассмотреть все разбиения этого множества на два и сравнить их центры тяжести. Но как сравнить я знаю, а вот как разбить понятия не имею.
Например, если у меня три точки, то должно получится три варианта разбиения. Программирую на Си.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2012, 19:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Разбиения множества (C++):

Число изъять из множества А, если оно является элементом множества А, но не является элементом множества В - C++
Введено с клавиатуры число изъять из множества А, если оно является элементом множества А, но не является элементом множества В. ...

Функция разбиения матрицы на две - C++
Доброго времени суток уважаемые форумчане. Столкнулся с проблемой. Необходимо написать функцию разбиения матрицы на две матрицы, в качестве...

Алгоритм разбиения массива на подмассивы - C++
Здравствуйте, помогите написать алгоритм есть массив элементов А вычисляются значения А10 А21 А20 ...

Программа разбиения строк на слова - C++
Привет всем. Прошу объяснить фрагмент когда строк 23-26 в данной программе #include<iostream> #include<cstdio> #include<locale> ...

Функция разбиения строки в части [C++] - C++
Всем доброго времени суток. Нужно написать условие, который разделит (через точки) строку line на lname, fname, mname Например: ...

Множества. Вычислить количество элементов множества Q, связанного c исходными множествами - C++
В общем задание звучит так : Заданы 3 упорядоченных множества F, G и H, представленные файлами f, g и h соответственно. Вычислить...

82
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
18.05.2012, 20:33 #2
Логическая схема:
Перебираем все числа m от 1 до n-1, где n -- количество точек
Для каждого m перебираем все комбинации из m точек таким образом:
Перебираем все точки, и для каждой из них комбинации из m-1 точки (рекурсия).
Итого, получили разбиение на m и n-m точек
0
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
18.05.2012, 20:50  [ТС] #3
Цитата Сообщение от UFO94 Посмотреть сообщение
Перебираем все точки, и для каждой из них комбинации из m-1 точки (рекурсия).
Вот это не совсем понятно...
0
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
18.05.2012, 20:57 #4
В каком виде вы собираетесь хранить комбинацию?
0
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
18.05.2012, 21:07  [ТС] #5
UFO94, в итоге мне нужно будет вывести номера точек первого и второго множества. Но можно вывести и координаты самих точек, что мне кажется более проблематично.
0
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
18.05.2012, 21:34 #6
Можно и номера. Тогда это выглядит так:
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
void grouping(int n, int m,int m1, int* num)//num -- массив номеров точек, которые уже вошли в комбинацию, m1 -- их количество
{
if(m1==0)
{
for(int i=1; i<n-m+1; i++)//Это все частный случай того, что начинается через 2 else, добавлено для первого вызова функции, когда у нас еще пуст массив num
{
int* num1=new int[1];
num1[0]=i;
grouping(n,m,1,num1);
delete num1;
}
}
else if(m==m1)
{
//Здесь делаем расчеты центров масс частей и т.д., 1-я группа -- частицы, номера которых в массиве num, 2-я -- остальные.
}
else
{
int last=num[m1-1];//У нас частицы упорядочены, и если у нас уже была комбинация из 1,3,4 частицы, например, то комбинация из 1,4,3 нас уже не интересует, потому новые частицы имеет смысл присоейдинять к комбинации только начиная с num[m1-1]
for(int i=last+1; i<n-m+m1+1; i++)//Если номер будет больше, чем n-m+m1+1, то опять-таки комбинации будут повторяться
{
int* num1=new int[m1+1];
for(int j=0; j<m1; j++)
num1[j]=num[j];
num1[m1]=i;
grouping(n,m,m1+1,num1);
delete num1;
}
}
}
Вроде так. Компилировать не пробовал, экспромт, потому очень удивлюсь, если будет работать без ошибок. Пробуйте, пишите, будем разбираться.
Ах, и да, что пишем в основной программе:
C++
1
2
3
4
5
6
int n1=(n+1)/2;
for(int i=1; i<n1; i++)
{
int* num=new int[1];
grouping(n,i,0,num);
}
И есть одна проблемма, если n -- четное, то каждое разбиение пополам будет считаться дважды. Не знаю, как это исправить...
0
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
19.05.2012, 06:03  [ТС] #7
UFO94, я вот тут подумала, что можно было бы комбинировать не целые точки, а массы этих точек, а потом просто в принтф писать номера строк массива с точками, которые будут совпадать с номерами масс.
0
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
19.05.2012, 11:37 #8
Если вы собираетесь рассмотреть все возможные комбинации, то это одно и то же.

Не по теме:

Кстати, это вы проверяете независимость положения центра масс от разбиения?

0
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
19.05.2012, 12:34  [ТС] #9
UFO94, нет. Мне нужно найти разбиение на два множества, расстояние между центрами масс которых минимальное.
Просто как сделать так, чтобы он сам перебрал все варианты?
0
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
19.05.2012, 13:21 #10
Ну, мой алгоритм и будет перебирать все варианты. Придеться ввести глобальные переменные "расстояние" и "разбиение", и все ок.
0
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
19.05.2012, 16:22  [ТС] #11
UFO94, Ваш алгоритм кажется мне каким-то сложным %) Я думала, что через for можно как-то сделать
0
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
19.05.2012, 16:31 #12
Тогда для каждого m прийдется писать свою функцию. Т.е., у нас например 10 точек. Для выбора 1 точки пишем 1 for. Для 2-х точек -- 2. Для 5 точек пожалуйте 5 for'ов. Здесь без рекурсии ну никак не обойтись. Другое дело, что, возможно, это не самый рациональный алгоритм... По крайней мере, по использованию памяти. Он использует m(m+1)*sizeof(int)/2 памяти, что при m=23 составляет больше мегабайта оперативной памяти.
0
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
19.05.2012, 21:16  [ТС] #13
UFO94, а можете тогда еще раз объяснить рекурсию, пожалуйста.
0
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
19.05.2012, 21:57 #14
Рекурсивная функция -- функция, вызывающая саму себя. Как это в данном случае работает:
мы перебираем по очереди точки (т.е. выбираем 1 точку), а потом сводим задачу к предидущей -- теперь нам нужно выбрать m-1 точку из принципиально возможных n-1. Когда мы выбрали все нужные нам m точек (условие m1==m, это т.н. "выход из рекурсии"), мы уже получили разбиение -- одна группа точек -- те точки, чьи номера входят в массив num, вторая -- те, чьи номера туда не входят.
Есть 2 тонких момента во всем этом. Во первых, нам нету смысла расматривать такие разбиения, которые отличаются только порядком выбора точек (например разбиение с выбраным на первом шаге номером 1, на втором -- 2, на третьем -- 3, и разбиение с выбраным на первом шаге номером 2, на втором -- 3, и на третьем -- 1 для нас одинаковы (разбиения [1;2;3] и [2;3;1])). Потому имеет смысл каждую точку выбирать не из всех еще не вошедших в наш массив, а из тех, у которых номер больше номера последней точки. Таким образом, массив num получается отсортированным по нарастанию. Также очевидно, что если нам нужно выбрать 3 точки из 10, то выбрав на первом шаге точку №9 мы уже никак не сможем выбрать еще 2 точки с большими номерами, потому мы выбираем точки не от последней выбраной до последней вообще, а от последней выбраной до n-m+m1+1. И еще 1 момент, нам надо как-то начать этот рекурсивный процесс. За начало отвечает условие if(m1==0) и то, что там внутри. Кстати, я придумал лучший способ использования памяти, для этого в функции grouping:
--Убираем строки 7,10,22-24,27
--В строках 8,9,25,26 меняем num1 на num.
В вызове из основной программы:
-- в четвертой строке 1 меняем на i.
И алгоритм будет жрать память как корень квадратный из того, что жрал раньше
1
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
20.05.2012, 06:11  [ТС] #15
Цитата Сообщение от UFO94 Посмотреть сообщение
Когда мы выбрали все нужные нам m точек (условие m1==m
То есть чтобы он перебрал все варианты комбинаций точек нужно еще на это цикл наложить?

А не проще будет все-таки комбинировать массы точек, а потом уже сопоставлять с точками?
0
20.05.2012, 06:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2012, 06:11
Привет! Вот еще темы с ответами:

Реализация разбиения числа с Динам. Прогр - C++
Доброго времени суток. Нужна помощь: как с помощью динамического программирования реализовать решение такой вот задачи: &quot;найти...

Функция разбиения строки на отдельные слова - C++
Подскажите, плиз, как написать функцию разбиения строки на отдельные слова. Параметр функции — исходная строка, результат работы —...

Квадрат с вершинами из первого множества накрывает все точки второго множества и имеет минимальную площадь - C++
Даны два множества точек на плоскости. Выбрать четыре различных точки первого множества так, чтобы квадрат с вершинами в этих точках...

Множества . Найти разность полученного множества с заданным - C++
Всем доброго времени суток! Необходима ваша помощь. Никак не могу сделать второй пункт задачи.Суть задачи-найти 1)объединение множества...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru