Những bài tập áp dụng đệ quy thường gặp trong C++

MayFest2024

Những bài tập áp dụng đệ quy có thể nói là KINH ĐIỂN, mà bất kỳ sinh viên CNTT nào cũng từng gặp phải 👨‍💻

Có thể đệ quy chưa phải giải pháp tối ưu nhất để xử lý các bài tập này, nhưng để hướng dẫn cho những bạn mới bắt đầu thì có lẽ đệ quy là dễ đọc, dễ hiểu bậc nhất ✅

1. Tháp Hà Nội

#include <iostream>

using namespace std;

void towerOfHanoi(int n, char source, char destination, char auxiliary)
{
    if (n == 1)
    {
        cout << "Chuyển đĩa 1 từ cột " << source << " sang cột " << destination << endl;
        return;
    }
    
    towerOfHanoi(n - 1, source, auxiliary, destination);
    cout << "Chuyển đĩa " << n << " từ cột " << source << " sang cột " << destination << endl;
    towerOfHanoi(n - 1, auxiliary, destination, source);
}

int main()
{
    int n;
    cout << "Nhập số đĩa: ";
    cin >> n;

    towerOfHanoi(n, 'A', 'C', 'B');

    return 0;
}

2. Bài toán xếp N quân hậu

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

// Mảng đánh dấu các cột, đường chéo chính và đường chéo phụ
bool columns[13], mainDiagonals[26], antiDiagonals[26];

// Tọa độ các quân hậu trên bàn cờ
vector<int> queenRows, queenColumns;

// Tổng số cách xếp
int numberOfSolutions = 0;

// Hàm in kết quả dưới dạng (row, col)
void printSolution(int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << "(" << queenRows[i] << ", " << queenColumns[i] << ")";
        if (i < n - 1)
        {
            cout << ", ";
        }
    }
    cout << endl;
}

// Hàm đệ quy để tìm các cách đặt quân hậu
void solveNQueens(int n, int currentRow)
{
    for (int currentColumn = 1; currentColumn <= n; currentColumn++)
    {
        // Tính chỉ số của đường chéo chính và đường chéo phụ hiện tại
        int currentMainDiagonal = currentRow + currentColumn;
        int currentAntiDiagonal = currentRow - currentColumn + 13; // +13 để tránh chỉ số âm

        // Kiểm tra vị trí đang xét có an toàn không?
        if (columns[currentColumn] || mainDiagonals[currentMainDiagonal] || antiDiagonals[currentAntiDiagonal])
        {
            continue;
        }

        // Đánh dấu vị trí quân hậu
        queenRows.push_back(currentRow);
        queenColumns.push_back(currentColumn);
        columns[currentColumn] = true;
        mainDiagonals[currentMainDiagonal] = true;
        antiDiagonals[currentAntiDiagonal] = true;

        // Nếu đã đặt đủ N quân hậu, in ra kết quả
        if (queenRows.size() == n)
        {
            numberOfSolutions++;
            printSolution(n);
        }
        else
        {
            // Đệ quy để đặt quân hậu tiếp theo
            solveNQueens(n, currentRow + 1);
        }

        // Quay lui: Bỏ đánh dấu vị trí quân hậu vừa thêm vào
        queenRows.pop_back();
        queenColumns.pop_back();
        columns[currentColumn] = false;
        mainDiagonals[currentMainDiagonal] = false;
        antiDiagonals[currentAntiDiagonal] = false;
    }
}

int main()
{
    cout << "ĐỀ BÀI: TÌM TẤT CẢ CÁC CÁCH XẾP N (N <= 12) QUÂN HẬU LÊN MỘT BÀN CỜ N X N, SAO CHO KHÔNG CÓ 2 QUÂN HẬU NÀO CÓ THỂ ĂN ĐƯỢC NHAU." << endl;
    cout << "------------------------------" << endl;

    int n;
    cout << "Nhập số lượng quân hậu muốn xếp: ";
    cin >> n;
    cout << "------------------------------" << endl;

    memset(columns, 0, sizeof(columns));
    memset(mainDiagonals, 0, sizeof(mainDiagonals));
    memset(antiDiagonals, 0, sizeof(antiDiagonals));

    cout << "Mỗi cách xếp sẽ nằm trên 1 dòng tương ứng dưới đây: " << endl;
    int currentRow = 1;
    solveNQueens(n, currentRow);

    cout << "------------------------------" << endl;
    cout << "TỔNG SỐ CÁCH XẾP LÀ: " << numberOfSolutions << endl;

    return 0;
}

3. Tìm kiếm nhị phân

#include <iostream>

using namespace std;

#define NOT_FOUND -1

int binarySearch(int arr[], int left, int right, int target)
{
    if (right >= left)
    {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
        {
            return mid;
        }

        if (arr[mid] > target)
        {
            return binarySearch(arr, left, mid - 1, target);
        }

        return binarySearch(arr, mid + 1, right, target);
    }

    return NOT_FOUND;
}

int main()
{
    int n;
    cout << "Nhập số phần tử của mảng: ";
    cin >> n;

    int arr[n];
    cout << "Nhập các phần tử của mảng (đã sắp xếp tăng dần): " << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    int target;
    cout << "Nhập số cần tìm: ";
    cin >> target;

    int result = binarySearch(arr, 0, n = 1, target);

    if (result != NOT_FOUND)
    {
        cout << "Số " << target << " được tìm thấy ở vị trí thứ " << result << endl;
    }
    else
    {
        cout << "Không tìm thấy số " << target << " trong mảng." << endl;
    }

    return 0;
}

4. Ước chung lớn nhất của 2 số

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a % b);
    }
}

int main()
{
    int a, b;
    cout << "Nhập hai số nguyên dương: ";
    cin >> a >> b;

    cout << "Ước chung lớn nhất của " << a << " và " << b << " là: " << gcd(a, b) << endl;

    return 0;
}

5. Tổng các chữ số của 1 số nguyên

#include <iostream>

using namespace std;

int sumOfDigits(int number)
{
    if (number == 0)
    {
        return 0;
    }
    else
    {
        return (number % 10) + sumOfDigits(number / 10);
    }
}

int main()
{
    int n;
    cout << "Nhập số nguyên dương n: ";
    cin >> n;

    cout << "Tổng các chữ số của " << n << " là: " << sumOfDigits(n) << endl;

    return 0;
}

6. Chuyển số nguyên sang dạng nhị phân

#include <iostream>

using namespace std;

void decimalToBinary(int n)
{
    if (n != 0)
    {
        decimalToBinary(n / 2);
        cout << (n % 2);
    }
}

int main()
{
    int n;
    cout << "Nhập số nguyên không âm n: ";
    cin >> n;

    cout << "Số nhị phân tương ứng là: ";
    if (n == 0)
    {
        cout << "0";
    }
    else
    {
        decimalToBinary(n);
    }
    cout << endl;

    return 0;
}

7. Chuyển số nguyên sang dạng hex

#include <iostream>

using namespace std;

void decimalToHex(int n)
{
    string hexCharacters = "0123456789ABCDEF";

    if (n != 0)
    {
        decimalToHex(n / 16);
        int remainder = n % 16;
        cout << hexCharacters[remainder];
    }
}

int main()
{
    int n;
    cout << "Nhập số nguyên không âm n: ";
    cin >> n;

    cout << "Số hex tương ứng là: ";
    if (n == 0)
    {
        cout << "0";
    }
    else
    {
        decimalToHex(n);
    }
    cout << endl;

    return 0;
}

8. Tính số Fibonacci thứ n

#include <iostream>

using namespace std;

int fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main()
{
    int n;
    cout << "Nhập số nguyên dương n: ";
    cin >> n;

    cout << "Số Fibonacci thứ " << n << " là: " << fibonacci(n) << endl;

    return 0;
}

9. Tính giai thừa

#include <iostream>

using namespace std;

int factorial(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        return n * factorial(n - 1);
    }
}

int main()
{
    int n;
    cout << "Nhập số nguyên dương n: ";
    cin >> n;

    cout << "Giai thừa của " << n << " là: " << factorial(n) << endl;

    return 0;
}