Thuật toán sinh xâu nhị phân kế tiếp

Nhập vào bàn phím:

  • số nguyên n là số bit của xâu nhị phân
  • số nguyên i: xâu nhị phân độ dài n có số bit 0 liên tiếp tối đa nhỏ hơn i
  • số nguyên k: xâu thứ k thỏa mãn 2 điều kiện trên

Output: hiển thị lên màn hình:xâu thứ k thỏa mãn có số bit 0 liên tiếp nhỏ hơn i theo thứ tự từ điển, nếu không tồn tại thì in ra -1
Bác nào làm bài này rồi xin gợi ý với thuật toán với, em làm mãi mà không ra kết quả ạ :wink:

https://xuanthanh.wordpress.com/2008/10/21/thu%E1%BA%ADt-toan-sinh-k%E1%BA%BF-ti%E1%BA%BFp-next-generation/ https://hocvachiaseblog.wordpress.com/2016/07/25/2-bai-toan-sinh-xau-nhi-phan-ke-tiep/
1 Like

Mở lại do hiểu lầm

1 Like

Vọc: đầu tiên tìm dãy min thỏa đề, sau đó thử tăng dần và nhận xét.

Làm mãi mà không ra, ai đó kiểm tra code mình sai ở đâu ạ :sunny:

indent preformatted text by 4 spaces
 #include<iostream>
#define MAX 1000000
using namespace std;
int a[MAX];
int n;// so bit nhi phan
int k;// so thu tu
int i;// so bit 0 lien tiep
int thutu =0;
int maxSubse0 = 0;
 bool isValid = true;

void solve(int j){//giai quyet truong hop bit thu i
    for(int v = 0;v<=1;v++){
    	    a[j] = v;	
	    if(v == 0){
		    maxSubse0++;
		    if(maxSubse0 >= i){
			    isValid = false;
		    }
	    }else{
		    maxSubse0 =0;
	    }
	    if(j ==(n-1)){
		    if(isValid){
			    thutu++;
			    if(thutu == k){
				        for(int v = 0; v < n; v++){
					    cout<<a[v]<<" ";
				    }cout<<endl;
			    }
		    }
	    }else{
		    solve(j+1);
	    }
	    //Reset stage
	    maxSubse0 = 0;
	    isValid = true;
    }
}		



 int main(){
    cin>>n;
    cin>>k;
    cin>>i;
    solve(0);
    return 0;
}

triển khai ý của bạn thêm vài steps cho mình hiểu rõ hơn đc ko

Clsoe theo yêu cầu

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?