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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ книга http://www.cyberforum.ru/cpp-beginners/thread87470.html
какие книги вы посоветуете для быстрого изучения языка си???
C++ Перевести число из десятичной в двоичную 1. Составить программу согласно заданию. 2. Протестировать программу одним из известных методов тестирования (Black Box або White Box) Примітка: 1.Данные вводяться с клавы. 2.Указывать результат роботи программи. Завдання: http://www.cyberforum.ru/cpp-beginners/thread87433.html
C++ Статистика:Метод наименьших квадратов
Вот такая задача мне попалась недавно на с++... Во время исследований получили экспериментальную зависимость вяскости глицерина в сантипуазах и температуры в градусах Цельсия: температура --- вяскость -42 ----- 6.71*10^6 -20 ----- 1.34*10^5 0 ------ 1.21*10^4 20 ----- 1.49*10^3 30 ----- 6.26*10^2 Методом...
Работа с файломи C++
Здравствуйте. Нужна программа которая бы делала следующее. У нас есть неопределенное количество файлов. Пользователь с помощью стандартного ввода пишет путь к файлу и производиться считывание строки из файла. Строкой внутри этого файла является путь к следующему файлу. После считывания строки производим такую же операцию, только пользователь уже ничего не вводит, а путь к файлу копируется из...
C++ Вектор и итераторы http://www.cyberforum.ru/cpp-beginners/thread87418.html
Всем привет. Помогите дописать курсовую. Нодо сделать вывод студентов с вектора + сортировку объектов в векторе по любому значению. Вот что у меня получилось: /////////////////////////////////////////////////////////////////////////////////////////////////////// #include "stdafx.h" #include <fstream> #include <iostream> #include <conio.h> #include <vector> #include <stdio.h>...
C++ написать функцию, возвращающую массив Всем здравствуйте, Вопрос такой: нужно написать функцию, которая возвращает массив из двух чисел, и я не хочу использовать std::pair. Следующий вариант работает вроде: int* return_array(){ int arr; arr = 0; подробнее

Показать сообщение отдельно
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
20.01.2010, 11:25     Покрытие множеств
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 раз)
 
Текущее время: 06:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru