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

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

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

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

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

Добрый вечер.
У меня есть множество точек в трехмерном пространстве, которые я считала и занесла в двухмерный массив. Задача состоит в том, чтобы рассмотреть все разбиения этого множества на два и сравнить их центры тяжести. Но как сравнить я знаю, а вот как разбить понятия не имею.
Например, если у меня три точки, то должно получится три варианта разбиения. Программирую на Си.
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 соответственно. Вычислить...

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

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

Не по теме:

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

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

Добавлено через 38 секунд
Цитата Сообщение от UFO94 Посмотреть сообщение
там сначала функция grouping
Я помню Ваш код. Эта функция присутствует в языке Си или это как раз и есть рекурсия?
UFO94
264 / 253 / 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 Посмотреть сообщение
рэндом засунуть
ИМХО, плохая идея. Так мы можем и не перебрать все комбинации, либо очень долго их перебирать. Львиную часть времени рендом будет обрабатывать уже пройденые нами варианты.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
20.05.2012, 12:36  [ТС] #21
Я окончательно запуталась Видимо не написать мне программу
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 12:46 #22
Ну так а с чем сложности? Смотри, по действиям:
1) Обьявляем глобальные переменные int* num1 ,int m2 и float dist=0;
2) До мейна вставляем прототип функции grouping.//Не забываем про изменение кода из поста номер 14
3) В мейне вставляем тот второй кусок кода..//Не забываем про изменение кода из поста номер 14
4) Вместо 15 строки в описании функции всталяем:
Подсчет расстояний между центрами масс L. Сравнение с dist. Если L больше, чем dist, то dist=L, m2=m, num1=new int[m]; И копируем поэлементно из массива num в массив num1.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
20.05.2012, 12:58  [ТС] #23
UFO94, получается, что номера точек мы берем, как номера строк? Потому что я построчно считываю координаты из файла
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 13:03 #24
Если у вас файл, где просто в каждой строке записаны координаты одной точки, то да.
Но вам сначала прийдется посчитать количество точек.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
20.05.2012, 13:04  [ТС] #25
UFO94, кол-во точек тоже читается из файла. Вот то, что я пока написала

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
#include <math.h> 
#define Nmax 100
int main (void)
{
    int i,j,k,r1,r2,N;
    int M[Nmax][Nmax];
    int K[Nmax];
    int R1[Nmax];
    int R2[Nmax];
    FILE *file;
    file = fopen("3tochki.txt", "r");
    fscanf(file,"%d",&N);
    for(i=0;i<N;i++){
        for(j=0;j<N;j++)
        fscanf(file,"%d",&M[i][j]);
        }
    FILE *f;
    f = fopen("3massa.txt", "r");
    for(k=0;k<N;k++)
        fscanf(f,"%f", &K);
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 13:07 #26
Стоп. У вас сколькимерное пространство? o_O
Общий случай, чтоли? В пределе -- 100-мерное?
Я уж не говорю о том, что все можно сделать намного рациональнее...
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
20.05.2012, 13:09  [ТС] #27
UFO94, трехмерное.

Добавлено через 53 секунды
То есть Nmax на 3 заменить?
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 13:14 #28
Одно из Nmax. Т.е., у вас будет массив [Nmax на 3]

Добавлено через 41 секунду
Впрочем, я могу просто переписать этот код, чтобы он стал чуть универсальнее и лучше, и обьяснить.

Добавлено через 1 минуту
Кстати, а почему бы не сделать массив [Nmax на 4]? 3 координаты + одна масса
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 81
20.05.2012, 13:16  [ТС] #29
UFO94, я просто думала, что разделить на два массива будет удобнее..
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 13:35 #30
Это на самом деле все равно. У статических массивов (те, которые у вас) есть 1 крупный недостаток. Нам должны быть изначально известны их размеры. К чему это ведет в вашей программе? Если у нас будет 101 точка, то последняя просто не прочитается. Если у нас будет 10 точек, то все будет работать, но памяти на это будет затрачено как на 101 точку. По другому обстоит дело с динамическими массивами. Переписанный ваш кусок кода:
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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
FILE* file=fopen("3tochki.txt","r");
int c='a';//В эту переменную будем считывать символы. Файл всегда заканчивается особым служебным символом -- конец файла (End Of File, EOF). В некоторых случаях он равен -1, потому в переменную типа char его не считаешь.
int N=0;//Количество точек
while(c!=EOF)//Пока не конец файла
{
if(c=='\n')//Перенос на следующую строку
N++;
c=getc(f);//Считывание следующего символа
}
N++;//Теперь N -- это наше реальное количество точек
fclose(file);
file=fopen("3tochki.txt","r");//Переоткрыли файл, чтобы курсор стал на его начало.
float* *pt=new float*[N];
for(int i=0; i<N; i++)
pt[i]=new float[3];//Создали динамический массив N на 3
float* mas=new float[N];//Создали динамический массив из N элементов
for(int i=0; i<N; i++)
{
fscanf(file,"%f%f%f",&pt[i][0],&pt[i][1],&pt[i][2]);
}
fclose(file);
file=fopen("3massa.txt","r");
for(int i=0; i<N; i++)
fscanf(file,"%f",&mas[i]);
fclose(file);
}
Добавлено через 3 минуты
Теперь тот же самый код, только с добавлением моей функции:
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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
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
      {
         num[0]=i;
         grouping(n,m,1,num);
      }
   }
   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, то опять-таки комбинации будут повторяться
      {
         num[m1]=i;
         grouping(n,m,m1+1,num);
      }
   }
}
int main()
{
   FILE* file=fopen("3tochki.txt","r");
   int c='a';//В эту переменную будем считывать символы. Файл всегда заканчивается особым служебным символом -- конец файла (End Of File, EOF). В некоторых случаях он равен -1, потому в переменную типа char его не считаешь.
   int N=0;//Количество точек
   while(c!=EOF)//Пока не конец файла
   {
      if(c=='\n')//Перенос на следующую строку
      N++;
      c=getc(f);//Считывание следующего символа
   }
   N++;//Теперь N -- это наше реальное количество точек
   fclose(file);
   file=fopen("3tochki.txt","r");//Переоткрыли файл, чтобы курсор стал на его начало.
   float* *pt=new float*[N];
   for(int i=0; i<N; i++)
   pt[i]=new float[3];//Создали динамический массив N на 3
   float* mas=new float[N];//Создали динамический массив из N элементов
   for(int i=0; i<N; i++)
   {
      fscanf(file,"%f%f%f",&pt[i][0],&pt[i][1],&pt[i][2]);
   }
   fclose(file);
   file=fopen("3massa.txt","r");
   for(int i=0; i<N; i++)
   fscanf(file,"%f",&mas[i]);
   fclose(file);
   int n1=(N+1)/2;
   for(int i=1; i<n1; i++)
   {
      int* num=new int[i];
      grouping(n,i,0,num);
   }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2012, 13:35
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
20.05.2012, 13:35
Ответ Создать тему
Опции темы

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