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

 
Download Vector mẫu lịch tết năm 2020 - file Eps

Download miễn phí Vector mẫu lịch tết năm 2020 - file Eps

Sáng tạo luôn là điều cần thiết dù bạn làm bất cứ việc gì. Nó sẽ tạo ra bản sắc, sự khác biệt không giống với bất kỳ ai. Những mẫu thiệp truyền thống bao giờ cũng mang đến sự nhàm chán.

Thiết kế website: www.gemini-lights.com

Thiết kế website: www.gemini-lights.com

Gemini Lights is a high performance cycling light manufacturer. We design and build a range of bicycle lights to suit commuters, mountain bike buffs, and high-speed racers.

20 Hot iPhone 4S Accessories

20 Hot iPhone 4S Accessories

The new iPhone 4S has lots of new features like iOS 5 and Siri, the new iPhone 4S is much more than a phone.

Công ty diệt chuột T&C

 

Diet con trung