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

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

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

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

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

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

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

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

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

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

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

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

Программа разбиения строки на слова с использованием указателей - C++
Здравствуйте, разъясните пожалуйста, почему в циклах while и инструкции if, условием является указатель? что это значит? это...

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

Не по теме:

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

ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
19.05.2012, 12:34  [ТС]     Разбиения множества #9
UFO94, нет. Мне нужно найти разбиение на два множества, расстояние между центрами масс которых минимальное.
Просто как сделать так, чтобы он сам перебрал все варианты?
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
19.05.2012, 13:21     Разбиения множества #10
Ну, мой алгоритм и будет перебирать все варианты. Придеться ввести глобальные переменные "расстояние" и "разбиение", и все ок.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
19.05.2012, 16:22  [ТС]     Разбиения множества #11
UFO94, Ваш алгоритм кажется мне каким-то сложным %) Я думала, что через for можно как-то сделать
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 составляет больше мегабайта оперативной памяти.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
19.05.2012, 21:16  [ТС]     Разбиения множества #13
UFO94, а можете тогда еще раз объяснить рекурсию, пожалуйста.
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.
И алгоритм будет жрать память как корень квадратный из того, что жрал раньше
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2012, 06:11     Разбиения множества
Еще ссылки по теме:

программа вращающейся сферы с эффектом разбиения на с++ Borland - C++
реализовать на с++ Borland программу: сфера падает вращаясь и разбивается на кусочки !!! :cry::( помогите кто чем может...

.h и .cpp файлы, бредовые ошибки после разбиения класса - C++
Какая то проблема со string Во всех функциях в файле реализации одна ошибка: Несоответствие списка аргументов, отсутствуют экземпляры ...

Удалить из множества А минимальный элемент множества В - C++
Удалить из множества А минимальный элемент множества В. могу удалить из A все елементи B. а минимальний нет( #include &lt;iostream&gt; ...

Написать рекурсивную процедуру генераций разбиения числа n на сумму слагаемых - C++
Задача : Написать рекурсивную процедуру генераций разбиения числа n на сумму слагаемых. Например при n=4 3 1 2 2 2 1 1 1 1 1 1 ...

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


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

Или воспользуйтесь поиском по форуму:
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
20.05.2012, 06:11  [ТС]     Разбиения множества #15
Цитата Сообщение от UFO94 Посмотреть сообщение
Когда мы выбрали все нужные нам m точек (условие m1==m
То есть чтобы он перебрал все варианты комбинаций точек нужно еще на это цикл наложить?

А не проще будет все-таки комбинировать массы точек, а потом уже сопоставлять с точками?
Yandex
Объявления
20.05.2012, 06:11     Разбиения множества
Ответ Создать тему
Опции темы

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