Chắc hẳn ai học về giải thuật cũng đã từng nghe qua và làm về bài toán đưa ra chuỗi nhị phân độ dài N rồi, nhưng nếu bạn vẫn chưa hoặc đang tìm hiểu. Vậy, trong bài viết này blog TUICOCACH.COM sẽ cùng các bạn tìm cách giải cũng như làm sao để tối ưu nhất cho thuật toán sinh dãy nhị phân có độ dài N với lập trình C/C++.
DANH SÁCH BÀI VIẾT Duyệt đồ thị, tìm kiếm đường đi dài nhất, đường đi ngắn nhất trong đồ thị Kiểm tra đồ thị liên thông trong bài toán đồ thị lập trình Sinh các chuỗi nhị phân có độ dài bằng n trong C/C++ Tìm dãy con có tổng trọng số lớn nhất trong lập trình C/C++ Tính A^n bằng phương pháp chia để trị Quy hoạch động tìm xâu con chung độ dài lớn nhất
Sinh các chuỗi nhị phân có độ dài bằng n
Chuỗi nhị phân là chuỗi chỉ bao gồm các số 0 và 1 và có độ dài nhất định. Sinh dãy nhị phân độ dài n chúng ta sẽ sinh tất cả các dãy nhị phân từ 000…(n số 0) tới 111…(n số 1).
Ví dụ n có độ dài là 3 ta sẽ có dãy nhị phân sau:
000
001
010
011
100
101
110
111
Mình sẽ sử dụng thuật toán quay lui để sinh dãy nhị phân độ dài bằng n, vậy viết chương trình như sau:
#include <iostream>
using namespace std;
int a[100];
void show(int n){
for(int i = 0; i<n; i++){
cout<<a[i];
}
cout<<"\n";
}
void Backtracking(int k, int n){
for(int i = 0; i<= 1; i++)
{
a[k] = i;
if(k == n-1){
show(n);
}
else{
Backtracking(k+1,n);
}
}
}
int main()
{
int n;
cout<<"Nhap n: ";
cin>>n;
Backtracking(0, n);
}
Kết quả chạy chương trình
Nếu bạn chưa hiểu chương trình trên có thể đọc thêm bài viết dưới đây.
[Xem tất cả bài viết chủ đề C/C++ tại đây]
