[Bài toán] Liệt kê các hoán vị của tập n phần tử bằng thuật toán Back Track

     Biểu diễn hoán vị dưới dạng p1, p2,.., pn, trong đó pi nhận giá trị từ 1 đến n và pi≠pj với i≠j. Các giá trị từ 1 đến n lần lượt được đề cử cho pi, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy, cần phải ghi nhớ với mỗi giá trị j xem nó đã được dùng hay chưa. Điều này được thực hiện nhờ một dãy các biến logic bj, trong đó bj= true nếu j chưa được dùng. Các biến này phải được khởi đầu giá trị true trong thủ tục Init. Sau khi gán j cho pi, cần ghi nhận false cho bj và phải gán true khi thực hiện xong Result hay Try(i+1). Hình sau mô tả cây tìm kiếm lời giải bài toán liệt kê hoán vị của 1, 2,.., n với n = 3.

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

#include  <stdio.h> 
#include  <conio.h> 
#include  <stdlib.h> 
#define MAX 100 
#define TRUE 1 
#define FALSE 0 
int P[MAX], B[MAX], n, count = 0;
void Init(void){
 int i;
 printf("\n Nhap n="); scanf("%d", &n);
 for (i = 1; i <= n; i++)
  B[i] = TRUE;
}
void Result(void){
 int i; count++;
 printf("\n Hoan vi thu %d:", count);
 for (i = 1; i <= n; i++)
  printf("%3d", P[i]);
 getch();
}
void Try(int i){
 int j;
 for (j = 1; j <= n; j++){
  if (B[j]) {
   P[i] = j;
   B[j] = FALSE;
   if (i == n) Result();
   else Try(i + 1);
   B[j] = TRUE;
  }
 }
}
void main(void){
 Init();
 Try(1);
}

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.