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

Ответить

Код подтверждения
Введите код в точности так, как вы его видите. Регистр символов не имеет значения.
BBCode ВКЛЮЧЁН
[img] ВКЛЮЧЁН
[url] ВКЛЮЧЁН
Смайлики ОТКЛЮЧЕНЫ
Обзор темы
   

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

Lei fang » 02 июн 2005, 16:58

А жаль

dagrs » 02 июн 2005, 16:36

Точно

Lei fang » 02 июн 2005, 16:28

Как я понимаю это тоже VC++ 6.0?

dagrs » 02 июн 2005, 16:22

Алгоритм R.W.Gosper-а
используется для генерации последовательности подмножеств по возрастанию порядка от пустого, до всего множества.

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

#include <iostream>
#include <cmath>

using namespace std;

unsigned snoob( unsigned x )
{
    unsigned smallest, ripple, ones;

    smallest = x & -x;
    ripple   = x + smallest;
    ones     = x ^ ripple;
    ones     = (ones >> 2)/smallest;
    return   ripple | ones;
}

void outSet( unsigned x )
{
    cout << "{";
    if(!x) { cout << "}"; return; }

    int num = 1; // номер бита, начиная с 1
    for(;;)
    {
        if( x==1 ) { cout << num << "}"; return; }
        if( x&1 ) cout << num << ", ";
        x >>= 1;
        ++num;
    }
}

int main()
{
    unsigned N;
    cout << "Input order set N = ";
    cin >> N;
    cout << endl;

    unsigned Ord1 = unsigned(pow(2,N));

    // подмножества из K элементов
    for( unsigned K = 0; K <=N; ++K )
    {
        unsigned x         = unsigned(pow(2,K))-1; // min subSet
        unsigned maxSubSet = Ord1 - unsigned(pow(2,N-K));

        for(;;)
        {
            if( x == maxSubSet ) {  outSet(x); cout<< endl; break; }
            outSet(x); cout << ", ";
            x = snoob(x);
        }
    }

    return 0;
}

Lei fang » 01 июн 2005, 20:21

Ах... Вот еще... Эта программа не генерирует пустое подмножество.
Чтобы создавалось впечатление, что пустое подмножество генерируется, нужно в самом начале записать в файл символ "0"

Lei fang » 01 июн 2005, 19:30

Ах да... Вот что там написано:

printf("Введите количество элементов в множестве");

printf("Введите элемент номер %d ", i+1);

Lei fang » 01 июн 2005, 19:16

А понятно, а то я до сих пор не могу разобраться со скриншотом... Ну хорошо, теперь его не надо грузить на сервак
Еще раз спасибо тебе, Eugie.

Eugie » 01 июн 2005, 19:13

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

Lei fang » 01 июн 2005, 19:09

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

Lei fang » 01 июн 2005, 19: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;
}
Всем спасибо за помощь!!!

Вернуться к началу