Hướng liệt kê dãy nhị phân theo yêu cầu

[anh1231 (Ngọc Anh)]

Liệt kê dãy nhị phân có độ dài N sao cho không có 2 bit 1 kề nhau.

Cho mình xin ý tưởng bài này với ạ. Có sử dụng đến phương pháp quay lui.

[Sherly1001]

Có sử dụng đến phương pháp quay lui.

Bạn cứ làm như bình thường thôi nhé.

Không nghĩ nổi cách nào thì cứ backtrack bình thường, liệt kê hết tất cả các hoán vị, rồi trước khi in ra thì kiểm tra hoán vị đó có thỏa mãn đề bài không.

void prt(int *a, int n) {
  for (int i = 0; i < n; ++i) printf("%d ", a[i]);
  printf("\n");
}

int check(int *a, int n) {
  for (int i = 1; i < n; ++i) if (a[i] == 1 && a[i] == a[i - 1]) return 0;
  return 1;
}

void try(int *a, int n, int i) {
  for (int j = 0; j <= 1; ++j) {
    a[i] = j;
    if (i == n - 1) {
      if (check(a, n)) prt(a, n);
    } else try(a, n, i + 1);
  }
}

void sher(int n) {
  int *a = (int*)calloc(n, sizeof(int));
  try(a, n, 0);
  free(a);
}

Viết ra như vậy rồi sẽ thấy việc viết hàm check như vậy là không cần thiết. Có thể rút ngắn thời gian chạy bằng cách thử a[i] một cách có suy nghĩ hơn.

Với mỗi lần thử a[i] thì kiểm tra xem a[i - 1] có bằng 1 không. Nếu có thì a[i] không được bằng 1 nữa.

void try(int *a, int n, int i) {
  for (int j = 0; j <= 1; ++j) {
    if (j == 1 && i > 0 && a[i - 1] == 1) break;
    a[i] = j;
    if (i == n - 1) prt(a, n);
    else try(a, n, i + 1);
  }
}