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

 
12 lý do nên thử dùng Ubuntu 10.10

12 lý do nên thử dùng Ubuntu 10.10

Ubuntu 10.10 đã thu hút được rất nhiều sự chú ý của người dùng, sẽ an toàn khi cá cược rằng số lượng lớn người dùng Ubuntu hiện có sẽ cập nhật lên phiên bản mới được ra mắt này.

Giới thiệu style guides trong content ở Drupal đáng xem

Giới thiệu style guides trong content ở Drupal đáng xem

It can mean different things in different contexts, but for front end development, it means a fully-realized

Hướng dẫn migrating content sang Drupal 8 năm 2015

Hướng dẫn migrating content sang Drupal 8 năm 2015

When Drupal 7 was released, it came with an upgrade script that would convert a Drupal 6 database into a Drupal 7 database

Tomdesgin.vn

 

Drupal Services