Toán rời rạc _Thao tác với xâu nhị phân_Bài 4

Bài 4:

Hãy duyệt tất cả các xâu nhị phân có độ dài n sao cho:

Xâu có duy nhất :

k số 0 liên tiếp

m số  1 liên tiếp

Ví dụ :

n =7, k =2,  m=3:   0100111 thỏa mãn:

//Code implementation:

//10_20_2011.cpp
#include"iostream"
using namespace std;

int n,k,m, *X, OK = 1, sum = 0;

void Init()
{
      cout<<"\nNhap do dai cua xau nhi phan = "; cin >>n;
      X = new int [n];
      for( int i=1; i<=n; i++)
      X[i]=0;
      cout<<"\nNhap so so 0 lien tiep : "; cin>> k;
      cout<<"\nNhap so so 1 lien tiep : "; cin>> m;
      
}

void Next_Bit_String()
{
     int i =n;
     while( i > 0 && X[i]) 
     {
            X[i] = 0;
            i--;
     }
     
     if( i>0)X[i] = 1;
     else OK = 0;
}

int Test()
{
    int dem0 =0, dem1 = 0, day0 =0, day1 = 0;
    for( int i=1; i<=n;i++)
    {
         if(X[i]==0)
         {
                    dem0 ++;
                    dem1 = 0;
                    if(dem0 >= k) day0 ++;
         }
         else
         {
             dem1 ++;
             dem0 = 0;
             if(dem1 >= m) day1 ++;
         }
    }
    
    if(day0 == 1 && day1 == 1) return 1;
    return 0;
}

void Result()
{
     cout<<"\nDay thu " << ++sum << "thoa man:\n ";
     for( int i=1; i<=n;i++)
       cout << X[i];
}

int main()
{
    Init();
    while(OK)
    {           
            if( Test()) Result();
            Next_Bit_String();
    }
    cout<< endl;
    delete(X);
    system("pause");
    return 0;
}