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

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

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

Tìm kiếm: