BÀI 3: THUẬT TOÁN TÌM KIẾM (SEARCHING)

Chuyên đề bồi dưỡng HSG - THPT Phan Chu Trinh, Gia Lai

1. Lý thuyết: Cuộc đua tốc độ

Tìm kiếm là thao tác cơ bản nhưng quyết định sự thành bại trong các kỳ thi. Khi dữ liệu đã được Sắp xếp, thay vì duyệt từng bước ($O(N)$), ta dùng Tìm kiếm nhị phân ($O(\log N)$).

Công thức: Với $10^6$ phần tử, tuyến tính cần $10^6$ bước, nhị phân chỉ cần khoảng 20 bước!

2. Thực hành: So sánh Tìm kiếm

🔬 PHÒNG THÍ NGHIỆM: TUYẾN TÍNH VS NHỊ PHÂN

Nhập số phần tử $N$ (giả sử $N = 1,000,000$):

3. Bài tập HSG: Tìm kiếm trên kết quả

Bài tập: Tìm giá trị nhỏ nhất thỏa mãn điều kiện

Phân tích: Thay vì tìm kiếm trên mảng, ta tìm kiếm trên phạm vi đáp án [low, high].

def binary_search_result(low, high):
    ans = high
    while low <= high:
        mid = (low + high) // 2
        if check(mid): # Điều kiện đề bài
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans

BÀI 2: THUẬT TOÁN SẮP XẾP (SORTING) - TỪ LÝ THUYẾT ĐẾN THỰC CHIẾN

Chuyên đề bồi dưỡng HSG Tin học - THPT Phan Chu Trinh

1. Lý thuyết cơ bản

Hiểu bài toán sắp xếp: Sắp xếp là quá trình đưa danh sách $N$ phần tử về thứ tự (tăng/giảm). Đây là bước "tiền xử lý" dữ liệu giúp biến các bài toán phức tạp $O(N^2)$ thành bài toán tối ưu $O(N \log N)$ hoặc $O(N)$.

Các lệnh cơ bản trong Python:

list.sort(): Sắp xếp tại chỗ (tối ưu bộ nhớ).
sorted(list): Trả về danh sách mới.
key=lambda x: ...: Định nghĩa tiêu chí sắp xếp tùy chỉnh.

Mô hình bài toán: [Dữ liệu thô] $\to$ [Sắp xếp ($O(N \log N)$)] $\to$ [Xử lý logic ($O(N)$)] $\to$ [Kết quả].

2. Ví dụ minh họa

Ví dụ: Sắp xếp đa tiêu chí

students = [("An", 8), ("Bình", 9), ("Chi", 8)]
# Dấu - trước x[1] giúp điểm cao lên trước, x[0] giúp tên xếp theo A-Z
students.sort(key=lambda x: (-x[1], x[0]))
print(students) # Kết quả: [('Bình', 9), ('An', 8), ('Chi', 8)]

3. Bài tập luyện tập (Đề thi HSG các Sở)

Bài tập 1: Cặp số có hiệu nhỏ nhất

Phân tích bài toán: Tìm $\min |A[i] - A[j]|$. Không được duyệt mọi cặp vì $O(N^2)$ sẽ quá thời gian.

Phân tích cấu trúc: Dùng list lưu dãy số.

Phân tích thuật toán: Sắp xếp dãy ($O(N \log N)$). Hiệu nhỏ nhất chắc chắn nằm giữa các cặp số kề nhau sau khi sắp xếp ($O(N)$).

Lời giải:

def find_min_diff(arr):
    arr.sort() # Sau khi sort: [2, 5, 8, 10, 14]
    min_val = float('inf')
    for i in range(len(arr) - 1):
        min_val = min(min_val, arr[i+1] - arr[i])
    return min_val
# Test: find_min_diff([10, 2, 14, 5, 8]) -> 2

Bài tập 2: Lựa chọn đoạn thẳng tối ưu

Phân tích bài toán: Chọn nhiều đoạn $[start, end]$ nhất không đè nhau.

Phân tích cấu trúc: Danh sách tuple (start, end).

Phân tích thuật toán: Thuật toán Tham lam. Sắp xếp theo end tăng dần. Chọn đoạn kết thúc sớm nhất để tối ưu khoảng không gian cho các đoạn tiếp theo.

Lời giải:

def max_segments(segments):
    segments.sort(key=lambda x: x[1]) # Sort theo thời điểm kết thúc
    count, last_end = 0, -float('inf')
    for start, end in segments:
        if start >= last_end: 
            count += 1
            last_end = end
    return count
# Test: [(1, 3), (2, 4), (3, 5)] -> Kết quả: 2

Bài tập 3: Phần tử xuất hiện nhiều nhất

Phân tích bài toán: Tìm giá trị có tần suất xuất hiện cao nhất.

Phân tích cấu trúc: List lưu trữ dãy số nguyên.

Phân tích thuật toán: Sắp xếp mảng để đưa các giá trị giống nhau về cùng một cụm. Duyệt qua mảng và đếm độ dài đoạn liên tiếp của mỗi cụm.

Lời giải:

def most_frequent(arr):
    arr.sort() # [1, 2, 2, 3, 3, 3]
    max_count, res = 0, arr[0]
    curr_count = 1
    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            curr_count += 1
        else:
            if curr_count > max_count:
                max_count, res = curr_count, arr[i-1]
            curr_count = 1
    return res if curr_count <= max_count else arr[-1]

4. Kỹ thuật nâng cao: "Vũ khí" trong phòng thi

Sử dụng `key` với hàm tùy chỉnh

Đôi khi tiêu chí sắp xếp không nằm ở giá trị mà nằm ở kết quả tính toán. Ví dụ: Sắp xếp danh sách số nguyên dựa trên tổng các chữ số của chúng.

def sum_digits(n):
    return sum(int(d) for d in str(abs(n)))

nums = [15, 23, 7, 42]
# Sắp xếp theo tổng chữ số tăng dần
nums.sort(key=sum_digits)
print(nums) # [7, 15, 23, 42] (Tổng: 7, 6, 5, 6 -> Sort: 5, 6, 6, 7)

5. Phân tích độ phức tạp (Tại sao chọn Sắp xếp?)

Hãy cùng so sánh "tốc độ" của thuật toán khi $N$ tăng lên:

Thuật toán	Độ phức tạp	$N = 10^3$	$N = 10^6$
Duyệt cặp ($O(N^2)$)	$O(N^2)$	$10^6$ (OK)	$10^{12}$ (TLE)
Sắp xếp ($O(N \log N)$)	$O(N \log N)$	$10^4$ (OK)	$2 \cdot 10^7$ (OK)

Kết luận: Với $N=10^6$, thuật toán $O(N^2)$ sẽ chạy mất hàng giờ, trong khi $O(N \log N)$ chỉ mất vài giây!

Bài tập 4: Xử lý số lớn (Big Number Sort)

Phân tích bài toán: Cho một danh sách các số cực lớn (dưới dạng chuỗi), hãy sắp xếp chúng theo giá trị tăng dần.

Thách thức: Nếu chuyển sang số nguyên, Python có thể xử lý được nhưng rất tốn bộ nhớ. Nếu sắp xếp theo kiểu chuỗi thông thường ("10" sẽ đứng trước "2"), kết quả sẽ sai.

Giải pháp: Sử dụng key kết hợp với `int` để so sánh giá trị thực tế.

def sort_big_numbers(str_list):
    # Dùng key=int để so sánh giá trị số thay vì so sánh ký tự ASCII
    str_list.sort(key=int)
    return str_list
# Test: ["100", "2", "30"] -> ["2", "30", "100"]

III. XÂU KÝ TỰ (STRING) - "XỬ LÝ VĂN BẢN"

Phần 3: Kỹ thuật xử lý chuỗi và chuẩn hóa dữ liệu - Đội tuyển HSG Phan Chu Trinh

Xâu ký tự thực chất là một "mảng của các ký tự". Tuy nhiên, trong Python, xâu ký tự có những phương thức xử lý cực mạnh giúp việc biến đổi văn bản trở nên đơn giản.

Ví dụ 3: Chuẩn hóa họ tên
Yêu cầu: Nhập vào một họ tên có thể chứa khoảng trắng thừa ở đầu, cuối hoặc giữa các từ. Hãy chuyển đổi về dạng chuẩn (Viết hoa chữ cái đầu mỗi từ, các từ cách nhau đúng 1 dấu cách).

1. Mã nguồn Python Full (Tham khảo)

def chuan_hoa_ho_ten(s):
    # Bước 1: Tách xâu thành danh sách các từ (loại bỏ khoảng trắng thừa)

    words = s.split()

    # Bước 2: Viết hoa chữ cái đầu mỗi từ (capitalize)

    cap_words = [w.capitalize() for w in words]

    # Bước 3: Nối lại thành xâu hoàn chỉnh bằng dấu cách

    result = ' '.join(cap_words)

    return result

# Sử dụng
name = "   nguYễn   vĂn   aN  "
print(f"Kết quả: '{chuan_hoa_ho_ten(name)}'")
# Output: "Nguyễn Văn An"

Lưu ý quan trọng:

Hàm split() không tham số sẽ tự động gom các khoảng trắng liên tiếp thành 1 dấu phân cách.
Xâu ký tự trong Python là Immutable (không thể thay đổi trực tiếp từng ký tự), nên ta thường chuyển sang List rồi mới Join lại.

✨ CÔNG CỤ CHUẨN HÓA TÊN TRỰC TUYẾN

Nhập họ tên cần chuẩn hóa:

4. Tư duy lập trình

Trong các kỳ thi HSG, xâu ký tự thường xuất hiện trong các bài toán về Tần suất (kết hợp với Dictionary) hoặc Xử lý số lớn (BigNum). Việc nắm vững split() và join() giúp bạn tiết kiệm 50% thời gian viết code so với các ngôn ngữ cũ như Pascal hay C++.

II. MẢNG (LIST) - "DÃY NGĂN KÉO CHỨA ĐỒ"

Phần 2: Quản lý và xử lý dữ liệu tập trung - Đội tuyển HSG Phan Chu Trinh

Mảng là cấu trúc dữ liệu quan trọng nhất giúp chúng ta lưu trữ hàng triệu giá trị chỉ với một tên biến duy nhất.

Ví dụ 2: Quản lý điểm số
Đề bài: Cho danh sách điểm của n học sinh. Tìm điểm cao nhất và đếm xem có bao nhiêu bạn đạt số điểm đó.

1. Mã nguồn Python tối ưu

# Cách 1: Sử dụng các hàm xây dựng sẵn (Built-in)
def thong_ke_diem(ds_diem):
    diem_max = max(ds_diem)
    so_luong = ds_diem.count(diem_max)
    return diem_max, so_luong

# Cách 2: Duyệt một vòng lặp (Tối ưu nhất cho dữ liệu lớn)
def tim_max_va_dem(ds_diem):
    m = -1
    c = 0
    for x in ds_diem:
        if x > m:
            m = x; c = 1
        elif x == m:
            c += 1
    return m, c

Phân tích thuật toán:

Kiến thức: Truy xuất A[i], hàm max(), count().
Tư duy: Gom nhóm dữ liệu. Thay vì xử lý rời rạc, ta xử lý trên một tập hợp thống nhất.
Độ phức tạp: $O(n)$. Với 1 triệu học sinh ($n=10^6$), Python chỉ mất khoảng 0.1s.

📊 MÔ PHỎNG QUẢN LÝ ĐIỂM HỌC SINH

Nhập số lượng học sinh bạn muốn giả lập (N):

Điểm cao nhất

Số bạn đạt được

Thời gian xử lý

3. Bài học về kỹ năng

Khi làm việc với mảng trong thi HSG Tin học, hãy luôn ưu tiên các hàm có sẵn của Python như sum(), max(), min(), sort() vì chúng được viết bằng ngôn ngữ C, giúp chương trình chạy nhanh hơn nhiều so với việc tự viết vòng lặp thủ công.

BÀI 1: ĐỘ PHỨC TẠP THUẬT TOÁN

Dành cho đội tuyển HSG Tin học - THPT Phan Chu Trinh

1. Khái niệm về "Thước đo sức mạnh" $O$

Trong lập trình thi đấu, không phải cứ ra kết quả đúng là có điểm. Bạn phải ra kết quả đúng trong thời gian cho phép (thường là 1 giây).

        Quy tắc vàng: Máy tính xử lý được khoảng 107 - 108 phép tính mỗi giây. Nếu thuật toán của bạn vượt quá con số này, bạn sẽ nhận lỗi TLE (Time Limit Exceeded).
    

2. Ví dụ: Tính tổng từ 1 đến $N$

Đề bài: Tính tổng $S = 1 + 2 + 3 + \dots + n$ với $n$ là số nguyên dương nhập từ bàn phím.
CÁCH 1: Duyệt tuần tự (Vòng lặp for - Duyệt vòng lặp $O(N)$) Mô tả: Giống như việc em đi bộ từ cổng trường vào lớp, bước đủ $n$ bước, mỗi bước cộng thêm 1 giá trị vào tổng.Mã nguồn Python:

        def sum_linear(n):

            s = 0

            for i in range(1, n + 1):

                s += i

          return s

=> Càng nhiều bước ($N$ lớn), máy càng tốn thời gian.

   Phân tích:  

              - Kiến thức:  Sử dụng biến tích lũy và vòng lặp cơ bản.

       -Tư duy: Tuyến tính (Linear). $n$ tăng gấp đôi thì máy phải làm việc gấp đôi.

       - Độ phức tạp: $O(n)$.).

CÁCH 2: Dùng công thức toán học (Gauss)

Mô tả: Thay vì đi bộ, em dùng "siêu năng lực" dịch chuyển tức thời. Chỉ cần một phép tính duy nhất là ra kết quả.:

       def sum_constant(n):

         return n * (n + 1) // 2

=> Dù $N$ lớn bao nhiêu, chỉ cần 1 bước tính là xong!

   Phân tích:  

              - Kiến thức: Áp dụng công thức tổng cấp số cộng: $$S = \frac{n(n+1)}{2}$$

       -Tư duy: TTối ưu (Constant). Không phụ thuộc vào độ lớn của $n$.

       - Độ phức tạp: $O(1)$

🔬 PHÒNG THÍ NGHIỆM THUẬT TOÁN

 import time 

def demo_complexity(n): 

    print(f"\n--- Thử nghiệm với n = {n:,} ---") 

    # Đo Cách 1: O(n) 

    start = time.time() 

    res1 = sum_linear(n) 

    end = time.time() 

     print(f"Cách 1 (Vòng lặp): Kết quả = {res1}, Thời gian = {end - start:.5f} giây") 

    # Đo Cách 2: O(1) 

    start = time.time() 

    res2 = sum_constant(n) 

    end = time.time() 

     print(f"Cách 2 (Toán học): Kết quả = {res2}, Thời gian = {end - start:.5f} giây") 

# Chạy thử nghiệm 

demo_complexity(10**7)  # 10 triệu 

demo_complexity(10**8)  # 100 triệu

Nhập số $N$ để so sánh tốc độ (Thử với $N = 10,000,000$):

Cách 2 - $O(1)$: ---

Cách 1 - $O(N)$: ---

3. Bài học rút ra

Tư duy tuần tự: Dễ nhưng chậm.
Tư duy tối ưu: Cần kiến thức nhưng cực nhanh.

TOÁN TIN ĐAM YI STUDY - DYS

BÀI 3: THUẬT TOÁN TÌM KIẾM (SEARCHING)

BÀI 3: THUẬT TOÁN TÌM KIẾM (SEARCHING)

1. Lý thuyết: Cuộc đua tốc độ

2. Thực hành: So sánh Tìm kiếm

🔬 PHÒNG THÍ NGHIỆM: TUYẾN TÍNH VS NHỊ PHÂN

3. Bài tập HSG: Tìm kiếm trên kết quả

Bài tập: Tìm giá trị nhỏ nhất thỏa mãn điều kiện

BÀI 2: THUẬT TOÁN SẮP XẾP (SORTING) - TỪ LÝ THUYẾT ĐẾN THỰC CHIẾN

BÀI 2: THUẬT TOÁN SẮP XẾP (SORTING) - TỪ LÝ THUYẾT ĐẾN THỰC CHIẾN

1. Lý thuyết cơ bản

2. Ví dụ minh họa

Ví dụ: Sắp xếp đa tiêu chí

3. Bài tập luyện tập (Đề thi HSG các Sở)

Bài tập 1: Cặp số có hiệu nhỏ nhất

Bài tập 2: Lựa chọn đoạn thẳng tối ưu

Bài tập 3: Phần tử xuất hiện nhiều nhất

4. Kỹ thuật nâng cao: "Vũ khí" trong phòng thi

Sử dụng `key` với hàm tùy chỉnh

5. Phân tích độ phức tạp (Tại sao chọn Sắp xếp?)

Bài tập 4: Xử lý số lớn (Big Number Sort)

III. XÂU KÝ TỰ (STRING) - "XỬ LÝ VĂN BẢN"

1. Mã nguồn Python Full (Tham khảo)

✨ CÔNG CỤ CHUẨN HÓA TÊN TRỰC TUYẾN

4. Tư duy lập trình

II. MẢNG (LIST) - "DÃY NGĂN KÉO CHỨA ĐỒ"

1. Mã nguồn Python tối ưu

📊 MÔ PHỎNG QUẢN LÝ ĐIỂM HỌC SINH

3. Bài học về kỹ năng

BÀI 1: ĐỘ PHỨC TẠP THUẬT TOÁN

1. Khái niệm về "Thước đo sức mạnh" $O$

2. Ví dụ: Tính tổng từ 1 đến $N$

CÁCH 2: Dùng công thức toán học (Gauss)

🔬 PHÒNG THÍ NGHIỆM THUẬT TOÁN

3. Bài học rút ra

DANH MỤC TIN HỌC

TRÌNH SOẠN THẢO TRỰC TUYẾN