Hệ thống kiến thức C++

C++ là một ngôn ngữ lập trình mạnh mẽ và linh hoạt, được sử dụng rộng rãi trong phát triển phần mềm hệ thống, game, ứng dụng hiệu năng cao và nhiều lĩnh vực khác. Để nắm vững C++, việc xây dựng một hệ thống kiến thức bài bản là vô cùng quan trọng. Bài viết này sẽ phác thảo một lộ trình học tập toàn diện, bao gồm các khía cạnh từ cơ bản đến nâng cao.

I. Cú pháp cơ bản

Phần này tập trung vào những viên gạch đầu tiên để xây dựng chương trình C++:

1. Cấu trúc chương trình

Cấu trúc tuần tự: Thực hiện các phép toán số học và logic theo thứ tự.
Cấu trúc rẽ nhánh: Thực hiện các quyết định logic.
Cấu trúc lặp: Lặp lại các phép toán số học, logic hoặc quyết định, với khả năng tính toán số lần lặp rõ ràng.

2. Cấu trúc tuần tự

Kiểu dữ liệu: int, long long, char, double, short, float, unsigned.
Toán tử (Biểu thức): Số học, logic, quan hệ, tăng/giảm, bitwise, ba ngôi, dấu phẩy.
Ưu tiên toán tử và chuyển đổi kiểu dữ liệu.
Biến và hằng số: Hằng số ký tự và hằng số có tên.

3. Cấu trúc rẽ nhánh

Một nhánh, hai nhánh, nhiều nhánh.
if, if-else, switch-case.
Lồng nhau và nối tiếp if.

4. Cấu trúc lặp

while, for, do-while.
Sử dụng for khi biết số lần lặp, while khi không biết.
Lồng nhau, break, continue, goto.


// Ví dụ sử dụng goto để nhảy đến nhãn lab
for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= i; j++) {
        cout << j << " ";
        if (j == 3) {
            goto lab; // Nhảy đến vị trí của nhãn lab để tiếp tục thực thi tuần tự
        }
    }
}
lab:
cout << "OK";


// Sử dụng goto để thực hiện vòng lặp đơn
int i = 1;
loop:
    cout << i << " "; // Thân vòng lặp
    if (i == 10) goto End;
    i++; // Tăng biến điều khiển vòng lặp
    goto loop;
End: // Kết thúc vòng lặp

II. Cú pháp nâng cao

1. Cấu trúc dữ liệu

Mảng: Biểu diễn dưới dạng danh sách tuyến tính có cấu trúc tuần tự, còn gọi là bảng tuần tự.
Chuỗi: Chuỗi kiểu C (mảng char) và chuỗi kiểu C++ (lớp string).
Struct: Thường được gọi là class trong C++, dùng để lưu trữ dữ liệu thuộc các kiểu khác nhau hoặc triển khai danh sách liên kết động.

Union: Tiết kiệm không gian lưu trữ.


union Node {
    int x;
    double y;
} a;
// Tại một thời điểm, a chỉ có thể mang một trong các kiểu thành viên xác định.
// sizeof(a) = kích thước của thành viên chiếm dung lượng lớn nhất.

Enum: Giới hạn các giá trị mà biến có thể lưu trữ.


enum Gender { MALE, FEMALE, UNKNOWN }; // Gán mặc định là 0, 1, 2
enum Gender { MALE = 7, FEMALE = 12, UNKNOWN }; // UNKNOWN được gán giá trị 13
Gender a = MALE;

2. Lớp và Lập trình hướng đối tượng

3. Xử lý ngoại lệ

III. Thuật toán cơ bản

1. Đệ quy

Là phương pháp phân tích từ trên xuống, tinh chỉnh dần dần, là một biến thể của phương pháp chia để trị (phương pháp giảm thiểu).

