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: [email protected]
  • 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

 
Google Ads Remarketing

Thủ thuật cài đặt Google Adwords Remarketing vào website của bạn

Nếu đây là lần đầu tiên dùng Google Adwords, bạn buộc phải tạo chiến dịch adword đầu tiên và thêm thẻ thanh toán vào tài khoản Google Adwords của mình.

MarTechTalks #3: Slide tài liệu của các diễn giả

MarTechTalks #3: Slide tài liệu của các diễn giả

Tất cả chúng ta đều biết rằng, các trang web đang được truy cập nhiều nhất trên thế giới đều có một điểm chung. Facebook, Google, Yahoo, Youtube, CNN…

Thủ thuật tối ưu Video cho website

Thủ thuật tối ưu Video cho website

Để videos của bạn hiển thị thực tiếp trong trang kết quả tìm kiếm (Search Engine Results Page - SERP), bạn phải tối ưu hóa trang Web, videos và nội dung text xung quanh video.

BLOG POSTS

 

Wordpress Freelancer

 

Wordpress Freelancer