[Thuật Toán] Sinh các chuỗi nhị phân có độ dài n

THUẬT TOÁN SINH CÁC DÃY NHỊ PHÂN CÓ ĐỘ DÀI N

Một dãy nhị phân có độ dài n là một dãy x[1..n] trong đó x[i] ∈{0,1}
ví dụ 1 dãy nhị phân có độ dài = 3 :

chúng ta có thể liên hệ giữa số chuỗi nhị phân này với định nghĩa chỉnh hợp như sau :

cho tập X gồm 2 phần tử {0;1}
mỗi bộ( dãy ) gồm n phần tử từ 2 phần tử đã cho ta được 1 chỉnh hợp lặp chập n của 2.

như vậy,

với n = 3 thì số cấu hình ( hay số dãy nhị phân ) = 8 ( như trên hình ban đầu ).


ta nhận thấy cấu hình đầu tiên sẽ là 00…0 và cấu hình cuối cùng sẽ là 11…1.

Nhận xét rằng nếu cấu hình x[1..n] là cấu hình đang có và không phải cấu hình cuối cùng cần liệt kê thì dãy kế tiếp sẽ nhận được bằng cách cộng thêm 1 ( theo cơ số 2 có nhớ) vào cấu hình hiện tại.

như vậy, phương pháp sinh đã được thỏa mãn 2 điều kiện đó là : biết được cấu hình đầu-cuối ; thuật toán sinh được cấu hình tiếp theo từ cấu hình trước nó.

chúng ta sẽ sử dụng phương pháp sinh để "đẻ" ra các cấu hình thỏa mãn đề bài như sau :

xét từ cuối dãy đi lên, gặp số 0 đầu tiên : 
* nếu thấy thì thay số 0 bằng số 1 và đặt tất cả phần tử sau vị trí đó = 0.
* nếu không thấy thì dãy toàn số 1, đây là cấu hình cuối cùng.

code của chương trình như sau :

#include<iostream>
using namespace std;
int n, a[10];
bool check = false;            // tạo 1 biến kiểu bool để kiểm tra xem đã đến cấu hình cuối chưa
void display(){  // hiển thị cấu hình ra màn hình
 for (int i = 1; i <= n; i++){
  cout << a[i];
 }
 cout << endl;
}
void nextString(){
 int i = n;
 while (a[i]==1 && i > 0){
  i--;
 }
 if (i == 0) check = true; // nếu i=0 tức là đã đến cấu hình cuối, gán biến check = true
 else
 {
  a[i] = 1;    // còn không thì gán a[i]=1
  for (int j = i + 1; j <= n; j++){
   a[j] = 0;   // gán tất cả phần tử phía sau a[i] =0
  }
 }
}
void main(){
 cout << " nhap do dai day nhi phan";
 cin >> n;
 for (int i = 1; i <= n; i++){   // cấu hình đầu tiên gồm toàn số 0
  a[i] = 0;
 }
 while (!check){
  display();       // hiển thị cấu hình
  nextString();      // sinh cấu hình tiếp theo
 }
 system("pause");
}

bài viết chắc chắn còn nhiều thiếu sót rất mong bạn đọc góp ý qua email : trieuhiepptit@gmail.com Thanks for reading !