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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.69
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
18.05.2012, 19:38     Разбиения множества #1
Добрый вечер.
У меня есть множество точек в трехмерном пространстве, которые я считала и занесла в двухмерный массив. Задача состоит в том, чтобы рассмотреть все разбиения этого множества на два и сравнить их центры тяжести. Но как сравнить я знаю, а вот как разбить понятия не имею.
Например, если у меня три точки, то должно получится три варианта разбиения. Программирую на Си.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
18.05.2012, 20:33     Разбиения множества #2
Логическая схема:
Перебираем все числа m от 1 до n-1, где n -- количество точек
Для каждого m перебираем все комбинации из m точек таким образом:
Перебираем все точки, и для каждой из них комбинации из m-1 точки (рекурсия).
Итого, получили разбиение на m и n-m точек
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
18.05.2012, 20:50  [ТС]     Разбиения множества #3
Цитата Сообщение от UFO94 Посмотреть сообщение
Перебираем все точки, и для каждой из них комбинации из m-1 точки (рекурсия).
Вот это не совсем понятно...
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
18.05.2012, 20:57     Разбиения множества #4
В каком виде вы собираетесь хранить комбинацию?
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
18.05.2012, 21:07  [ТС]     Разбиения множества #5
UFO94, в итоге мне нужно будет вывести номера точек первого и второго множества. Но можно вывести и координаты самих точек, что мне кажется более проблематично.
UFO94
 Аватар для UFO94
263 / 252 / 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 -- четное, то каждое разбиение пополам будет считаться дважды. Не знаю, как это исправить...
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
19.05.2012, 06:03  [ТС]     Разбиения множества #7
UFO94, я вот тут подумала, что можно было бы комбинировать не целые точки, а массы этих точек, а потом просто в принтф писать номера строк массива с точками, которые будут совпадать с номерами масс.
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
19.05.2012, 11:37     Разбиения множества #8
Если вы собираетесь рассмотреть все возможные комбинации, то это одно и то же.

Не по теме:

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

ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
19.05.2012, 12:34  [ТС]     Разбиения множества #9
UFO94, нет. Мне нужно найти разбиение на два множества, расстояние между центрами масс которых минимальное.
Просто как сделать так, чтобы он сам перебрал все варианты?
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
19.05.2012, 13:21     Разбиения множества #10
Ну, мой алгоритм и будет перебирать все варианты. Придеться ввести глобальные переменные "расстояние" и "разбиение", и все ок.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
19.05.2012, 16:22  [ТС]     Разбиения множества #11
UFO94, Ваш алгоритм кажется мне каким-то сложным %) Я думала, что через for можно как-то сделать
UFO94
 Аватар для UFO94
263 / 252 / 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 составляет больше мегабайта оперативной памяти.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
19.05.2012, 21:16  [ТС]     Разбиения множества #13
UFO94, а можете тогда еще раз объяснить рекурсию, пожалуйста.
UFO94
 Аватар для UFO94
263 / 252 / 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.
И алгоритм будет жрать память как корень квадратный из того, что жрал раньше
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 06:11  [ТС]     Разбиения множества #15
Цитата Сообщение от UFO94 Посмотреть сообщение
Когда мы выбрали все нужные нам m точек (условие m1==m
То есть чтобы он перебрал все варианты комбинаций точек нужно еще на это цикл наложить?

А не проще будет все-таки комбинировать массы точек, а потом уже сопоставлять с точками?
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 12:06     Разбиения множества #16
Цитата Сообщение от ejk Посмотреть сообщение
То есть чтобы он перебрал все варианты комбинаций точек нужно еще на это цикл наложить?
Нужен цикл в основной программе и в нем вызов функции grouping. Ну, я приводил этот кусок кода.

Цитата Сообщение от ejk Посмотреть сообщение
комбинировать массы точек
А что вы имеете в виду под комбинированием масс?

Не по теме:

У нас с вами, похоже, резко несовпадают часовые пояса...(

ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 12:09  [ТС]     Разбиения множества #17
Цитата Сообщение от UFO94 Посмотреть сообщение
вызов функции grouping
Мы эту функцию вообще не затрагивали Я понятия не имею, что это.
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 12:15     Разбиения множества #18
Вообще-то, это та функция, которую я написал. На первой странице, сообщение номер 6, там сначала функция grouping, потом ее вызов из основной программы
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 12:16  [ТС]     Разбиения множества #19
Цитата Сообщение от UFO94 Посмотреть сообщение
А что вы имеете в виду под комбинированием масс?
У меня для каждой точки задана ее масса и основной целью является найти разбиение точек на два подмножества, чтобы расстояния между центрами тяжести были минимальны. Вот я и подумала, что комбинировать массы проще, чем точки.
Еще можно создать один цикл фор, где просто перебираются точки, как будто шарики из мешка. Но там мне еще посоветовали рэндом засунуть

Добавлено через 38 секунд
Цитата Сообщение от UFO94 Посмотреть сообщение
там сначала функция grouping
Я помню Ваш код. Эта функция присутствует в языке Си или это как раз и есть рекурсия?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2012, 12:26     Разбиения множества
Еще ссылки по теме:

C++ Число изъять из множества А, если оно является элементом множества А, но не является элементом множества В
C++ Программа разбиения строк на слова
Алгоритм разбиения массива на подмассивы C++

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

Или воспользуйтесь поиском по форуму:
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 12:26     Разбиения множества #20
Это не стандартная функция в языке С, иначе я бы ее не писал. Рекурсия -- это просто прием вызова функцией самой себя. Например:
Функция нахождения факториала числа n:
{
Если n!=0
Возвращаем n*Факториал(n-1);//Вот он, вызов функции самой из себя. Но нужно этот процесс еще как-то закончить.
Если n==0 возвращаем 1;// 0! по определению равен 1
}

Цитата Сообщение от ejk Посмотреть сообщение
комбинировать массы
Просто напишите, чисто логически, как вы это представляете.

Цитата Сообщение от ejk Посмотреть сообщение
цикл фор, где просто перебираются точки, как будто шарики из мешка
Если бы нам нужно было выбрать 1 точку, то был бы просто цикл for. Но нам нужно много точек, потому циклом for принципиально можно, но уж очень муторно.

Цитата Сообщение от ejk Посмотреть сообщение
рэндом засунуть
ИМХО, плохая идея. Так мы можем и не перебрать все комбинации, либо очень долго их перебирать. Львиную часть времени рендом будет обрабатывать уже пройденые нами варианты.
Yandex
Объявления
20.05.2012, 12:26     Разбиения множества
Ответ Создать тему
Опции темы

Текущее время: 07:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru