Lập trình C/C++

4 bài tập cơ bản của Thuật toán quay lui và bài tập tham khảo trong C++ (Full Code)

Posted on by Đỗ Thành
Học lập trình
10
Th1
View: 67

I. LÝ THUYẾT

Thuật toán quay lui (Backtracking) là một kỹ thuật giải quyết vấn đề bằng cách xây dựng dần các giải pháp ứng viên và loại bỏ những giải pháp không phù hợp. Trong C++, bạn có thể sử dụng đệ quy để hiện thực hóa thuật toán quay lui.

Cấu trúc cơ bản của thuật toán quay lui:

  1. Bắt đầu từ trạng thái ban đầu.
  2. Thử mỗi lựa chọn có thể tại trạng thái hiện tại.
    • Nếu lựa chọn đó hợp lệ:Tiến hành bước tiếp theo (gọi đệ quy).
    • Nếu lựa chọn không hợp lệ:
    • Bỏ qua lựa chọn đó (backtrack).
  3. Nếu đạt được trạng thái đích (lời giải), dừng lại.

II. BÀI TẬP

Bài 1. Xâu nhị phân

Thuật toán sinh dãy nhị phân bằng thuật toán quay lui là một cách tiếp cận đệ quy để tạo ra tất cả các dãy nhị phân có độ dài n. Quay lui là một kỹ thuật sử dụng đệ quy để thử tất cả các giá trị có thể cho một phần của giải pháp và sau đó quay trở lại và thử các giá trị khác.

Đặc điểm chính:

  1. Cơ sở (Base case): Khi độ dài của dãy nhị phân đạt đến n, chúng ta sẽ không thể thêm các bit khác nữa và chúng ta sẽ in ra dãy nhị phân đã tạo được.
  2. Bước đệ quy (Recursive step): Mỗi lần đệ quy, chúng ta sẽ thêm một bit 0 hoặc 1 vào dãy nhị phân và sau đó tiếp tục đệ quy để thử tất cả các trường hợp có thể.

Vector:

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> x;

void inkq() {
    for (int i = 1; i <= n; i++)
        cout << x[i];
    cout << endl;
}

void Try(int i) {
    // Duyệt qua các khả năng của x[i]
    for (int j = 0; j <= 1; j++) {
        x[i] = j;
        if (i == n) inkq();
        else Try(i + 1);
    }
}

int main() {
    cin >> n;
    x.resize(n + 1);
    Try(1);
    return 0;
}

Mảng:

#include <iostream>
using namespace std;
int n, x[100];
void inkq() {
    for(int i = 1; i <= n; i++)
        cout << x[i];
    cout << endl;
}
void Try(int i) {
    // duyet qua cac kha nang cua x[i]
    for (int j = 0; j <= 1; j++) {
         x[i] = j;
         if (i == n) inkq();
         else Try(i + 1);
    }
}
int main() {
    cin >> n;
    Try(1);
    return 0;
}

Bài 2. Tổ hợp chập k của n phần tử

Thuật toán sinh tổ hợp chập k của n phần tử bằng thuật toán quay lui là một cách tiếp cận đệ quy để tạo ra tất cả các tổ hợp chập k từ tập hợp gồm n phần tử. Quay lui là một kỹ thuật sử dụng đệ quy để thử tất cả các giá trị có thể cho một phần của giải pháp và sau đó quay trở lại và thử các giá trị khác.

Đặc điểm chính:

  1. Cơ sở (Base case): Khi số lượng phần tử đã chọn đủ k, chúng ta sẽ in ra tổ hợp đã tạo được.
  2. Bước đệ quy (Recursive step): Mỗi lần đệ quy, chúng ta sẽ thêm một phần tử mới vào tổ hợp và tiếp tục đệ quy để thử tất cả các trường hợp có thể.

Vector:

#include <iostream>
#include <vector>
using namespace std;

int n, k;
vector<int> x;

void inkq() {
    for (int i = 1; i <= k; i++)
        cout << x[i];
    cout << endl;
}

void Try(int i) {
    // Duyệt qua các khả năng mà x[i] có thể nhận được
    // Giá trị lớn nhất: n - k + i, nhỏ nhất: x[i-1] + 1
    for (int j = x[i-1] + 1; j <= n - k + i; j++) {
        x[i] = j;
        if (i == k) inkq();
        else Try(i + 1);
    }
}

int main() {
    cin >> n >> k;
    x.resize(k + 1, 0);
    Try(1);
    return 0;
}

Mảng:

#include <iostream>
using namespace std;
int n, k, x[100];
void inkq() {
    for(int i = 1; i <= k; i++)
        cout << x[i];
    cout << endl;
}
void Try(int i) {
    // duyet qua cac kha nang ma x[i] co the nhan duoc
    // Gia tri lon nhat: n - k + i, nho nhat: x[i-1] + 1
    for (int j = x[i-1] + 1; j <= n - k + i; j++) {
         x[i] = j;
         if (i == k) inkq();
         else Try(i + 1);
    }
}
int main() {
    cin >> n >> k;
    Try(1);
    return 0;
}

Bài 3. Sinh hoán vị

Đầu vào:

  • Một mảng chứa các phần tử cần sinh hoán vị.
  • Hai chỉ số l và r, lần lượt là chỉ số đầu và cuối của mảng.

Thuật toán:

  1. Cơ sở (Base case): Nếu l == r, có nghĩa là tất cả các phần tử đã được xác định vị trí trong hoán vị. Chúng ta in ra hoán vị hiện tại.
  2. Bước đệ quy (Recursive step):
    1. Lặp qua tất cả các chỉ số i từ l đến r:
      1. Hoán đổi vị trí của hai phần tử tại vị trí l và vị trí i trong mảng.
      1. Đệ quy tiếp tục với l tăng lên 1 để xác định vị trí tiếp theo trong hoán vị.
      1. Quay lui bằng cách hoán đổi lại vị trí của hai phần tử để tiếp tục với các trường hợp khác.

Vector:

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> x, u;

void inkq() {
    for (int i = 1; i <= n; i++)
        cout << x[i];
    cout << endl;
}

void Try(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0) { // Xét xem giá trị j đã được sử dụng chưa?
            x[i] = j;
            u[j] = 1; // Đánh dấu đã chọn
            if (i == n) inkq();
            else Try(i + 1);
            u[j] = 0; // Quay lui tại đây
        }
    }
}

int main() {
    cin >> n;
    x.resize(n + 1);
    u.resize(n + 1, 0);
    Try(1);
    return 0;
}

Mảng:

#include <iostream>
using namespace std;
int n, k, x[100], u[100];

void inkq() {
    for(int i = 1; i <= n; i++)
        cout << x[i];
    cout << endl;
}
void Try(int i) {
    for (int j = 1; j <= n; j++) {
         if(u[j] == 0) { // Xet xem gia tri j da duoc su dung chua?
            x[i] = j;
            u[j] = 1; // Danh dau da chon
         }
         if (i == n) inkq();
         else Try(i + 1);
         u[j] = 0; // Quay lui tai day
    }
}
int main() {
    cin >> n;
    Try(1);
    return 0;
}

Bài 4. Sinh phân hoạch

Vector:

#include <iostream>
#include <vector>
using namespace std;

// Hàm đệ quy để tìm cách phân tích số N
void decompose(int n, vector<int>& result, int start) {
    if (n == 0) {
        // Nếu tổng đạt yêu cầu, in ra tổ hợp hiện tại
        for (size_t i = 0; i < result.size(); ++i) {
            if (i > 0) cout << " + ";
            cout << result[i];
        }
        cout << endl;
        return;
    }

    // Duyệt qua các số từ start đến n
    for (int i = start; i <= n; ++i) {
        result.push_back(i); // Thêm số vào tổ hợp
        decompose(n - i, result, i); // Đệ quy với tổng còn lại
        result.pop_back(); // Loại bỏ số để thử số khác
    }
}

int main() {
    int N;
    cin >> N;
    vector<int> result;
    decompose(N, result, 1);

    return 0;
}

Mảng:

#include <bits/stdc++.h>
using namespace std;

int n, a[100];

void show(int k) {
    cout << n << " = ";
    for (int i = 1; i <= k; i++) {
        if (i > 1) cout << " + ";
        cout << a[i];
    }
    cout << endl;
}

void pt(int i, int sum, int prev) {
    for (int j = prev; j <= n - sum; j++) {
        a[i] = j; // Gán giá trị hiện tại vào tổ hợp
        if (sum + j == n) {
            show(i); // In ra nếu tổng đạt giá trị n
        } else {
            pt(i + 1, sum + j, j); // Đệ quy với tổng tăng thêm j và giới hạn j
        }
    }
}

int main() {
    cin >> n;    
    pt(1, 0, 1); // Bắt đầu với chỉ số 1, tổng là 0, giá trị trước là 1
    return 0;
}

Tham khảo: Bài toán N-Queens

#include <iostream>
#include <vector>
using namespace std;

bool isSafe(vector<int>& x, int row, int col) {
    for (int i = 1; i < row; i++) {
        if (x[i] == col || abs(x[i] - col) == abs(i - row)) return false;
    }
    return true;
}

void backtrack(int row, int n, vector<int>& x) {
    if (row > n) {
        for (int i = 1; i <= n; i++) cout << x[i] << " ";
        cout << endl;
        return;
    }
    for (int col = 1; col <= n; col++) {
        if (isSafe(x, row, col)) {
            x[row] = col;
            backtrack(row + 1, n, x);
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of queens: ";
    cin >> n;
    vector<int> x(n + 1);
    backtrack(1, n, x);
    return 0;
}

Bài tập khai thác dãy nhị phân:

Bài 1. Sinh toàn bộ dãy nhị phân

Viết chương trình sinh tất cả các dãy nhị phân có n phần tử.

Bài 2. Sinh dãy nhị phân theo thứ tự ngược

Viết chương trình sinh tất cả các dãy nhị phân có n phần tử, nhưng theo thứ tự ngược (từ 2n – 1 đến 0).

Bài 3. Đếm số dãy có số lượng bit 1 cụ thể

Viết chương trình sinh tất cả các dãy nhị phân có n phần tử và đếm số dãy chứa đúng k bit 1 (0 ≤ k ≤ n).

Bài 4. Sinh dãy nhị phân thỏa mãn điều kiện liên tiếp

Viết chương trình sinh tất cả các dãy nhị phân có n phần tử sao cho không có hai số 1 nào đứng liền nhau.

Bài 5. Sinh dãy nhị phân có số phần tử cố định

Viết chương trình sinh tất cả các dãy nhị phân có nnn phần tử và chứa đúng k bit 1.

Bài 6. Sinh dãy nhị phân dạng đối xứng

Viết chương trình sinh tất cả các dãy nhị phân có nnn phần tử và đối xứng qua trung điểm (ví dụ: 11011 là đối xứng).

Bài 7. Sinh dãy nhị phân theo thứ tự từ điển

Viết chương trình sinh tất cả các dãy nhị phân có nnn phần tử theo thứ tự từ điển.

Bài 8. Sinh dãy nhị phân có tổng phần tử lẻ

Viết chương trình sinh tất cả các dãy nhị phân có nnn phần tử sao cho tổng giá trị các phần tử ở vị trí lẻ là lẻ.

Bài 9. Sinh dãy nhị phân chỉ chứa số 0 ở vị trí chẵn

Viết chương trình sinh tất cả các dãy nhị phân có n phần tử sao cho tất cả các vị trí chẵn (0, 2, 4, …) chỉ chứa số 0.

Bài 10. Sinh dãy nhị phân không chứa chuỗi con liên tiếp

Viết chương trình sinh tất cả các dãy nhị phân có nnn phần tử sao cho không chứa chuỗi con 111.

Code tham khảo:

#include <iostream>
#include <vector>
using namespace std;

int n, k;
vector<int> x;

void inkq() {
    for (int i = 1; i <= n; i++)
        cout << x[i];
    cout << endl;
}

// Bài 1: Sinh toàn bộ dãy nhị phân
void Try1(int i) {
    for (int j = 0; j <= 1; j++) {
        x[i] = j;
        if (i == n) inkq();
        else Try1(i + 1);
    }
}

// Bài 2: Sinh dãy nhị phân theo thứ tự ngược
void Try2(int i) {
    for (int j = 1; j >= 0; j--) {
        x[i] = j;
        if (i == n) inkq();
        else Try2(i + 1);
    }
}

// Bài 3: Đếm số dãy có số lượng bit 1 cụ thể
int countBit1() {
    int count = 0;
    for (int i = 1; i <= n; i++)
        if (x[i] == 1) count++;
    return count;
}
void Try3(int i) {
    for (int j = 0; j <= 1; j++) {
        x[i] = j;
        if (i == n) {
            if (countBit1() == k) inkq();
        } else Try3(i + 1);
    }
}

// Bài 4: Sinh dãy nhị phân thỏa mãn điều kiện liên tiếp
void Try4(int i) {
    for (int j = 0; j <= 1; j++) {
        if (j == 1 && x[i - 1] == 1) continue;
        x[i] = j;
        if (i == n) inkq();
        else Try4(i + 1);
    }
}

// Bài 5: Sinh dãy nhị phân có số phần tử cố định
void Try5(int i, int cnt) {
    for (int j = 0; j <= 1; j++) {
        x[i] = j;
        if (i == n) {
            if (cnt + j == k) inkq();
        } else Try5(i + 1, cnt + j);
    }
}

// Bài 6: Sinh dãy nhị phân dạng đối xứng
void Try6(int i) {
    for (int j = 0; j <= 1; j++) {
        x[i] = x[n - i + 1] = j;
        if (i >= n / 2) inkq();
        else Try6(i + 1);
    }
}

// Bài 7: Sinh dãy nhị phân theo thứ tự từ điển
void Try7(int i) {
    for (int j = 0; j <= 1; j++) {
        x[i] = j;
        if (i == n) inkq();
        else Try7(i + 1);
    }
}

// Bài 8: Sinh dãy nhị phân có tổng phần tử lẻ
void Try8(int i) {
    for (int j = 0; j <= 1; j++) {
        x[i] = j;
        if (i == n) {
            int sum = 0;
            for (int k = 1; k <= n; k += 2) sum += x[k];
            if (sum % 2 == 1) inkq();
        } else Try8(i + 1);
    }
}

// Bài 9: Sinh dãy nhị phân chỉ chứa số 0 ở vị trí chẵn
void Try9(int i) {
    for (int j = 0; j <= 1; j++) {
        if (i % 2 == 0 && j == 1) continue;
        x[i] = j;
        if (i == n) inkq();
        else Try9(i + 1);
    }
}

// Bài 10: Sinh dãy nhị phân không chứa chuỗi con 111
bool check10() {
    for (int i = 3; i <= n; i++)
        if (x[i] == 1 && x[i - 1] == 1 && x[i - 2] == 1)
            return false;
    return true;
}
void Try10(int i) {
    for (int j = 0; j <= 1; j++) {
        x[i] = j;
        if (i == n) {
            if (check10()) inkq();
        } else Try10(i + 1);
    }
}

Bài tập khai thác tổ hợp chập k của n:

Bài 1. Sinh tất cả tổ hợp chập k của n

Viết chương trình sinh tất cả tổ hợp chập k của n.

Bài 2. Sinh tổ hợp chập k theo thứ tự ngược

Viết chương trình sinh tất cả tổ hợp chập k của n theo thứ tự ngược (bắt đầu từ tổ hợp lớn nhất).

Bài 3. Sinh tổ hợp có tổng giá trị chỉ số lẻ

Viết chương trình sinh tất cả tổ hợp chập k của nnn sao cho tổng các chỉ số trong tổ hợp là số lẻ.

Bài 4. Sinh tổ hợp không chứa phần tử đầu tiên

Viết chương trình sinh tất cả tổ hợp chập k của n mà không chứa phần tử đầu tiên (chỉ số 1).

Bài 5. Sinh tổ hợp chỉ chứa số lẻ

Viết chương trình sinh tất cả tổ hợp chập k của n sao cho tất cả các chỉ số trong tổ hợp đều là số lẻ.

Bài 6. Sinh tổ hợp có phần tử liên tiếp

Viết chương trình sinh tất cả tổ hợp chập k của n sao cho có ít nhất hai phần tử liên tiếp.

Bài 7. Sinh tổ hợp thỏa mãn điều kiện tổng

Viết chương trình sinh tất cả tổ hợp chập k của n sao cho tổng các phần tử trong tổ hợp lớn hơn một giá trị S cho trước.

Bài 8. Sinh tổ hợp không chứa số chẵn

Viết chương trình sinh tất cả tổ hợp chập k của n sao cho không chứa bất kỳ số chẵn nào.

Bài 9. Sinh tổ hợp chỉ chứa số nguyên tố

Viết chương trình sinh tất cả tổ hợp chập k của n sao cho tất cả các phần tử trong tổ hợp đều là số nguyên tố.

Bài 10. Sinh tổ hợp có độ chênh lệch nhỏ nhất

Viết chương trình sinh tất cả tổ hợp chập k của n sao cho độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong tổ hợp là nhỏ nhất.

Code tham khảo:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n, k, S;
vector<int> x;

void inkq() {
    for (int i = 1; i <= k; i++)
        cout << x[i] << " ";
    cout << endl;
}

// Bài 1: Sinh tất cả tổ hợp chập k của n
void Try1(int i) {
    for (int j = x[i - 1] + 1; j <= n - k + i; j++) {
        x[i] = j;
        if (i == k) inkq();
        else Try1(i + 1);
    }
}

// Bài 2: Sinh tổ hợp chập k theo thứ tự ngược
void Try2(int i) {
    for (int j = n - k + i; j >= x[i - 1] + 1; j--) {
        x[i] = j;
        if (i == k) inkq();
        else Try2(i + 1);
    }
}

// Bài 3: Sinh tổ hợp có tổng giá trị chỉ số lẻ
void Try3(int i) {
    for (int j = x[i - 1] + 1; j <= n - k + i; j++) {
        x[i] = j;
        if (i == k) {
            int sum = 0;
            for (int l = 1; l <= k; l++) sum += x[l];
            if (sum % 2 == 1) inkq();
        } else Try3(i + 1);
    }
}

// Bài 4: Sinh tổ hợp không chứa phần tử đầu tiên
void Try4(int i) {
    for (int j = max(2, x[i - 1] + 1); j <= n - k + i; j++) {
        x[i] = j;
        if (i == k) inkq();
        else Try4(i + 1);
    }
}

// Bài 5: Sinh tổ hợp chỉ chứa số lẻ
void Try5(int i) {
    for (int j = x[i - 1] + 1; j <= n - k + i; j++) {
        if (j % 2 == 0) continue;
        x[i] = j;
        if (i == k) inkq();
        else Try5(i + 1);
    }
}

// Bài 6: Sinh tổ hợp có phần tử liên tiếp
bool check6() {
    for (int i = 2; i <= k; i++)
        if (x[i] - x[i - 1] == 1) return true;
    return false;
}
void Try6(int i) {
    for (int j = x[i - 1] + 1; j <= n - k + i; j++) {
        x[i] = j;
        if (i == k) {
            if (check6()) inkq();
        } else Try6(i + 1);
    }
}

// Bài 7: Sinh tổ hợp thỏa mãn điều kiện tổng
void Try7(int i) {
    for (int j = x[i - 1] + 1; j <= n - k + i; j++) {
        x[i] = j;
        if (i == k) {
            int sum = 0;
            for (int l = 1; l <= k; l++) sum += x[l];
            if (sum > S) inkq();
        } else Try7(i + 1);
    }
}

// Bài 8: Sinh tổ hợp không chứa số chẵn
void Try8(int i) {
    for (int j = x[i - 1] + 1; j <= n - k + i; j++) {
        if (j % 2 == 0) continue;
        x[i] = j;
        if (i == k) inkq();
        else Try8(i + 1);
    }
}

// Bài 9: Sinh tổ hợp chỉ chứa số nguyên tố
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); i++)
        if (num % i == 0) return false;
    return true;
}
void Try9(int i) {
    for (int j = x[i - 1] + 1; j <= n - k + i; j++) {
        if (!isPrime(j)) continue;
        x[i] = j;
        if (i == k) inkq();
        else Try9(i + 1);
    }
}

// Bài 10: Sinh tổ hợp có độ chênh lệch nhỏ nhất
void Try10(int i, int &minDiff) {
    for (int j = x[i - 1] + 1; j <= n - k + i; j++) {
        x[i] = j;
        if (i == k) {
            int diff = x[k] - x[1];
            if (diff < minDiff) {
                minDiff = diff;
                inkq();
            }
        } else Try10(i + 1, minDiff);
    }
}

Bài tập khai thác Sinh hoán vị:

Bài 1. Sinh tất cả các hoán vị

Viết chương trình sinh tất cả các hoán vị của n phần tử.

Bài 2. Sinh hoán vị theo thứ tự ngược

Viết chương trình sinh tất cả các hoán vị của n phần tử theo thứ tự ngược (bắt đầu từ hoán vị lớn nhất).

Bài 3. Sinh hoán vị chỉ chứa số lẻ

Viết chương trình sinh tất cả các hoán vị của n phần tử sao cho chỉ chứa các số lẻ.

Bài 4. Sinh hoán vị không chứa số nguyên tố

Viết chương trình sinh tất cả các hoán vị của nnn phần tử sao cho không chứa số nguyên tố.

Bài 5. Sinh hoán vị có tổng các phần tử là số chẵn

Viết chương trình sinh tất cả các hoán vị của n phần tử sao cho tổng các phần tử trong hoán vị là một số chẵn.

Bài 6. Sinh hoán vị có hai phần tử liên tiếp chênh lệch nhỏ nhất

Viết chương trình sinh tất cả các hoán vị của n phần tử sao cho trong mỗi hoán vị, hai phần tử liên tiếp có độ chênh lệch nhỏ nhất.

Bài 7. Sinh hoán vị không chứa cặp số liên tiếp chênh lệch lớn hơn 2

Viết chương trình sinh tất cả các hoán vị của nnn phần tử sao cho không có cặp số liên tiếp nào chênh lệch lớn hơn 2.

Bài 8. Sinh hoán vị đối xứng

Viết chương trình sinh tất cả các hoán vị của nnn phần tử sao cho hoán vị đó đối xứng (giống nhau khi đảo ngược).

Bài 9. Sinh hoán vị không chứa số lẻ ở vị trí chẵn

Viết chương trình sinh tất cả các hoán vị của n phần tử sao cho không có số lẻ ở vị trí chẵn.

Bài 10. Sinh hoán vị chứa số lớn nhất ở giữa

Viết chương trình sinh tất cả các hoán vị của nnn phần tử sao cho phần tử lớn nhất luôn nằm ở vị trí giữa (nếu n lẻ) hoặc một trong hai vị trí giữa (nếu n chẵn).

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
vector<int> x, u;

