Thuật toán sử dụng trong giải đề tin học trẻ

1. Prefix Sum — Tổng tiền tố
2. Binary Search — Tìm kiếm nhị phân
3. Two Pointers — Hai con trỏ
4. Đệ quy
5. Backtracking — Quay lui
6. Heap sort

1. Prefix Sum — Tổng tiền tố

Prefix Sum (tổng tiền tố) là một kỹ thuật rất quan trọng trong lập trình, đặc biệt khi cần tính tổng của nhiều đoạn liên tiếp trong một mảng.

Thay vì mỗi lần cần tính tổng lại cộng từng số, ta tính sẵn tổng từ đầu đến từng vị trí.

Ví dụ cơ bản

Cho dãy:

a = [2, 4, 1, 5, 3]

Ta tạo một dãy mới gọi là prefix:

prefix[0] = 2
prefix[1] = 2 + 4 = 6
prefix[2] = 2 + 4 + 1 = 7
prefix[3] = 2 + 4 + 1 + 5 = 12
prefix[4] = 2 + 4 + 1 + 5 + 3 = 15

Kết quả:

a        = [2, 4, 1, 5, 3]
prefix = [2, 6, 7, 12, 15]

Có thể hiểu:

prefix[i] = tổng các phần tử từ đầu dãy đến i

Ví dụ:

prefix[3] = 12

có nghĩa là:

2 + 4 + 1 + 5 = 12

Ví dụ code

#include <iostream>

using namespace std;



int main()

{

    int nums[] = {2, 4, 1, 5, 3};

    int prefix[5];

    prefix[0]= nums[0];

    for(int i=1;i<5;i++)

    {

        prefix[i]=prefix[i-1]+ nums[i];

    }

    cout << "prefix: " << endl    ;

    for(int i=0;i<5;i++)

    {

        cout << prefix[i] << " " ;

    }

    return 0;

}

2. Binary Search — Tìm kiếm nhị phân

Tìm kiếm nhị phân (Binary Search) là một thuật toán dùng để tìm một giá trị trong một dãy đã được sắp xếp.

Không tìm từng số một. Mỗi lần kiểm tra, ta bỏ đi một nửa dãy.

Đây là điểm quan trọng nhất cần nhớ.

Ví dụ đơn giản nhất

Có dãy số đã sắp xếp:

2   4   6   8   10   12   14   16   18

Ta cần tìm số: 14

Bước 1: Tìm số ở giữa
Có 9 số, số ở giữa là: 10
So sánh:  14 > 10

   Vậy số 14 không thể nằm bên trái 10.

Ta bỏ: 2   4   6   8   10

Chỉ còn: 12   14   16   18

Bước 2: Tìm số ở giữa
Giữa đoạn còn lại là khoảng: 14
Ta tìm thấy: 14 == 14

Kết luận:

Tìm thấy 14

Tại sao gọi là "nhị phân"?

"Nhị" nghĩa là hai.

Mỗi lần tìm kiếm, ta chia dãy thành 2 phần.

Ví dụ:

2  4  6  8  10  12  14  16  18
               ↑
             giữa

Nếu cần tìm 14:

Bên trái              Bên phải
2 4 6 8 10      |     12 14 16 18

Ta bỏ một bên.

Sau đó tiếp tục chia đôi:

12 14 16 18
     ↑
    giữa

Điều kiện quan trọng nhất

Dãy phải được sắp xếp

Ví dụ: 2 4 6 8 10 12 14

Có thể dùng Binary Search.

Nhưng: 8 2 14 4 10 6 12

thì không thể sử dụng Binary Search thông thường.

Tại sao? Vì khi thấy: 14 > số ở giữa

ta phải biết chắc rằng 14 nằm bên phải.

Điều này chỉ đúng khi dãy đã được sắp xếp.

4. Ba biến quan trọng

Khi lập trình Binary Search, thường sử dụng 3 biến:

left, right, mid

Trong đó:

left: vị trí đầu
right: vị trí cuối
mid: vị trí giữa

Ví dụ:

2   4   6   8   10   12   14
↑               ↑              ↑
left            mid           right

Ta tính:

mid = (left + right) / 2;

Ba trường hợp khi so sánh

Giả sử cần tìm: x = 14
và: a[mid] = 10

Có 3 trường hợp.

Trường hợp 1: Tìm thấy
a[mid] == x

Ví dụ:

10 == 10 → Tìm thấy.

Trường hợp 2: Số cần tìm lớn hơn số giữa

x > a[mid]

Ví dụ: 14 > 10

Vì dãy tăng dần nên số 14 phải nằm bên phải.

Ta bỏ nửa bên trái.

left = mid + 1;

Trường hợp 3: Số cần tìm nhỏ hơn số giữa

x < a[mid]

Ví dụ: 6 < 10

Số 6 phải nằm bên trái.
Ta bỏ nửa bên phải.

right = mid - 1;

Code C++ đơn giản

#include <iostream>

#include <vector>

using namespace std;



int main()

{

    vector<int> a = {2, 4, 6, 8, 10, 12, 14, 16, 18};



    int x = 14;



    int left = 0;

    int right = a.size() - 1;



    while (left <= right)

    {

        int mid = (left + right) / 2;



        if (a[mid] == x)

        {

            cout << "Tim thay";

            break;

        }

        else if (x > a[mid])

        {

            left = mid + 1;

        }

        else

        {

            right = mid - 1;

        }

    }



    return 0;

}

Giải thích từng bước code

Ban đầu:
int left = 0;
int right = a.size() - 1;

Dãy:
2   4   6   8   10   12   14   16   18
↑                   ↑                  ↑
0                  4                  8
left               mid               right

Ta có:

mid = (0 + 8) / 2;
mid = 4;

Do đó:

a[mid] = a[4] = 10

Ta cần tìm:
x = 14

So sánh:

14 > 10

Nên: left = mid + 1;
Tức:
left = 5;

Bây giờ chỉ còn:
12   14   16   18
↑         ↑         ↑
5         6         8
left      mid      right

Lại tính:
mid = (5 + 8) / 2;
Kết quả:
mid = 6

Ta có:

a[6] = 14

Và:

a[mid] == x

→ Tìm thấy.

3. Two Pointers — Hai con trỏ

4. Đệ quy

5. Backtracking — Quay lui

6. Thuật toán Heap sort trong C++

Heap Sort trong C++
Heap Sort (sắp xếp vun đống) là thuật toán sắp xếp dựa trên cấu trúc dữ liệu Heap.

Các bước cần nhớ trong thuật toán:

Biến mảng thành Max Heap.
Phần tử lớn nhất sẽ nằm ở vị trí đầu a[0].
Đổi a[0] với phần tử cuối.
Giảm kích thước Heap.
Vun lại Heap.
Lặp lại cho đến khi mảng được sắp xếp tăng dần.

Max Heap là gì?

Ví dụ:

        50
       /  \
     30    40
    / \    /
   10 20  35

Ta có:

50 > 30
50 > 40
30 > 10
30 > 20
40 > 35

Mỗi nút cha ≥ các nút con → đây mấu chốt của Max Heap.

Quan hệ giữa cha và con

Với mảng:

int a[] = {50, 30, 40, 10, 20, 35};

Nếu một phần tử ở vị trí i:

Con trái  = 2*i + 1
Con phải  = 2*i + 2
Cha       = (i-1)/2

Ví dụ i = 1:

Con trái = 2*1 + 1 = 3
Con phải = 2*1 + 2 = 4

Tức là:

       a[0]
       /    \
     a[1]   a[2]
     /  \
   a[3] a[4]

Bài tập, với a[2] thì con trái bao nhiêu, co phải bao nhiệu ?

     a[2]
     /  \
   a[2*2+1=5] a[2*2+2=6]

Hàm heapify

Đây là phần quan trọng nhất của Heap Sort.

void heapify(int a[], int n, int i)

{

    int lonNhat = i;



    int trai = 2 * i + 1;

    int phai = 2 * i + 2;



    if (trai < n && a[trai] > a[lonNhat])

        lonNhat = trai;



    if (phai < n && a[phai] > a[lonNhat])

        lonNhat = phai;



    if (lonNhat != i)

    {

        swap(a[i], a[lonNhat]);



        heapify(a, n, lonNhat);

    }

}

Ý nghĩa:

Giả sử:

        10
       /  \
     50    30

10 không phải lớn nhất.

So sánh:

10
50  ← lớn nhất
30

Đổi:

        50
       /  \
     10    30

Sau đó tiếp tục heapify ở vị trí mới của 10.

Code Heap Sort hoàn chỉnh

#include <iostream>

using namespace std;



void heapify(int a[], int n, int i)

{

    int lonNhat = i;



    int trai = 2 * i + 1;

    int phai = 2 * i + 2;



    // Tìm phần tử lớn nhất

    if (trai < n && a[trai] > a[lonNhat])

        lonNhat = trai;



    if (phai < n && a[phai] > a[lonNhat])

        lonNhat = phai;



    // Nếu cha không phải lớn nhất

    if (lonNhat != i)

    {

        swap(a[i], a[lonNhat]);



        // Vun lại Heap

        heapify(a, n, lonNhat);

    }

}



void heapSort(int a[], int n)

{

    // Bước 1: Tạo Max Heap

    for (int i = n / 2 - 1; i >= 0; i--)

    {

        heapify(a, n, i);

    }



    // Bước 2: Lấy phần tử lớn nhất

    // đưa về cuối mảng

    for (int i = n - 1; i > 0; i--)

    {

        swap(a[0], a[i]);



        // Heap chỉ còn i phần tử

        heapify(a, i, 0);

    }

}



int main()

{

    int a[] = {10, 5, 20, 8, 15, 30, 2};



    int n = 7;



    heapSort(a, n);



    for (int i = 0; i < n; i++)

    {

        cout << a[i] << " ";

    }



    return 0;

}

Sơ đồ của Heap Sort

Heap Sort = Tạo Max Heap → lấy số lớn nhất → đưa về cuối → Heapify lại → lặp lại.
 

Tìm kiếm: