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 (102 votes)
Ảnh của Tommy Tran

Tommy Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
 CEO Facebook đã bay từ Lào Cai về lại Hà Nội

CEO Facebook đã bay từ Lào Cai về lại Hà Nội

Theo lái xe của công ty du lịch Đức Minh chở đoàn từ khách sạn Topas về thành phố Lào Cai từ 8 giờ 30 phút nhưng do yêu cầu đi chậm nên 10 giờ 30 đoàn mới tới vị trí...

Kiểm soát côn trùng chuột toàn diện - diệt chuột

Kiểm soát côn trùng chuột toàn diện - diệt chuột

Khi hợp đồng cũ hết thời hạn hiệu lực, hai bên có thể gia hạn hoặc ký hợp đồng dịch vụ mới cho năm kế tiếp

Cloud computing là một mô hình tính toán thương mại

Cloud computing là một mô hình tính toán thương mại

Khái niệm cloud computing (điện toán đám mây) ra đời từ năm 2007. Nửa năm sau đó, cloud computing đã nhận được sự quan tâm vượt hẳn grid computing (điện toán lưới). Dù vậy, đến tận bây giờ vẫn chưa có một định nghĩa thống nhất cho nó.

Cloud computing là một mô hình tính toán thương mại

BLOG POSTS