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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.69
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
18.05.2012, 19:38     Разбиения множества #1
Добрый вечер.
У меня есть множество точек в трехмерном пространстве, которые я считала и занесла в двухмерный массив. Задача состоит в том, чтобы рассмотреть все разбиения этого множества на два и сравнить их центры тяжести. Но как сравнить я знаю, а вот как разбить понятия не имею.
Например, если у меня три точки, то должно получится три варианта разбиения. Программирую на Си.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 12:36  [ТС]     Разбиения множества #21
Я окончательно запуталась Видимо не написать мне программу
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UFO94
 Аватар для UFO94
263 / 252 / 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
Сообщений: 80
20.05.2012, 12:58  [ТС]     Разбиения множества #23
UFO94, получается, что номера точек мы берем, как номера строк? Потому что я построчно считываю координаты из файла
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 13:03     Разбиения множества #24
Если у вас файл, где просто в каждой строке записаны координаты одной точки, то да.
Но вам сначала прийдется посчитать количество точек.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
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
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 13:07     Разбиения множества #26
Стоп. У вас сколькимерное пространство? o_O
Общий случай, чтоли? В пределе -- 100-мерное?
Я уж не говорю о том, что все можно сделать намного рациональнее...
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 13:09  [ТС]     Разбиения множества #27
UFO94, трехмерное.

Добавлено через 53 секунды
То есть Nmax на 3 заменить?
UFO94
 Аватар для UFO94
263 / 252 / 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
Сообщений: 80
20.05.2012, 13:16  [ТС]     Разбиения множества #29
UFO94, я просто думала, что разделить на два массива будет удобнее..
UFO94
 Аватар для UFO94
263 / 252 / 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);
   }
}
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 13:38  [ТС]     Разбиения множества #31
Цитата Сообщение от UFO94 Посмотреть сообщение
fscanf(file,"%f%f%f",&pt[i][0],&pt[i][1],&pt[i][2]);
Да, я изначально хотела эту функцию брать, только не могла понять, как ее правильно использовать

Добавлено через 1 минуту
А вот там, где нужно рассчитать центр тяжести, нужны координаты точек в множестве. Как из извлекать?
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 13:40     Разбиения множества #32
Цитата Сообщение от ejk Посмотреть сообщение
fscanf(file,"%d",&M[i][j]);
Ну так у вас эта функция и была использована....

Координаты точек хранятся в массиве pt(у вас он M). В массиве num лежат только номера точек, которые вошли в 1-ю группу.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 13:44  [ТС]     Разбиения множества #33
Цитата Сообщение от UFO94 Посмотреть сообщение
только номера точек
Которые являются номерами строк в двумерном массиве, так?

Добавлено через 1 минуту
Еще вопрос: откуда в вашем коде появляется m1?
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 13:50     Разбиения множества #34
Цитата Сообщение от ejk Посмотреть сообщение
Которые являются номерами строк в двумерном массиве, так?
Да, все правильно.

Цитата Сообщение от ejk Посмотреть сообщение
Еще вопрос: откуда в вашем коде появляется m1?
m1 -- это счетчик уже выбраных точек. Т.е., допустим нам надо выбрать 10 точек. Мы выполняем много раз функцию grouping (ну, она скорее сама себя выполняет), и уже выбрали 4 точки, выбираем 5-ю. Тогда m1=4. При этом первые 4 элемента массива num содержат номера точек, которые мы уже выбрали.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 13:54  [ТС]     Разбиения множества #35
UFO94, а m тогда что такое?
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 14:04     Разбиения множества #36
Полное количество точек, которые нам нужно выбрать. Функция grouping заканчивает считать, когда m1==m. Число m мы перебираем в основной программе от 1 (выбор только одной точки) до, исправьте, не (N+1)/2, а просто N/2, т.е. до половины всего количества точек с округлением вниз. Т.е., если у нас 9 точек, то мы сперва рассмотрим все разбиения 1 на 8 (1 точку выбираем), потом 2 на 7 (выбираем 2 точки), 3 на 6 (выбираем 3 точки), 4 на 5 (выбираем 4 точки). Разбиения 5 на 4, 6 на 3 и т.д. нас не интересуют, потому что они будут повторять разбиения 4 на 5, 3 на 6 и т.д., только выбраные и невыбраные точки поменяются местами.
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 14:09  [ТС]     Разбиения множества #37
А не будет получаться так, что мы будем брать 1 на 8 и первая точка всегда будет первая в списке. Ну то есть по идее мы же должны перебрать все точки и к каждой еще 8 в другой группе собрать, так? Эта функция так делает?
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 14:24     Разбиения множества #38
Эта функция делает так (совсем пошагово):
Хотим выбрать 1 точку, вызываем функцию//Это еще в main
___Функция выбирает точку №1
___--- сделали свои подсчеты для этого разбиения ---
___Функция выбирает точку №2
___--- сделали свои подсчеты для этого разбиения ---
___....
___Функция выбирает точку №9
___--- сделали свои подсчеты для этого разбиения ---
Хотим выбрать 2 точки//опять таки, это еще в мейн
___Функция выбирает первой точкой №1
______Функция выбирает второй точкой №2
______--- Подсчеты ---
______Функция выбирает второй точкой №3
______--- Подсчеты ---
______Функция выбирает второй точкой №4
______--- Подсчеты ---
______....
______Функция выбирает второй точкой №9
______--- Подсчеты ---
___Функция выбирает первой точкой №2
______Функция выбирает второй точкой №3
______--- Подсчеты ---
______Функция выбирает второй точкой №4
______--- Подсчеты ---
______Функция выбирает второй точкой №5
______--- Подсчеты ---
______....
______Функция выбирает второй точкой №9
______--- Подсчеты ---
........
___Функция выбирает первой точкой №7
______Функция выбирает второй точкой №8
______--- Подсчеты ---
______Функция выбирает второй точкой №9
______--- Подсчеты ---
___Функция выбирает первой точкой №8
______Функция выбирает второй точкой №9
______--- Подсчеты ---
Хотим выбрать 3 точки
... аналогично....
Хотим выбрать 4 точки
... аналогично ...
ejk
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 80
20.05.2012, 14:35  [ТС]     Разбиения множества #39
Так. Все. Вроде с функцией разобралась. Такой вопрос: как сделать, чтобы он просто вывел это разбиение? Ну чтобы проверить правильно ли работает.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2012, 14:53     Разбиения множества
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
20.05.2012, 14:53     Разбиения множества #40
Там, где я в комментариях поставил кучу !, пишем
C++
1
2
3
for(int i=0; i<m; i++)
printf("%d  ",num[i]);
printf("\n");
Yandex
Объявления
20.05.2012, 14:53     Разбиения множества
Ответ Создать тему
Опции темы

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