void inkq() {
    for (int i = 1; i <= n; i++)
        cout << x[i] << " ";
    cout << endl;
}

bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); i++)
        if (num % i == 0) return false;
    return true;
}

// Bài 1: Sinh tất cả các hoán vị
void Try1(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0) {
            x[i] = j;
            u[j] = 1;
            if (i == n) inkq();
            else Try1(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 2: Sinh hoán vị theo thứ tự ngược
void Try2(int i) {
    for (int j = n; j >= 1; j--) {
        if (u[j] == 0) {
            x[i] = j;
            u[j] = 1;
            if (i == n) inkq();
            else Try2(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 3: Sinh hoán vị chỉ chứa số lẻ
void Try3(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0 && j % 2 == 1) {
            x[i] = j;
            u[j] = 1;
            if (i == n) inkq();
            else Try3(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 4: Sinh hoán vị không chứa số nguyên tố
void Try4(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0 && !isPrime(j)) {
            x[i] = j;
            u[j] = 1;
            if (i == n) inkq();
            else Try4(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 5: Sinh hoán vị có tổng các phần tử là số chẵn
void Try5(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0) {
            x[i] = j;
            u[j] = 1;
            if (i == n) {
                int sum = 0;
                for (int k = 1; k <= n; k++) sum += x[k];
                if (sum % 2 == 0) inkq();
            } else Try5(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 6: Sinh hoán vị có hai phần tử liên tiếp chênh lệch nhỏ nhất
void Try6(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0) {
            x[i] = j;
            u[j] = 1;
            if (i == n) {
                int minDiff = n;
                for (int k = 2; k <= n; k++) minDiff = min(minDiff, abs(x[k] - x[k - 1]));
                if (minDiff == 1) inkq();
            } else Try6(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 7: Sinh hoán vị không chứa cặp số liên tiếp chênh lệch lớn hơn 2
void Try7(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0) {
            x[i] = j;
            if (i > 1 && abs(x[i] - x[i - 1]) > 2) continue;
            u[j] = 1;
            if (i == n) inkq();
            else Try7(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 8: Sinh hoán vị đối xứng
void Try8(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0) {
            x[i] = j;
            u[j] = 1;
            if (i == n) {
                bool isSym = true;
                for (int k = 1; k <= n / 2; k++)
                    if (x[k] != x[n - k + 1]) isSym = false;
                if (isSym) inkq();
            } else Try8(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 9: Sinh hoán vị không chứa số lẻ ở vị trí chẵn
void Try9(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0 && !(i % 2 == 0 && j % 2 == 1)) {
            x[i] = j;
            u[j] = 1;
            if (i == n) inkq();
            else Try9(i + 1);
            u[j] = 0;
        }
    }
}

// Bài 10: Sinh hoán vị chứa số lớn nhất ở giữa
void Try10(int i) {
    for (int j = 1; j <= n; j++) {
        if (u[j] == 0) {
            x[i] = j;
            u[j] = 1;
            if (i == n) {
                int mid = (n + 1) / 2;
                if (x[mid] == n || (n % 2 == 0 && (x[mid] == n || x[mid + 1] == n))) inkq();
            } else Try10(i + 1);
            u[j] = 0;
        }
    }
}
Đỗ Thành