[Bài toán] Liệt kê các xâu nhị phân độ dài n bằng thuật toán Back Track

Lý thuyết Back Track bạn có thể xem thêm ở đây.
     Biểu diễn các xâu nhị phân dưới dạng b1, b2,..., bn, trong đó bi∈{0, 1 }. Thủ tục đệ qui Try(i) xác định bi với các giá trị đề cử cho bi là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không cần phải thoả mãn điều kiện gì (do đó bài toán không cần đến biến trạng thái). thủ tục Init khởi tạo giá trị n và biến đếm count. thủ tục kết quả in ra dãy nhị phân tìm được. Chẳng hạn với n =3, cây tìm kiếm lời giải được thể hiện như hình.

Chương trình cài đặt:

#include <stdio.h> 
#include <alloc.h> 
#include <conio.h> 
#include <stdlib.h> 
void Result(int *B, int n){
 int i;
 printf("\n ");
 for (i = 1; i <= n; i++)
  printf("%3d", B[i]);
}
void Init(int *B, int n){
 int i;
 for (i = 1; i <= n; i++)
  B[i] = 0;
}
void Try(int i, int *B, int n){
 int j;
 for (j = 0; j <= 1; j++){
  B[i] = j;
  if (i == n) {
   Result(B, n);
  }
  else Try(i + 1, B, n);
 }
}
void main(void){
 int *B, n; clrscr();
 printf("\n Nhap n=");
 scanf("%d", &n);
 B = (int *)malloc(n*sizeof(int));
 Init(B, n);
 Try(1, B, n);
 free(B);
 getch();
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.