Генерация всех возможных подмножеств на Bornald C++ 3. 1

Модераторы: Romeo, Hawk, Absurd, WinMain, DeeJayC

Lei fang
Сообщения: 49
Зарегистрирован: 28 май 2005, 20:25
Откуда: Саратов
Контактная информация:

Генерация всех возможных подмножеств на Bornald C++ 3. 1

Сообщение Lei fang » 28 май 2005, 21:10

Здравствуйте!!!

Люди! Помогите мне, пожалуйста! Я учусь на программиста и мне дали задание "Сгенерировать все возможные подмножества данного n-элементного множества. Результат записать в файл." Отправить данные в файл не сложно, а вот как сгенерировать эти подмножества я что-то не понимаю. Думаю, что должен быть один массив, который нужно просматривать в цикле и если такой комбинации элементов еще не было, то записывать ее в файл. Однако я не представляю себе как должен выглядеть такой алгоритм более подробно. В этом вся и проблема. Кто-нибудь помогите!

Eugie
Сообщения: 707
Зарегистрирован: 17 фев 2004, 23:59
Откуда: SPb

Сообщение Eugie » 31 май 2005, 00:17


Lei fang
Сообщения: 49
Зарегистрирован: 28 май 2005, 20:25
Откуда: Саратов
Контактная информация:

Сообщение Lei fang » 31 май 2005, 12:31

Спасибо. Чесно говоря я тоже не совсем понимаю изложенный там алгоритм.
Во первых: Что такое сигнатура и зачем она там нужна?
Если есть множество из 4 элементов (1, 2, 3, 4), то подмножествами будут (если, конечно, перестановки не считаются подмножествами)
(0)
(1)
(2)
(3)
(4)
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)
Зачем нужны 0 и 1?

>>объявляешь переменную типа unsigned long и в последовательно ее инкрементируешь от 0 до 2^N-1.
Что значит инкрементируешь? И что такое 2^N-1?

Помогите!!! Надо сдать до сессии...

Lei fang
Сообщения: 49
Зарегистрирован: 28 май 2005, 20:25
Откуда: Саратов
Контактная информация:

Сообщение Lei fang » 31 май 2005, 13:44

Совсем забыл про
(1, 2, 3)
(2, 3, 4)

Аватара пользователя
WinMain
Сообщения: 912
Зарегистрирован: 14 янв 2005, 10:30
Откуда: Москва
Контактная информация:

Сообщение WinMain » 31 май 2005, 16:04

Здесь используется прямой аналог с двоичной системой исчисления, т.е. из массива, состоящего только из нулей и единиц, и имеющего N элементов, можно сформировать количество разных комбинаций, равное 2 в степени N (сокращённо 2^N). Далее понятие сигнатуры можно определить как: 1- принадлежит подмножеству, 0- не принадлежит. Так из множества, в котором всего 10 элементов, можно составить 1024 разных варианта подмножеств, включая пустое множество и полное исходное множество.

Lei fang
Сообщения: 49
Зарегистрирован: 28 май 2005, 20:25
Откуда: Саратов
Контактная информация:

Сообщение Lei fang » 31 май 2005, 17:23

Хорошо. Спасибо. Уже хоть что-то стало понятно (хотя и не достаточно).

Пожалуйста, помогите составить алгоритм.

Что именно делать дальше?

1. Создаю динамический массив из n элементов (пусть будет 4)
2. Заполняю массив (p={1, 2, 3, 4} ;)
3. ???
.
.
.

Извините за непонятливость...

Eugie
Сообщения: 707
Зарегистрирован: 17 фев 2004, 23:59
Откуда: SPb

Сообщение Eugie » 01 июн 2005, 17:11

Проще самому написать :)

Код: Выделить всё

#include "stdafx.h"
#include <iostream>
#include <cmath>

using namespace std;

void main()
{
    int p[] = {1, 2, 3, 4};
    int n = sizeof(p)/sizeof(int);
    int m = (int)pow(2,n);

    for (int i=0; i<m; ++i)
    {
      bool sep=false;
      cout << "{";
      for (int d=0; d<n; ++d)
      {
        if ((1<<d)&i)
        {
            cout << (sep ? ", " : "") << p[d];
            sep = true;
        }
      }
      cout << "}\n";
    }
}

Lei fang
Сообщения: 49
Зарегистрирован: 28 май 2005, 20:25
Откуда: Саратов
Контактная информация:

Сообщение Lei fang » 01 июн 2005, 18:06

Спасибо за Вашу доброту, Eugie.

Хм... Это... А Вы написали эту программу точно на Bornald C++ 3. 1?

Просто, я попытался ее компилировать, а там 10 ошибок! Эти 3 библиотеки не открываются (Хотя если написать #include <iostream.h>, то она откроется, а с другими такое не выходит).

Да еще компилятор не знает большенства операторов. Я, конечно, слышал, что тот bc_31, на котором мы пишем программы, покотцан, но чтоб так...

В общем, если я правильно понял, как тут вставлять картинки, то скриншот здесь:
Изображение

и, если нужен локальный путь, то:

[img]http://D:\Documents%20and%20Settings\User\Мои%20документы\bc%203.%201.%20jpg[/img]

Всем спасибо за помощь!!!

Мне уже помогли написать эту программу с помощью рекурсии.

Вот исходник, если кому-нибудь он понадобится, то он к Вашим услугам:

Код: Выделить всё

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>

int n, m, *p, *q;
FILE *fp;

void Print()
{
	for(int i=0; i<m; i++){fprintf(fp, "%i ", q[p[i]]);}
	fprintf(fp, "\n");
}

int generator(int number, int nomer)
{
	if(number>n)return 0;

	for (int i=number; i<=n; i++)
	{
		p[nomer]=i;
		if(nomer==m){Print(); return 0;}
		p[nomer]=generator(i+1, nomer+1);
	}
	return 0;
}


main()
{
	clrscr();

	printf("‚ўҐ¤ЁвҐ Є®«ЁзҐбвў® н«Ґ¬Ґ­в®ў ў ¬­®¦Ґб⢥	");
	scanf("%d", &n);

	p=(int *)malloc(n*sizeof(int));
	q=(int *)malloc(n*sizeof(int));

	fp=fopen("C:\\Lang\\File.txt", "w");

	for(int i=0; i<n; i++)
	{
		printf("‚ўҐ¤ЁвҐ н«Ґ¬Ґ­в ­®¬Ґа %d	 ", i+1);
		scanf("%d", q+i);
	}

	for(i=1; i<=n; i++){m=i; generator(0, 0);}

	fclose(fp);
	getch();
	return 0;
}
Всем спасибо за помощь!!!

Lei fang
Сообщения: 49
Зарегистрирован: 28 май 2005, 20:25
Откуда: Саратов
Контактная информация:

Сообщение Lei fang » 01 июн 2005, 18:09

Как-то странно тут картинки вставляются...

Eugie
Сообщения: 707
Зарегистрирован: 17 фев 2004, 23:59
Откуда: SPb

Сообщение Eugie » 01 июн 2005, 18:13

Lei fang, то был VC++ 6.0 :)

Ответить