Dãy Fibonacci.
Tháp Hà Nội.
Xuất hoán vị, tổ hợp.
Tìm kiếm và quay lui (backtracking).
Phân tích số.
Thuật toán chia để trị:
- Định nghĩa: Là phương pháp chia bài toán phức tạp thành các bài toán con có quy mô nhỏ hơn nhưng cấu trúc tương tự, sau đó giải đệ quy các bài toán con, cuối cùng hợp nhất kết quả của các bài toán con thành lời giải cho bài toán ban đầu. Thuật toán chia để trị đặc biệt phù hợp với các bài toán có tính chất đệ quy:
  1. Bài toán gốc có thể phân rã thành các bài toán con giống hệt có quy mô nhỏ hơn.
  2. Lời giải của bài toán con có thể hợp nhất thành lời giải của bài toán gốc.
  3. Các bài toán con độc lập với nhau (không có sự chồng chéo).
- Tổng quan: Thuật toán chia để trị giải quyết bài toán qua ba bước: "chia", "giải", "hợp".
  - Phân chia (Divide): Chia bài toán gốc thành nhiều bài toán con.
  - Giải quyết (Conquer): Giải đệ quy các bài toán con này, khi quy mô đủ nhỏ thì giải trực tiếp.
  - Hợp nhất (Combine): Hợp nhất lời giải của các bài toán con thành lời giải của bài toán gốc.
- Ý tưởng thuật toán: Chia bài toán gốc thành các bài toán con, giải đệ quy rồi hợp nhất. Cụ thể:
  1. Phân chia: Chia bài toán lớn thành nhiều bài toán nhỏ hơn, thường có quy mô tương tự. Các bài toán con có thể giải độc lập và là phiên bản đơn giản hóa của bài toán gốc.
  2. Giải quyết: Giải đệ quy các bài toán con. Nếu quy mô đủ nhỏ, giải trực tiếp.
  3. Hợp nhất: Kết hợp lời giải của các bài toán con thành lời giải cuối cùng.
- Triển khai mã: Dưới đây là ví dụ mã C++ triển khai thuật toán sắp xếp trộn (Merge Sort) bằng ý tưởng chia để trị:
```
        
        #include<bits/stdc++.h>
        using namespace std;
        void merge(int arr[],int left,int mid,int right) {
            int n1=mid-left+1;
            int n2=right-mid;
            int leftArr[1000],rightArr[1000];
            for(int i=0; i<n1; i++) {
                leftArr[i]=arr[left+i];
            }
            for(int i=0; i<n2; i++) {
                rightArr[i]=arr[mid+1+i];
            }
            int i=0,j=0,k=left;
            while(i<n1&&j<n2) {
                if(leftArr[i]<=rightArr[j]) { // Hợp và sắp xếp
                    arr[k++]=leftArr[i++];
                } else {
                    arr[k++]=rightArr[j++];
                }
            }
            while(i<n1) {
                arr[k++]=leftArr[i++];
            }
            while(j<n2) {
                arr[k++]=rightArr[j++];
            }
        }
        void mergeSort(int arr[],int left,int right) {
            if(left>=right) {
                return;
            }
            int mid=left+(right-left)/2;
            mergeSort(arr,left,mid);
            mergeSort(arr,mid+1,right);
            merge(arr,left,mid,right);
        }
        int main() {
            int arr[10]= {3,5,1,6,2,9,8};
            int n=7;
            cout<<"Original:"<<endl;
            for(int i=0; i<n; i++) {
                cout<<arr[i]<<endl;
            }
            mergeSort(arr,0,n-1);
            cout<<"Sorted:"<<endl;
            for(int i=0; i<n; i++) {
                cout<<arr[i]<<" ";
            }
            cout<<endl;
            return 0;
        }
        
        
```
  Giải thích mã:
  - mergeSort: Hàm đệ quy, chia mảng thành hai phần, sắp xếp rồi hợp nhất.
  - merge: Hợp nhất hai mảng con đã sắp xếp thành một mảng con đã sắp xếp.
  - main: Hàm chính, gọi mergeSort để sắp xếp mảng.
- Ví dụ:
  Khi hợp nhất hai mảng con đã sắp xếp leftArr = [1, 5] và rightArr = [2, 6]:
  1. Khởi tạo con trỏ: i = 0, j = 0, k = 0.
  2. So sánh leftArr[0] (1) và rightArr[0] (2). Vì 1 <= 2, sao chép 1 vào mảng kết quả, tăng i và k. Mảng kết quả: [1].
  3. So sánh leftArr[1] (5) và rightArr[0] (2). Vì 5 > 2, sao chép 2 vào mảng kết quả, tăng j và k. Mảng kết quả: [1, 2].
  4. So sánh leftArr[1] (5) và rightArr[1] (6). Vì 5 <= 6, sao chép 5 vào mảng kết quả, tăng i và k. Mảng kết quả: [1, 2, 5].
  5. Mảng leftArr đã hết. Sao chép phần còn lại của rightArr (là 6) vào mảng kết quả. Mảng kết quả: [1, 2, 5, 6].
- Lưu ý:
  - Chi phí đệ quy: Có thể gây tiêu tốn không gian ngăn xếp lớn. Cân nhắc tối ưu hóa đệ quy đuôi hoặc chuyển đổi sang phiên bản không đệ quy.
  - Lựa chọn chiến lược phân chia: Dựa trên đặc điểm bài toán. Ví dụ, Quick Sort chọn phần tử chốt để phân chia, Merge Sort chia đôi mảng.
  - Hiệu quả hợp nhất: Bước hợp nhất ảnh hưởng trực tiếp đến hiệu suất tổng thể.
  - Độ phức tạp không gian: Thường yêu cầu không gian bổ sung để lưu trữ lời giải bài toán con.
  - Trường hợp áp dụng: Các bài toán có thể phân rã thành các bài toán con độc lập (sắp xếp, tìm kiếm, xử lý ảnh, phép toán ma trận).

2. Truy hồi (Recursion)

Là phương pháp phân tích từ dưới lên, tích hợp dần dần.

Dãy Fibonacci.
Tìm kiếm và quay lui (backtracking).
Phân tích số: Số cách phân tích số nguyên dương n thành tổng của k số nguyên dương.
- P(n, k) = P(n-1, k-1) + P(n-k, k).
- P(n, k) = 0 khi n < k.
Tổng tiền tố: Tính tổng các đoạn tĩnh trong một dãy (dãy không thay đổi).
Tổng tiền tố cho phép tính tổng các đoạn trong O(1) sau khi thực hiện tiền xử lý O(n).
```
    
    // Tiền xử lý tổng tiền tố 1D
    int sum[10005], a[10005]; // sum[i] = a[1] + ... + a[i]
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }

    // Truy vấn tổng đoạn [l, r]
    scanf("%d%d",&l,&r);
    printf("%d\n", sum[r] - sum[l - 1]); // Độ phức tạp O(1)
    
    
```
Tổng tiền tố 2D: Áp dụng tương tự cho ma trận hai chiều. Công thức tính tổng cho một hình chữ nhật con có góc trên bên trái là (x1, y1) và góc dưới bên phải là (x2, y2): Sum(x1, y1, x2, y2) = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1] trong đó S[i][j] là tổng tiền tố từ (1, 1) đến (i, j).
Sai phân: Dùng để sửa đổi đoạn, sau đó tính tổng tiền tố để khôi phục lại mảng ban đầu.
Với mảng a, mảng sai phân b được định nghĩa sao cho a[i] = b[1] + ... + b[i]. Để cộng c vào đoạn [l, r] của a, ta chỉ cần thực hiện b[l] += c và b[r+1] -= c. Việc này giúp tối ưu hóa thao tác sửa đổi đoạn từ O(n) xuống O(1).

Sai phân 2D: Tương tự, áp dụng cho ma trận hai chiều để thực hiện các thao tác cộng giá trị vào một hình chữ nhật con trong O(1).
Tiền tố/Hậu tố cực trị: Tạo một dãy có thứ tự dựa trên dãy gốc.

3. Sắp xếp

Sắp xếp nổi bọt: Hoán đổi hai phần tử liền kề để loại bỏ các cặp nghịch đảo.
Sắp xếp chọn: Lặp lại việc chọn phần tử nhỏ nhất và đặt vào vị trí đúng.
Sắp xếp chèn: Chèn phần tử đang xét vào đúng vị trí trong phần đã sắp xếp.
Sắp xếp đếm: (Sẽ đề cập chi tiết hơn trong các phần sau).

4. Nhị phân

Tại sao sử dụng tìm kiếm nhị phân: Để tìm kiếm hiệu quả trong mảng đã sắp xếp với độ phức tạp O(log n), thay vì duyệt tuần tự O(n).
Ưu điểm: Tốc độ tìm kiếm nhanh.
Nhược điểm: Yêu cầu dữ liệu phải có thứ tự, khó khăn trong việc chèn và xóa.
Các cách viết tìm kiếm nhị phân:
- Tìm kiếm mục tiêu về phía bên trái (while(l < r)).
- Tìm kiếm mục tiêu về phía bên phải (while(l <= r)).
- lower_bound: Tìm phần tử đầu tiên lớn hơn hoặc bằng giá trị cho trước.
- upper_bound: Tìm phần tử đầu tiên lớn hơn giá trị cho trước.
Nhị phân trên đáp án: Khi đáp án có tính đơn điệu và nằm trong một khoảng lớn, có thể dùng nhị phân để tìm kiếm đáp án tối ưu.
Phân biệt tìm kiếm nhị phân và nhị phân trên đáp án: Tìm kiếm nhị phân tìm trong tập dữ liệu có thứ tự, còn nhị phân trên đáp án tìm trong khoảng giá trị của đáp án.
Khi nào sử dụng nhị phân trên đáp án: Khi đáp án nằm trong một khoảng lớn, khó tìm trực tiếp nhưng dễ kiểm tra tính khả thi, và có tính đơn điệu.
Ví dụ bài toán: Chia mảng thành M đoạn sao cho giá trị lớn nhất của tổng các đoạn là nhỏ nhất.

IV. Tham lam

Lựa chọn giải pháp tốt nhất tại mỗi bước cục bộ, với hy vọng đạt được giải pháp tối ưu toàn cục.

Bài toán chất xếp tối ưu: Ưu tiên chọn các vật có trọng lượng nhỏ nhất để tối đa hóa số lượng vật có thể xếp lên thuyền có sức chứa giới hạn.
Bài toán cái túi phân số: Ưu tiên chọn các vật có tỷ lệ giá trị/trọng lượng cao nhất. Cho phép chia nhỏ vật phẩm.
Bài toán chọn điểm không giao nhau: Sắp xếp các khoảng theo điểm cuối và chọn điểm cuối của khoảng đó làm điểm đại diện nếu nó không bị phủ bởi điểm đã chọn trước đó.

V. Quy hoạch động

Giải quyết bài toán bằng cách chia thành các bài toán con nhỏ hơn và lưu trữ kết quả để tái sử dụng.

Bài toán cơ bản: Dãy Fibonacci, Tam giác Pascal, Kim tự tháp số.

Bài toán cái túi 0/1: Chọn vật phẩm để tối đa hóa giá trị trong giới hạn trọng lượng, mỗi vật phẩm chỉ chọn một lần.

    
    // Cài đặt quy hoạch động cho bài toán cái túi 0/1
    int knapsack(int capacity, vector<int>& weights, vector<int>& values, int n) {
        vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= capacity; ++j) {
                if (weights[i-1] > j) { // Nếu không đủ chỗ chứa
                    dp[i][j] = dp[i-1][j];
                } else { // Có thể chọn hoặc không chọn
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]);
                }
            }
        }
        return dp[n][capacity];
    }

    
    // Tối ưu không gian với mảng 1D
    int knapsack_optimized(int capacity, vector<int>& weights, vector<int>& values, int n) {
        vector<int> dp(capacity + 1, 0);

        for (int i = 0; i < n; ++i) {
            for (int j = capacity; j >= weights[i]; --j) { // Duyệt ngược để tránh dùng lại vật phẩm
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }

Bài toán cái túi không giới hạn: Mỗi vật phẩm có thể chọn nhiều lần.
Bài toán cái túi nhiều lần: Mỗi vật phẩm có số lượng giới hạn. Có thể tối ưu bằng cách phân rã nhị phân số lượng.
Bài toán cái túi hỗn hợp: Kết hợp các loại bài toán cái túi 0/1, không giới hạn và nhiều lần.
Phân tích số.

VI. Tìm kiếm (Flood Fill)

DFS (Depth-First Search): Duyệt theo chiều sâu, thường sử dụng đệ quy.
BFS (Breadth-First Search): Duyệt theo chiều rộng, thường sử dụng hàng đợi.
Kỹ thuật cắt tỉa (Pruning) trong DFS: Giúp loại bỏ các nhánh tìm kiếm không khả thi hoặc không mang lại kết quả tốt hơn.

VII. Cấu trúc dữ liệu nâng cao

Danh sách tuyến tính:
- Danh sách tuyến tính bị giới hạn: Hàng đợi vòng, Stack và Queue.
- Stack (Ngăn xếp): Nguyên tắc LIFO (Last-In, First-Out). Thường dùng cho quản lý hàm gọi, đánh giá biểu thức.
- Queue (Hàng đợi): Nguyên tắc FIFO (First-In, First-Out). Thường dùng cho lập lịch tác vụ, BFS.
- Hàng đợi đơn điệu và Ngăn xếp đơn điệu: Dùng để duy trì tính đơn điệu của dữ liệu trong các bài toán như cửa sổ trượt.
Danh sách liên kết: Đơn, đôi, vòng.
Cây nhị phân: Cấu trúc dữ liệu phân cấp với tối đa hai con.
Lưu trữ và duyệt đồ thị: Ma trận kề, danh sách kề.
Sắp xếp tô pô.

VIII. Kiến thức bổ sung

Toán tử Bitwise: ~, &, |, ^, <<, >>.
Mảng và chuỗi: Khởi tạo, truy cập, các hàm xử lý chuỗi C-style và std::string.
Mã hóa dữ liệu: Mã gốc, mã bù 1, mã bù 2.
Chuyển đổi hệ cơ số.
Thuật toán: Mô tả bằng ngôn ngữ tự nhiên, lưu đồ, mã giả. Phương pháp liệt kê (brute-force), mô phỏng.
Kiến thức rời rạc: Mạng máy tính, hệ điều hành, ngôn ngữ lập trình, công cụ phát triển, các nhà khoa học máy tính tiêu biểu.
Con trỏ: Biến lưu trữ địa chỉ bộ nhớ.
Struct: Cấu trúc dữ liệu tùy chỉnh.
Hàm và phạm vi: Khai báo, định nghĩa, truyền tham số (theo giá trị, theo tham chiếu, theo con trỏ). Biến toàn cục và cục bộ.
Thuật toán truy hồi: Tính toán từng bước dựa trên điều kiện đã biết.
Độ phức tạp thuật toán: O(n^2), O(n log n), O(2^n).
Thao tác tệp: Đọc, ghi tệp.
Xử lý ngoại lệ: Khối try-catch.

IX. Chuyên đề Toán học

Sàng nguyên tố: Thuật toán sàng Eratosthenes, sàng Euler.
Hàm Euler: φ(n) - số các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n.
Tổ hợp: Hoán vị, chỉnh hợp, tổ hợp.
Định lý phân tích duy nhất: Mọi số nguyên lớn hơn 1 đều có thể phân tích duy nhất thành tích các số nguyên tố.
Toán học THPT: Đại số, hình học, số học, xác suất thống kê.
Toán học tổng hợp.

Thẻ: C++ cú pháp thuật toán Cấu trúc dữ liệu quy hoạch động

Đăng vào ngày 20 tháng 5 lúc 11:25

Thành phố Cuồng loạn