Câu lạc bộ Tin học dành cho học sinh Tiểu học

[sai mần gium pen 07 - Vũ Hoàng Quân 5/4]

Mục tiêu tiết 9: Hiểu và viết được các thuật toán cơ bản trong C++​

Thuật toán là gì?​

Thuật toán (Algorithm) là một dãy các bước cụ thể giúp bạn giải quyết một vấn đề.
Ví dụ: bạn muốn sắp xếp một danh sách số theo thứ tự tăng dần → cần có thuật toán sắp xếp.

---

Các loại thuật toán cơ bản bạn cần biết​

Nhóm	Ví dụ	Mục đích
Tìm kiếm (Searching)	Linear Search, Binary Search	Tìm phần tử trong mảng
Sắp xếp (Sorting)	Bubble Sort, Selection Sort, Quick Sort	Sắp xếp dữ liệu
Đệ quy (Recursion)	Tính giai thừa, Fibonacci	Giải bài toán bằng cách gọi lại chính nó
Thuật toán tham lam (Greedy)	Chọn đồng xu tối ưu	Tối ưu từng bước nhỏ nhất
Thuật toán đồ thị (Graph)	Dijkstra, BFS, DFS	Tìm đường đi hoặc kết nối trong mạng

---

Bắt đầu với ví dụ: Tìm kiếm nhị phân (Binary Search)​

Dùng khi mảng đã được sắp xếp tăng dần.
Thay vì duyệt từng phần tử, ta chia đôi liên tục để tìm nhanh hơn.

Code ví dụ:​

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == x)
            return mid; // tìm thấy
        else if (arr[mid] < x)
            left = mid + 1; // tìm bên phải
        else
            right = mid - 1; // tìm bên trái
    }
    return -1; // không tìm thấy
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 23;

    int result = binarySearch(arr, n, x);
    if (result != -1)
        cout << "Tìm thấy " << x << " tại vị trí " << result;
    else
        cout << "Không tìm thấy!";
}

Giải thích:

• Giả sử có 10 phần tử.
• Ở mỗi bước, bạn loại bỏ một nửa mảng.
• Thời gian tìm kiếm chỉ còn O(log n) thay vì O.

---

Thuật toán sắp xếp: Bubble Sort (nổi bọt)​

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Mảng sau khi sắp xếp: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

Độ phức tạp: O(n²)
Dễ hiểu, nhưng chậm với mảng lớn.

---

Thử thách nhỏ ​

Hãy tự viết thuật toán đệ quy tính giai thừa (n!)
Gợi ý:

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}