Thứ Năm, 1 Tháng Mười Hai 2022
Trang chủLập trìnhCTDL & Thuật toánSinh các chuỗi nhị phân có độ dài bằng n trong C/C++...

Sinh các chuỗi nhị phân có độ dài bằng n trong C/C++ – Thuật toán

XEM THÊM
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

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++.

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]

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x