[Bài toán] Liệt kê dãy nhị phân độ dài n.

[Bài toán] Liệt kê dãy nhị phân độ dài n.
[Giải] 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;
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.