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 10:​

• Hiểu 3 loại thuật toán nâng cao cực kỳ quan trọng:
  Thuật toán Tham lam (Greedy Algorithm)
  Lập trình động (Dynamic Programming - DP)
  Thuật toán Đồ thị (Graph Algorithms)

---

1. THUẬT TOÁN THAM LAM (Greedy Algorithm)​

Khái niệm:​

Thuật toán tham lam chọn phương án tốt nhất tại từng bước, hy vọng kết quả cuối cùng cũng là tốt nhất.

Ví dụ: Bài toán đổi tiền xu ​

Bạn có các loại tiền: 1, 2, 5, 10, 20
Cần đổi 63 đồng → dùng ít tờ nhất có thể.

Giải bằng C++:​

#include <iostream>
using namespace std;

void greedyCoins(int coins[], int n, int amount) {
    cout << "Các đồng xu được chọn: ";
    for (int i = n - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            cout << coins[i] << " ";
        }
    }
}

int main() {
    int coins[] = {1, 2, 5, 10, 20, 50};
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 63;
    greedyCoins(coins, n, amount);
}

Kết quả:
50 10 2 1 → tổng 63, chỉ dùng 4 tờ tiền.
Thuật toán này không phải lúc nào cũng tối ưu, nhưng rất nhanh.

---

2. LẬP TRÌNH ĐỘNG (Dynamic Programming - DP)​

Khái niệm:​

DP là kỹ thuật lưu lại kết quả trung gian để tránh tính toán lại.
Thường dùng cho bài toán tối ưu hoặc đệ quy lặp lại nhiều lần.

Ví dụ: Dãy Fibonacci​

Công thức:

F = F(n-1) + F(n-2), với F(0)=0, F(1)=1

Nếu dùng đệ quy thường, sẽ rất chậm
Ta dùng mảng lưu kết quả để tăng tốc.

#include <iostream>
using namespace std;

int fibonacciDP(int n) {
    int f[n+2];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
    return f[n];
}

int main() {
    int n = 10;
    cout << "F(" << n << ") = " << fibonacciDP(n);
}

Kết quả: F(10) = 55
Tốc độ nhanh gấp hàng trăm lần so với đệ quy thường.

---

3. THUẬT TOÁN ĐỒ THỊ (Graph Algorithm)​

Khái niệm:​

Đồ thị gồm các đỉnh (nodes) và cạnh (edges) — mô phỏng mạng xã hội, bản đồ, v.v.

Duyệt đồ thị: BFS & DFS​

DFS (Depth First Search)​

Đi sâu hết nhánh này trước khi quay lại.

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

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) dfs(neighbor, visited, graph);
    }
}

int main() {
    vector<vector<int>> graph = {
        {},        // 0 không dùng
        {2, 3},    // 1 -> 2,3
        {1, 4},    // 2 -> 1,4
        {1, 5},    // 3 -> 1,5
        {2},       // 4 -> 2
        {3}        // 5 -> 3
    };
    vector<bool> visited(6, false);
    cout << "Duyệt DFS từ đỉnh 1: ";
    dfs(1, visited, graph);
}

Kết quả: 1 2 4 3 5
DFS là nền tảng của nhiều thuật toán tìm đường và phát hiện chu trình.

---

Tổng kết tiết 10:​

Thuật toán	Đặc điểm	Ứng dụng
Greedy	Quyết định cục bộ tối ưu	Chọn tiền xu, sắp xếp công việc
DP	Lưu kết quả trung gian	Fibonacci, Knapsack, tối ưu hóa
Graph (DFS/BFS)	Duyệt và tìm đường	Mạng xã hội, bản đồ, AI

 

[Nguyễn Hoàng Gia Phú-5/10]

wao