C/C++ - Liệt kê các hoán vị của tập n phần tử bằng thuật toán Back Track

C/C++ - Liệt kê các hoán vị của tập n phần tử bằng thuật toán Back Track

Xem lại lý thuyết thuật toán Back Track

>> Lý thuyết về thuật toán quay lui 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.

các hoán vị của tập n phần tử

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

}

 

Bạn thấy bài viết này như thế nào?: 
Average: 9.9 (103 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Trang thời tiết Weather Channel’s Journey chuyển sang Drupal

Trang thời tiết Weather Channel’s Journey chuyển sang Drupal

When my business partner, Paul Chason, and I joined forces over seven years ago we had a rather simple vision for Mediacurrent.

Cần Emotional Intelligence để Development tốt hơn trong Drupal 7

Cần Emotional Intelligence để Development tốt hơn trong Drupal 7

I am unabashedly an engineer. I obsess over the pursuit of finding the most efficient solution to any problem.

45.000 tài khoản Facebook bị đánh cắp

45.000 tài khoản Facebook bị đánh cắp

Báo cáo mới nhất của công ty bảo mật Symantec cho biết đã có trên 45.000 tài khoản người dùng Facebook bị sâu máy tính Ramnit đánh cắp...

Tomdesgin.vn

 

Drupal Services