[Series] Thuật toán Sinh | Kì một: Sinh nhị phân

--- ---

Mục lục

---

Giới thiệu
Giới thiệu thuật toán
Quay lui nhị phân
Áp dụng giải thuật

Giới thiệu

Nhị phân là một chuỗi kí tự gồm [0,1] thường được dùng để biểu diễn các tín hiệu số trong môn Điện tử số(Kỹ thuật số PTIT), và được sử dụng bởi chính chiếc máy tính của chúng ta, những thao tác cực kì phức tạp cũng được biểu diễn bởi những dãy nhị phân. Vd: 001, 111, 111100110,…
Tất nhiên dãy nhị phân có quy luật cả đấy. Bây giờ chúng ta sẽ đi tìm cách để xây dựng bộ mã nhị phân nhé!

Giới thiệu thuật toán

---

Ví dụ:

• Một dãy nhị phân cấp 3: 000, 001, 010, 011, 100, 101, 110, 111
• Dãy nhị phân cấp 2: 00, 01, 10, 11
• Dãy nhị phân cấp n: sẽ có $2^n$ dãy

Thuật toán chúng ta dùng ở đây mình sẽ không chứng minh lại mà áp dụng kết quả luôn, các bạn có thể tự suy nghĩ từ các dãy, quy luật rất đơn giản

Thuật toán được phát biểu như sau:

• Bước khởi tạo: Khởi tạo tất cả các giá trị bằng 0
• Bước một: Duyệt từ cuối về đầu gặp số 0 đầu tiên thì đánh đấu là 1
• Bước hai: Đặt tất cả các số ở sau thành 0
• Bước ba: Lặp lại đến khi không tìm được số 0 nào nữa

Minh họa thuật toán:
Giả sử n = 3
Cấu hình đầu tiên: a = 000
Bước 1: thấy vị trí i=3 với a[i]=0 chuyển a[i]=1
Bước 2: từ 3+1=4 -> 3 chuyển về 0-> cấu hình tiếp 001
Lặp lại:
Bước 1: 001 thấy vị trí i=2 với a[i]=0 chuyển a[i]=1-> 011
Bước 2: từ vị trí i=2+1->3 chuyển về 0-> 010
Lặp lại:
…

Code:

#include <iostream>
using namespace std;
int a[20],n;
void Init() {
 cin>>n;
 for(int i = 1; i <= n; i++) 
  a[i] = 0;
}
void InCauHinh() {
 for (int i = 1; i <= n; i++) {
  cout << a[i];
 }
 cout << endl;
}
void SinhNhiPhan() {
 while(1) {
  InCauHinh();
  int i = n;
  while(i >= 1 && a[i] != 0) {
   i--;
  }
  if (i < 1) { // tức dãy hiện tại là 111..11
   break; // kết thúc
  }
  a[i] = 1; // đánh dấu lại thành 1, sau đó chuyển nửa bên kia =0
  for (int j = i + 1; j <= n; j++) {
   a[j] = 0;
  }
 }
}
int main() {
 Init();
 SinhNhiPhan();
}

Độ phức tạp: O($2^n)$ - vậy nên sinh tối đa chỉ đến khoảng 20-22 thôi nhé :v

Thuật toán trên khá là dài phải không, khó nhớ nữa :’(. Tuy nhiên chúng ta có cách ngắn hơn mà dễ hiểu chạy cũng ngang cái trên thôi :v

Quay lui sinh nhị phân

---

Ở các kỳ trước, chúng ta đã học về Backtracking(Quay lui). Vậy nên ta sẽ áp dụng nó vào thuật toán này! (Thực ra có rất nhiều thuật toán liên quan tới Quay lui đó)

Lướt lại tý nhé:
0 0
0 1
1 0
1 1
Thấy từng phần tử nó lặp theo quy luật là cứ 0 rồi sẽ thành 1 và ngược lại. Xem trên là vị trí 2 thì chu kì lặp là 1 đơn vị, vị trí 1 là 2 đơn vị.

Code:

#include <iostream>
using namespace std;
int a[20],n;
void Init() {
 cin>>n;
 for(int i = 1; i <= n; i++) 
  a[i] = 0;
}
void InCauHinh() {
 for (int i = 1; i <= n; i++) {
  cout << a[i];
 }
 cout << endl;
}
void Try(int i) { // Xác định vị trí i là 0 hay là 1
 for (int j = 0; j < 2; j++) {
  a[i] = j; // Tại vị trí i chỉ có thể thay thế bằng 0 hoặc 1
  if (i == n) {
   InCauHinh(); // Nếu đạt đủ độ dài dãy thì in ra
  } else {
   Try(i + 1); // Ngược lại xác định vị trí i + 1
  }
 }
}
int main() {
 Init();
 Try(1); // Bắt đầu từ vị trí 1
}

Áp dụng giải thuật

---

Sinh nhị phân áp dụng với rất nhiều bài tập mang tính “chọn lựa” - tức là có thể chọn hoặc không chọn.
Thôi thì nói nhiều lí thuyết quá, nhảy vào bài tập luôn cho nó đỡ buồn ngủ.
Link: https://www.spoj.com/PTIT/problems/BCCOW/
Tóm tắt đề bài cho ngắn: Cho n con bò với n cân nặng cho trước, chọn ra các con bò sao cho trọng lượng lớn nhất và không vượt quá M.

Phân tích bài toán:

• Bài này thuộc dạng sinh nhị phân
• Vậy mình có thể áp dụng như sau, nếu chọn con bò thứ i thì đánh dấu 1, không thì đánh dấu là 0
• Sau đó tính tổng các con được đánh dấu là 1 rồi tìm Max.
• Tức sẽ sinh nhị phân một dãy cấp n:
• Giả sử dãy mình đang xét là: 0001 thì tức là chỉ chọn con bò thứ 4 thôi.

Code:

#include <iostream>
using namespace std;
int a[20], n, w;
int result = 0;
int danhdau[20];
void Init() {
 cin>>w>>n;
 for (int i = 1; i <= n; i++) 
  cin >> a[i];
 for (int i = 1; i <= n; i++) 
  danhdau[i] = 0;
}
void Update() {
 int Sum=0;
 for(int i = 1; i <= n; i++) {
  if (danhdau[i]==1) {
   Sum += a[i];
  }
 }
 if (Sum < w) {
  if (Sum > result)
   result = Sum; // Nếu thỏa mãn yêu cầu thì cập nhật két quả
 }
}
void SinhNhiPhan() {
 while(1) {
  Update();
  int i = n;
  while(i >= 1 && danhdau[i] != 0) {
   i--;
  }
  if (i < 1) { // tức dãy hiện tại là 111..11
   break; // kết thúc
  }
  danhdau[i] = 1; // đánh dấu lại thành 1, sau đó chuyển nửa bên kia =0
  for (int j = i + 1; j <= n; j++) {
   danhdau[j] = 0;
  }
 }
}
int main() {
 Init();
 SinhNhiPhan();
 cout << result;
}

Luyện tập thêm nhiều bài tập nữa nhé!

Thank you