01/10/2018, 17:35

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ả ạ

*grab popcorn* viết 19:50 ngày 01/10/2018

~~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/~~

*grab popcorn* viết 19:45 ngày 01/10/2018

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

rogp10 viết 19:44 ngày 01/10/2018

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

Nguyễn Văn Thịnh viết 19:51 ngày 01/10/2018

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

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;
}

Nguyễn Văn Thịnh viết 19:40 ngày 01/10/2018

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

*grab popcorn* viết 19:38 ngày 01/10/2018

Clsoe theo yêu cầu

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Nguyễn Văn Thịnh

0 chủ đề

0 bài viết

Tác giả nổi bật