Viết chương trình liệt kê các dãy nhị phân có độ dài n
Bài viết hôm nay mình sẽ hướng dẫn các bạn cách viết chương trình liệt kê các dãy nhị phân có độ dài n.(chuỗi nhị phân có độ dài n là chuỗi số có số chữ số bằng n và các chữ số trong chuỗi chỉ gồm 0 và 1.)
- Input
-
13
- Output
-
123456780 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1
NỘI DUNG BÀI VIẾT
Giới thiệu bài toán liệt kê các dãy nhị phân
Nhận xét: Chuỗi nhị phân có độ dài là n. Mỗi vị trí trong dãy sẽ có thể chọn 1 trong 2 số : 0 hoặc 1. Hay mỗi vị trí trong dãy đều có 2 cách chọn. Vì dãy có n vị trí, nên sẽ có tất cả 2^n khả năng xảy ra. Nói cách khác, sẽ có 2^n dãy nhị phân độ dài n.
Với ví dụ ở trên (n=3) ta sẽ có 2^3=8 dãy nhị phân khác nhau.
Trước khi tìm lời giải cho bài toán này các bạn thử để ý dãy nhị phân ở phía trên xem có đặc điểm gì không nhé! Dãy sẽ bắt đầu từ 000 (có giá trị 0) và kết thúc tại 111(có giá trị là 7). Như vậy dãy trên là một dãy tăng dần (tăng từ 0 đến 7). Nếu bạn chưa biết cách chuyển từ hệ 10 sang hệ nhị phân thì có thể xem lại tại đây.
Hướng dẫn giải bài toán liệt kê các dãy nhị phân
Sử dụng phương pháp sinh
Ta chỉ sử dụng phương pháp sinh để giải một bài toán khi :
- Chúng ta biết quy luật của bài toán liệt kê. Biết được cấu hình đầu và cấu hình cuối của bài toán.
- Từ một cấu hình hiện tại ta có thể tạo ra được cấu hình kế tiếp nó.
Với bài toán ở trên ta chỉ cần cấu hình đầu là 00…0 và cấu hình cuối 11…1 là có thể giải quyết được rồi phải không nào.
Ví dụ ở trên (n = 3 ) có cấu hình đầu là: 000 cấu hình sau nó là 001 tiếp nữa là 010. Vậy ý tưởng của mình là in ra cấu hình đầu tiên, sau đó lại tăng cấu hình đó lên và in ra tiếp. Quá trình cứ lặp đi lặp lại như vậy đến khi đã liệt kê hết tất cả cấu hình.
Có nhiều cách để tìm cấu hình sau, nhưng ở đây mình sẽ dùng chính quy tắc tăng của dãy để tìm. Tức là cấu hình sau bằng cấu hình trước một đơn vị.
Xây dựng chương trình
Đầu tiên mình sẽ tạo ra một mảng A[n] toàn các phần tử bằng 0. Sau đó để tìm cấu hình phía sau nó mình cộng thêm một đơn vị.
Nhưng lưu ý là chúng ta phải kiểm tra từ sau tới để tránh trường hợp có các cấu hình 100 101 102…
Ta xây dựng hàm gen(sinh ra các cấu hình) như sau:
|
1 2 3 4 5 6 7 8 9 |
void gen(int A[], int n) { ++A[n - 1]; for (int i = n - 1; i > 0; --i) { if (A[i] > 1) { ++A[i - 1]; A[i] -= 2; } } } |
Xây dựng hàm xuất
|
1 2 3 4 5 |
void xuat(int A[], int n) { for (int i = 0; i < n; i++) cout << A[i]; cout << endl; } |
Full code chương trình
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<iostream> #include<math.h> using namespace std; void gen(int A[], int n) { ++A[n - 1]; for (int i = n - 1; i > 0; --i) { if (A[i] > 1) { ++A[i - 1]; A[i] -= 2; } } } void xuat(int A[], int n) { for (int i = 0; i < n; i++) cout << A[i]; cout << endl; } int main(){ int n; cout << "Nhap n: "; cin >> n; //Khởi tạo mảng int *A = new int[n]; //Xây dựng cấu hình đầu tiên for (int i = 0; i < n; i++) A[i] = 0; //In cấu hình hiện tại và xây dựng cấu hình kế tiếp for (int i = 0; i < pow(2, n); i++) { xuat(A, n); gen(A, n); } } |
|
1 2 3 4 5 6 7 8 9 |
Nhap n: 3 000 001 010 011 100 101 110 111 |
Có một lưu ý nhỏ đó là chúng ta phải xác định trước có bao nhiêu cấu hình.
Bài viết mình đến đây cũng kết thúc. Cám ơn các bạn đã theo dõi !
