Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Комбинаторика - булеан

Автор: nikitosinasuperman 20.3.2006, 15:53

Подскажите пожалуйста, как правильно организовать алгоритм нахождения всех двоичных чисел определенного разряда вот должно быть так:
000
001
010
100 - вот тут момент. если по правилу сложения двоичных чисел, то должна быть строка 011 вместо 100.
и тд
до
111

Но я немного покуражился, и сделал для 3-х разрадного числа алгоритм, помогиче написать для любого разряда алгоритм:

Код


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

main()
{clrscr();
 int a[4],n=4, k=0;
 for(int i=0;i<n;i++)
    {a[i]=0;
     printf("%d",a[i]);
    }
    printf("\n");
i=2;
    while(k!=(n-1))
    {
    do
        {

         while((i>k) && (a[i]==1))
            {
             a[i]=0;
             i=i-1;
            }
         if(i>=k) a[i]=1;

        for(int j=0;j<n;j++)
         printf("%d",a[j]);
         printf("\n");

        }while(i!=k);
      k=k+1;
      i=n-1;
      if(k==(n-1))
       {a[n-1]=1;
        for(i=0;i<n;i++)
        printf("%d",a[i]);
       }
     }
     printf("\n");
}

Автор: Romikgy 20.3.2006, 16:04

Какова максимальная разрядность будет?

Автор: nikitosinasuperman 20.3.2006, 16:11

а это имеет значение? ну для
10-ти smile

хотя бы

Автор: pablo 20.3.2006, 16:13

Я могу предложить следующее:

Например для 10 да и в общем для любого разряда: сначала записываем такое число нулей, числа которого разряда надо найти,
например для 10 это будет 0000000000, затем, заменяем самый правый(левый) нуль на 1, получаем 0000000001, потом двигаем эту единицу, влево: т.е, вместо левого нуля, ставим 1, пока не достигнем левого(правого) конца строки, соодтветсвенно получаем числа:
000000010, 000000100, 0000010000, и т.д. Потом производим выше описанную операцию но уже немного по другому, ставим на 2 самые правые(левые) позиции 2 единицы и двигаем самую левую единицу вправо, потом единицу которая стоит правее и т.д, т.е получим числа примерно такие: 0000000011, 0000000101, 0000001001, 0000010001, ..., 1000000001, потом чиля такого вида: 1000000010, 1000000100 1000001000 ... Проведя операцию для числа единиц равному порядку числа, мы найдём все возможные комбинации.

Автор: maxim1000 20.3.2006, 17:19

проще организовать прибавление единицы в двоичном коде:
если разряд, к которому добавляется единица нулевой, то просто меняем его на 1
если 1 - меняем на 0 и добавляем единицу уже к следующему разряду
пример:
101
001//начинаем с добавления единицы ксладшему разряду
------
100//если была единица, меняем на ноль
010//и прибавляем уже к следующему

100
001
------
101//если был ноль - просто меняем на ноль и больше ничего не делаем...

Автор: sdeniss 20.3.2006, 17:35

Цитата(maxim1000 @ 20.3.2006, 17:19

)

проще организовать прибавление единицы в двоичном коде:

посмотри статью про БПФ на alogolist.manual.ru там написано подробно про добавление "обратной 1"

Автор: MAKCim 20.3.2006, 18:52

Код


template<unsigned int _N> void generate()
{
    bool array__[_N]={0}, mask__;
    do
    {
        // в array__[0] ... array__[_N-1]   нужное число     

        unsigned int index__=_N-1;
        while (index__>=0 && array__[index__]) array__[index__--]=false;
        mask__=index__>=0;
        if (mask__) array__[index__]=true;
    }
    while (mask__);
}

естественно вместо стачического массива и шаблона можно использовать дин массивы, вектора и т .д
для больших _N будет работать медленно

Автор: maxim1000 20.3.2006, 19:10

Цитата(sdeniss @ 20.3.2006, 16:35

)

посмотри статью про БПФ на alogolist.manual.ru там написано подробно про добавление "обратной 1"

я там читал одну про реализацию сложения длинных чисел с помощью БПФ - она имеется в виду?
если да, то тут, как мне кажется, несколько другая ситуация: прибавление произвольного числа действительно можно ускорить спомощью БПФ, но прибавление одной единицы имеет сложность, пропорциональную длине числа, так что БПФ вряд ли его ускорит (т.к. у него n*log n)

Автор: darkart 20.3.2006, 19:25

Код


#include<iostream>
using namespace std;
const int MAX=3;//размерность массива
int main()
{
    int Arr[MAX];//описание массива
    char ch;//вспомогательная переменная
    memset(Arr,0,sizeof(Arr));
    do
    {
        cout<<"Bin Number:";
        for(int i=0;i<MAX;i++)//печать массива
            cout<<Arr[i];
        cout<<"\n";
        cout<<"Please enter your choice:\n"<<"n-next number\n"<<"q-exit\n";
        cin>>ch;//ввод выбранного действия
        if(ch=='n'||ch=='N')
        {
            int i=MAX-1;//последний разряд
            while(i>=0&&Arr[i])//пока на I-ом месте 1 ставим на это место 0
            {
                Arr[i]=0;
                i--;//переход к след. разряду
            }
            if(i<0)//перебрали все разряды
            {
                memset(Arr,0,sizeof(Arr));//обнуляем массив заново
            }
            else Arr[i]++;//ставим 1
        }
    }
    while(ch!='q'&&ch!='Q');
    return 0;
}

Автор: nikitosinasuperman 21.3.2006, 12:21

Сеня с универа приехал, осенило. написал сложением единиц. захожу сюда, а тут такую идею предложил максим smile

зацените:

Код


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

main()
{clrscr();
 int n;
 scanf("%d",&n);
 int*a=new int[n];
 printf("1. ");
 for(int i=0;i<n;i++)
    {a[i]=0;
     printf("%d",a[i]);
    }
printf("\n");
    for(i=0;i<pow(2,n)-1;i++)
        {a[n-1]+=1;
         for(int j=n-1;j>0;j--)
            if(a[j]==2)
                {a[j]=0;
                 a[j-1]=a[j-1]+1;
                }
             printf("%d. ",i+2);
        for(int k=0;k<n;k++)
            printf("%d",a[k]);
        printf("\n");
        }
delete[]a;
}

в нем может что-то не так? пишите smile

) мне нравится smile

Автор: Doc_d0s 21.3.2006, 17:00

методом деление, только вот узнать с какого разряда писать, можно загнать в цикл и проверить, если будет не лень накидаю код и скину smile