Bài tập liệt kê dãy nhị phân độ dài n bằng C/C++

Liệt kê dãy nhị phân độ dài n.

Viết dãy nhị phân dưới dạng b1b2..bn, trong đó bi∈{0, 1 }. Xem mỗi dãy nhị phân b=b1b2..bn là biểu diễn nhị phân của một số nguyên p(b). Khi đó thứ tự hiển nhiên nhất có thể xác định trên tập các dãy nhị phân là thứ tự từ điển được xác định như sau:

Ta nói dãy nhị phân b = b1b2..bn đi trước dãy nhị phân b’ = b’1b’2..b’n theo thứ tự từ điển và kí hiệu b<b’nếu p(b) <p(b’).

Ví dụ với n=4, các xâu nhị phân độ dài 4 được liệt kê theo thứ tự từ điển là:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

Như vậy, dãy đầu tiên là 0000 dãy cuối cùng là 1111. Nhận xét rằng, nếu xâu nhị phân chứa toàn bít 1 thì quá trình liệt kê kết thúc, trái lại dãy kế tiếp sẽ nhận được bằng cách cộng thêm 1(theo modul 2 có nhớ) vào dãy hiện tại.

Từ đó ta nhận được qui tắc sinh kế tiếp như sau:

1. Tìm i đầu tiên từ phải xang trái (i=n, n-1,..,1) thoả mãn bi =0.
2. Gán lại bi =1 và bj=0 với tất cả j>i. Dãy thu được là dãy cần tìm.

Ví dụ ta có xâu nhị phân độ dài 10: 1100111011. Ta có i = 8, ta đặt b8 =1, b9,b10 =0 ta được xâu nhị phân kế tiếp: 1100111100.

Thuật toán sinh kế tiếp được mô tả trong thủ tục sau:

#include<iostream>

using namespace std;

int n = 4;

int* arr;

bool nextBinary(int* arr){

 // in mảng.

 for(int j=0;j<n;j++){

  cout<<arr[j]<<" ";

 }

 cout<<endl;

 //sinh mảng binary kế tiếp

 int index = n -1;

 while(arr[index]==1 && index >= 0) index--;

 //mảng binary cuối cùng -> return false.

 if(index == -1) return false;

 arr[index] = 1;

 for(int i=index+1;i<n;i++){

  arr[i]=0;

 }

 return nextBinary(arr);

 

}

int main(){

 freopen("BINARY.OUT","w",stdout);

 //init first binary array.

 arr = new int[n];

 for(int i=0;i<n;i++){

  arr[i]=0;

 }

 nextBinary(arr);

 return 0;

}