( Thuật toán quay lui) Liệt kê các dãy nhị phân có độ dài N

Biểu diễn dãy nhị phân có độ dài N dưới dạng  x[1...n]

Thử các giá trị {0, 1} gán cho x [ i ]. Với mỗi giá trị thử gán x[i]  lại thử các giá trị có thể gán cho x[i+1].


*

// Thuat toan quay lui liet ke cac xau nhi phan co do dai N

program BinaryStrings;
const

     InputFile = 'BSTR.INP';
     OutputFile = 'BSTR.OUT';
     max = 100;
     
var
     x : array[1...max] of integer;
     n : Integer;
     f : text;
     
procedure printResult; {In cau hinh tim duoc do thu tuc de quy Attempt goi moi khi tim duoc cau hinh}
var
     i : integer;
     begin
     for i := 1 to n do Write( f, x[i]);
     WriteLn(f);
     end;
     
procedure Attempt ( i: Integer);
var
     j: Integer;
     
begin
     for j:= 0 to 1 do { Xet cac gia tri co the gan cho x[i]}
       begin
            x[i] := j; {Thu dat x[i]}
            
            if ( i = n) printResult {Neu i = n thi in ket qua}
     
            else Attempt( i+1); {Neu i chua phai phan tu cuoi thi tim tiep x[i+1]}
            
     endl;
     
endl;

begin

      Assign( f,InputFile);Reset(f);
      ReadLn(f,n);{Nhap du lieu}
      close(f);
      Assign( f,OutputFile);Rewrite(f);
      Attempt(1);{Thu cac cach chon x[1]};
      close(f);
      
end.
 

// Implementation 
//Liet ke cac day nhi phan co do dai n su dung thuat toan quay lui

#include<iostream>
#include<fstream.h>
#define MAX 100

int n, a[MAX], sum = 0;
//n = do dai cua chuoi nhi phan
//sum = thu tu cua chuoi nhi phan tim duoc

void Init()
{
     ifstream f;
     f.open("IBSTR.txt");
     f>>n;
     f.close();
}
     

//Ham in ra chuoi nhi  phan

void printBinaryString()
{
     ofstream f;
     f.open("OBSTR.txt",std::ios::app);
     std::cout<<"\nChuoi nhi phan thu " <<++sum<<" : "<<std::endl;
     f<<"\nChuoi nhi phan thu " << sum<< " : "<<std::endl;
     for( int i =1;i<=n;++i)
     {
          std::cout<<" "<<a[i];
          f<<" "<<a[i];
     }
     std::cout<<std::endl;
     f<<std::endl;
     f.close();
     
}

void Attempt(int i) 
{
     int j;
     for( j = 0;j<=1;++j) // Khoi tao bo gia tri co the gan cho x[i]
     {
          a[i] = j;
          if( i == n)printBinaryString();
          else Attempt( i+1); //Tim tiep cac gia tri co the co cua x[i+1];
     }
}

main()
{
      Init();
      
      Attempt(1); //Tim cac gia tri co the co cua x[1];
      
      system("pause");
}