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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.77
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
#1

Покрытие множеств - C++

19.01.2010, 18:22. Просмотров 3733. Ответов 37
Метки нет (Все метки)

Добрый день, новичок на этом форуме =)
нуждаюсь в помощи с задачей на покрытия множеств.
Дано множество

http://img96.imageshack.us/img96/1008/mnoj.jpg

нужно двумя алгоритмами (полного и граничного переборов) вычислить полные покрытия и "лишние" покрытия.
как можно наиболее оптимально осуществить полный и граничный перебор? ведь это 2^n вариантов..
Думал еще над способом с битными масками, но нигде не нашел ничего подобного.
Буду очень благодарен за помощь.

Добавлено через 35 минут
я прошелся по разделу и понял, что может быть я не туда запостил?
если да, то пусть модераторы перенесут тему в раздел "С\С++", а то вроде не совсем "начинающая" задачка.
благодарю
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2010, 18:22     Покрытие множеств
Посмотрите здесь:

Найти покрытие полным перебором - C++
Всем доброго времени суток. Программирование С++ изучаю недавно. Дали запрограммировать покрытие полным и граничным перебором. Загнал...

Минимальное реберное покрытие графа - C++
Господа, подскажите пожалуйста, как реализовать эту задачу. Я так понимаю суть ее заключается ее в том, что,s необходимо найти такое...

Покрытие шахматной доски ходом коня - C++
4. Покрытие шахматной доски ходом коня.

Определить, существует ли покрытие C' из C мощности не более K - C++
УСЛОВИЕ. Задано семейство C подмножеств конечного множества S и положительное целое число K <= |C|. ВОПРОС. Существует ли покрытие C' из...

пересечение множеств - C++
найти пересечение мнжества А и В. Результат вывести в другом множестве. заранее спс. извиняюсь если такое задание уже было

Пересечение множеств - C++
Есть такое задание: Создать класс- множество. Функции-члены реализуют добавление и удаление элемента, пересечение и размность множеств. ...

Булеан множеств - C++
В общем нужно в программе "операции с множествами" добавить операцию "Булеан" честно говоря вообще ничего в голову не лезет....может...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
19.01.2010, 21:24     Покрытие множеств #2
Видимо, 1-9 - элементы множества
A - G -сами множества
Между ними - матрица инцендентности
А что означает столбец (a) ?
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
19.01.2010, 22:08  [ТС]     Покрытие множеств #3
извините, забыл указать, что последний столбец - цена множества. после нахождения покрытий также можно находить самое дешевое.
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
20.01.2010, 11:25     Покрытие множеств #4
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
#include <stdio.h>
 Для начала будем считать что мощность множества N < 32 = sizeof(long)
 Тогда полное множество делается так:
  long U = 0;
  for(i=0; i<N; i++) U |= (1L<<i);
 Для полного перебора тоже используем шкалу
  long P = 0;
  for(i=0; i<n; i++) P |= (1L<<i);  // n - Кол-во множеств
 Пусть множества заданы числами long A[n]
 ( A[i] & (1L << j)) = 1 тогда и только, когда i-тое множество
                         содержит j-тый элемент
  double a[n]; - Веса
  double s; // цена покрытия
  long X = 0; // X содержит множества, участвующие в пробном покрытии
  long Y;  // Частичное покрытие
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {  // Покрытие найдено
        s = 0;
        for (j=0; j<i; j++) { // Печать найденного покрытия и его цены
          if (X & (1L<<j)) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if (X & (1L<<i)) Y = (Y | A[i]);
    }
    X++;
  }
Это только идея. Возможны опечатки.
Перебор почти полный (отбрасываются остатнии множества, когда все покрыто).
Если N>=32, тогда надо находить другое представление множеств.
1) Как массива long и сделать маленькие фунциклюшки работы с битами
для массива (присвоение i-того бита, проверка i-того бита, сравнение
двух массивов и т.д.)
2) Как строки символов равных 1 или 0. Легче для программирования,
но неэкономно по памяти (в 8 раз)
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
20.01.2010, 15:30  [ТС]     Покрытие множеств #5
Цитата Сообщение от Day Посмотреть сообщение
Это только идея. Возможны опечатки.
Перебор почти полный (отбрасываются остатнии множества, когда все покрыто).
спасибо! я именно пример этого способа и искал)
буду признателен если подробнее поможете разобраться

U |= (1L<<i);
это битовый сдвиг влево на позицию "i" с доставкой "1" бита в конец?
таким образом у нас будет выходить
1
11
111
1111
и тд
тоесть
1
3
7
15
какой вид массива А[n] будет? я не совсем понял.. A[n]= { {1},{2},{3}, ... {n} } ?
Я так понял, что этот кусочек не есть кодом программы
( A[i] & (1L << j)) = 1 тогда и только, когда i-тое множество
содержит j-тый элемент
но как это выражение может быть равно 1? можно пример на числе каком-то.

пока что без осмысления этих вещей не могу пройтись далее по коду. =)
insideone
Модератор
Автор FAQ
3638 / 916 / 49
Регистрация: 10.01.2010
Сообщений: 2,468
20.01.2010, 15:39     Покрытие множеств #6
1011 0011 0000 1110 // A[i]
&
0000 0000 0000 1000 // ==
//0000 0000 0000 0001 << 3 // 1L << 3
Результат: 1&1 = 1

1011 0011 0000 1110 // A[i]
&
0000 0000 0001 0000 // ==
//0000 0000 0000 0001 << 4 // 1L << 4
Результат: 0&1 = 0

На самом деле & пробегает по всем битам, однако т.к. остальные биты нулевые в нашем 1L то результат тоже будет нулевым для других бит. Вроде так =))
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
20.01.2010, 15:49  [ТС]     Покрытие множеств #7
insideone, спасибо, это понял)

осталось понять формат массива A[n]
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
21.01.2010, 12:31     Покрытие множеств #8
U |= (1L<<j) - Да это так.
В U получается столько единиц, какова мощность всего множества

(A[j] & (1L<<j)) == 1 - Простите, ошибочка моя
Правильно
(A[j]&(1L<<j)) != 0
Или
((A[j]>>j) & 1) == 1
Для твоего примера
A = 10100010
B = 101001010
....
Рекомендация.
Осторожнее с битовыми операциями!
В C приоритеты не очень логично проставлены
На всякий случай заключайте их в скобки
У == приоритет больше, чем у &&
Но если скобок не жалеть - все будет хорошо
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
21.01.2010, 16:49  [ТС]     Покрытие множеств #9
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
int N=7,n=9,j,i=0;
 
// Togda polnoe mnojestvo delaetsya tak:
  long U = 0;
  for(i=0; i<7;i++ )
   {
   U |= (1L<<i);
 
    }
// Dlya polnogo perebora toje ispol'zuem shkalu
  long P = 0;
  for(i=0; i<n; i++)
  {
     P |= (1L<<i);
   }
 
 
  double a[9]; //vesa
  double s; // cena
  /// Pust' mnojestva zadany chislami long A[n]
  long A[7]={ {10100010}, {101001010}, {110011},
                 {100100100},{1010001},{1101},{10110101},};
  long X = 0; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  long Y;  // Chastichnoe pokrytie
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) { 
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )
       {
          Y = (Y | A[i]);
       }
    }
    X++;
  }
}

я правильно понял как должны задаться множества?
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
22.01.2010, 10:58     Покрытие множеств #10
Вроде, все правильно.
Только этот кусочек мы то с тобой понимаем, а транслятор может и не понять
long A[7]={ {10100010}, {101001010}, {110011},
{100100100},{1010001},{1101},{10110101},};
Лучше так
Код
long  A[7] = { 0xA2, 0x14A, 0x63, 0x124, 0x51, 0xD, 0xb5 };
Т.е записываем в 16-й системе
(Мог ошибиться в циферках)
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
22.01.2010, 16:06  [ТС]     Покрытие множеств #11
да, только 3ий елемент 0х33.


тестирую вот программу.
выводит:
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
странно, эти множества даже не создают покрытие...
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
22.01.2010, 18:14     Покрытие множеств #12
0x33 - Согласен
Будь добр, пришли исходник тестируемой проги
(в предпоследем твоем посте вариант явно не рабочий - даже a[j] не инициализированы)
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
22.01.2010, 18:32  [ТС]     Покрытие множеств #13
извините) я думал, что запостил)
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
#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <conio.h>
#include <alloc.h>
void main() {
clrscr();
int N=7,n=9,j,i=0;
 
// Togda polnoe mnojestvo delaetsya tak:
  long U = 0;
  for(i=0; i<7;i++ )
   {
   U |= (1L<<i);
 
    }
// Dlya polnogo perebora toje ispol'zuem shkalu
  long P = 0;
  for(i=0; i<n; i++)
  {
     P |= (1L<<i);
   }
 
 
  double a[9]={ {1}, {3}, {2}, {2}, {1}, {2}, {3} }; //vesa
  double s; // cena
  /// Pust' mnojestva zadany chislami long A[n]
 long  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xb5 };
 
  long X = 0; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  long Y;  // Chastichnoe pokrytie
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )
       {
          Y = (Y | A[i]);
       }
    }
    X++;
  }
}
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
23.01.2010, 00:08     Покрытие множеств #14
Основная ошибка - было перепутано N и n
Окромя того я все делал на чистом С, а он, дурачок, не понимает объявлений переменных
внутри функции, только в начале понимает
С++ и вся его мощь тут не нужны.
Так что переставил кой чего
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
#include <stdio.h>
// #include <iostream.h>
#include <string.h>
#include <conio.h>
// #include <alloc.h>
 
