Bài toán liệt kê

#1

Mình đang làm bài bài toán liệt kê những xâu nhị phân 5 bit không chứa 2 số 0 liên tiếp theo thuật toán quay lui:

void Try(int i){
	for(int j=0;j<=1;j++){
		A[i] = j;
		if(A[i] == 0){
			A[i+1] = 1;
		}
		if(i == n){
		output();
		}
		else Try(i+1);
	}
}

Mình chạy nhưng kết quả ra sai, mọi người cho mình xin chút gợi ý cách tiếp cận khác nhé!
Thanks all !!!

#2

Gán bằng j (0-n) thế này mà là nhị phân (0, 1)!?

Trong vòng lặp lại còn dùng đệ quy.

Chỉ cần 1 vòng lặp, mỗi lần sẽ ngẫu nhiên giá trị 0 hoặc 1.
Mỗi lần đến vị trí tiếp theo, xét vị trí trước đó, nếu nó là 0 thì vị trí hiện tại bằng 1. Ngược là (!= 0) thì tiếp tục ngẫu nhiên.

1 Like
#3

Liệt kê sao random nhỉ :smiley:

Nếu sửa i+1 rồi thì phải lên i+2 thôi, nhưng điều kiện phải đặt phía trước.

3 Likes
#4 
#include <stdio.h>
#include <stdint.h>
#define SIZE 5      // Độ dài chuỗi nhị phân

int8_t A[SIZE + 1] = {1};

// Hàm in cấu hình
void PrintResult() {
    for(int i = 1; i <= SIZE; ++i) 
        printf("%d ", A[i]);

    printf("\n");
}
// Giải thuật BackTracking
void Try(int i) {
    for(int j = 0; j <= 1; ++j) {
        if(A[i - 1] == 0) j = 1;
        A[i] = j;
        if(i == SIZE) PrintResult();
        else Try(i + 1);
    }
}

int main()
{
    Try(1);
    return 0;
}
#5

Lý do kết quả sai
if(A[i] == 0) A[i+1] = 1;
Dòng này gán A[i+1] = 1
Nhưng khi gọi Try(i+1) sẽ lại gán A[i+1] = 0 lại !!!

#6

Mình đã hiểu rồi, cám ơn mấy bạn nhiều nhé !

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