void main()
{
 int N = 7;  // kol-vo podmnogestv
 int n = 9;  // kol-vo elementov polnogo mnogestva
 int j, i;
 // double a[9]={ {1}, {3}, {2}, {2}, {1}, {2}, {3} }; // Eta stroka ne dolgna compilirovatsiy
 double a[7]={ 1, 3, 2, 2, 1, 2, 3 }; //vesa
  // Pust' mnojestva zadany chislami long A[n]
 long  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xb5 };
 long U, P, X;
 long Y;  // Chastichnoe pokrytie
 double s; // cena
 
//  clrscr();
 
// Togda polnoe mnojestvo delaetsya tak:
  U = 0;
  for(i=0; i<n;i++ )   U |= (1L<<i);
// Dlya polnogo perebora toje ispol'zuem shkalu
  P = 0;
  for(i=0; i<N; i++)   P |= (1L<<i);
  X = 1; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )  Y = (Y | A[i]);
    }
    X++;
  }
}
Что-то получается, но я не проверял, уж ты сам, будь добр, этим займись.
Если что-то будет не так - вставляй отладочные печати непонятных переменных
Если печатей этих будет слишком много: перенаправь стандартный вывод:
...exe >файл

ЗЫ. 1. Какова причина замена русских слов латиницей? Ты здесь не один такой -
так очень многие делают. Т.е. причина какая-то есть. Мне интересно - какая.
2. Пожалуйста! (и всем, кому сможешь, передай) Старайтесь делать грамотно отступы.
Чтобы операторы одного блока (между { ... } ) начинались друг под другом
Мучительно разбираться в проге с отступами в стиле шаляй-валяй. Ты и сам когда-нибудь
это поймешь.
Когда я вижу в коде этот раскардаш, как правило, тут же тему пропускаю.
Тебе повезло - задачка любопытная, и я нашел в ней новый ход.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.01.2010, 00:31     Покрытие множеств
Еще ссылки по теме:

Пересечение множеств - C++
Вход — два множества натуральных чисел. Выход — их пересечение (перечисление элементов через пробел в любом порядке без повторений)...

объединение множеств - C++
template&lt;class ValType, class FwdIt&gt; FwdIt copy ( FwdIt first, FwdIt last, FwdIt result ) { while (first!=last) *result++ =...

Обработка множеств - C++
Что должна делать эта программа? В чём её смысл? Разработать программу, реализующую обработку нескольких массивов структур (до 5...

Калькулятор множеств - C++
Доброго всем утра, у меня есть лаба &quot;операции над множествами&quot;, там класс множество и методы работы с ним. На вход подаются две строки типа...

Объединение множеств - C++
Задача. Написать программу, которая объединяет 2 множества. Вот мой код. Мне выдаёт ошибку, что последовательность не отсортирована. В...


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

Или воспользуйтесь поиском по форуму:
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
23.01.2010, 00:31  [ТС]     Покрытие множеств #15
1. Borland C под Dos понимает русские слова только под утилитой keyrus =)
2. *позор* я понимаю это и сам часто одногрупникам обьясняю, но в таких программах, где мало кода частенько забываю об этом)

да, очень благодарен за то, что взялись помочь
сейчас буду проверять.

Добавлено через 7 минут
вставляй отладочные печати непонятных переменных
как?)

вот первое же покрытие выдало : A B C D, неправильное.
но второе A B D E правильное.
третим повторило A B C D
4 - A B C F, тоже правильное
5 - опять повторило A B C D
6 - A B E F, правильное
ну вот пока видно, что только на A B C D проштрафилось..
Yandex
Объявления
23.01.2010, 00:31     Покрытие множеств
Ответ Создать тему
Опции темы

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