Khóa học Python từ Cơ bản đến Nâng cao

Bài 7.5 - Tìm Số Cặp Có Hiệu Chẵn Trong Python

Chào mừng quay trở lại với chuỗi bài tập Python! Trong bài này, chúng ta sẽ cùng nhau giải quyết một bài toán khá thú vị liên quan đến tính chất của các con số: đếm số cặp phần tử trong một danh sách sao cho hiệu của hai phần tử trong cặp đó là một số chẵn.

Nghe có vẻ đơn giản, nhưng hãy cùng phân tích sâu hơn và khám phá những cách tiếp cận khác nhau nhé!

Phân Tích Bài Toán: Hiệu Chẵn Là Sao?

Khi nào thì hiệu của hai số nguyên là một số chẵn? Hãy nhớ lại một chút về tính chẵn lẻ của các phép toán cơ bản:

• Số chẵn - Số chẵn = Số chẵn (Ví dụ: 8 - 2 = 6)
• Số lẻ - Số lẻ = Số chẵn (Ví dụ: 7 - 3 = 4)
• Số chẵn - Số lẻ = Số lẻ (Ví dụ: 6 - 3 = 3)
• Số lẻ - Số chẵn = Số lẻ (Ví dụ: 7 - 2 = 5)

Từ đó, chúng ta có thể thấy một quy luật quan trọng: Hiệu của hai số nguyên là số chẵn khi và chỉ khi hai số đó có cùng tính chẵn lẻ.

Nói cách khác, chúng ta cần đếm số lượng các cặp (a, b) trong danh sách sao cho a và b đều là số chẵn, HOẶC a và b đều là số lẻ.

Bây giờ, với hiểu biết này, chúng ta có thể bắt tay vào xây dựng giải thuật.

Cách Tiếp Cận 1: "Thô Bạo" - Duyệt Qua Tất Cả Các Cặp

Cách đơn giản và trực quan nhất là kiểm tra tất cả các cặp có thể có trong danh sách. Với một danh sách có n phần tử, chúng ta có thể sử dụng hai vòng lặp lồng nhau để xét mọi cặp (danh_sach[i], danh_sach[j]) với i và j khác nhau.

Chúng ta cần cẩn thận để không đếm một cặp hai lần (ví dụ: (2, 4) và (4, 2) là cùng một cặp khi nói về hiệu tuyệt đối, nhưng trong bài này, chúng ta có thể coi (a, b) và (b, a) là các cặp riêng biệt nếu thứ tự quan trọng, hoặc chỉ xét i < j nếu thứ tự không quan trọng và chúng ta muốn đếm các cặp duy nhất. Đề bài thường ngụ ý đếm các cặp phần tử khác vị trí, tức là (danh_sach[i], danh_sach[j]) với i != j. Tuy nhiên, cách phổ biến nhất trong các bài toán dạng này là đếm các cặp không có thứ tự, tức là chỉ xét i < j. Hãy đi theo hướng đếm các cặp không có thứ tự để tránh trùng lặp và làm quen với mẫu duyệt phổ biến này.

Mã nguồn:

def dem_cap_hieu_chan_thobao(danh_sach):
    """
    Đếm số cặp có hiệu chẵn bằng cách duyệt qua tất cả các cặp (i < j).

    Args:
        danh_sach: Danh sách các số nguyên.

    Returns:
        Số lượng các cặp (danh_sach[i], danh_sach[j]) với i < j 
        sao cho danh_sach[i] - danh_sach[j] là số chẵn.
    """
    so_luong_cap = 0
    n = len(danh_sach)

    # Duyệt qua tất cả các chỉ số i từ 0 đến n-2
    for i in range(n - 1):
        # Duyệt qua tất cả các chỉ số j từ i+1 đến n-1
        for j in range(i + 1, n):
            # Lấy hai số trong cặp
            so1 = danh_sach[i]
            so2 = danh_sach[j]

            # Kiểm tra hiệu có phải số chẵn không
            # Sử dụng toán tử % để kiểm tra tính chẵn lẻ
            if (so1 - so2) % 2 == 0:
                so_luong_cap += 1

    return so_luong_cap

# Ví dụ minh họa
print(f"Ví dụ 1: {dem_cap_hieu_chan_thobao([1, 2, 3, 4, 5])}") # Output: 4
# Các cặp có hiệu chẵn (chỉ xét i < j): (1,3), (1,5), (2,4), (3,5)

print(f"Ví dụ 2: {dem_cap_hieu_chan_thobao([2, 4, 6, 8])}") # Output: 6
# Tất cả các cặp đều là (chẵn, chẵn), hiệu đều chẵn.
# (2,4), (2,6), (2,8), (4,6), (4,8), (6,8)

print(f"Ví dụ 3: {dem_cap_hieu_chan_thobao([1, 3, 5, 7])}") # Output: 6
# Tất cả các cặp đều là (lẻ, lẻ), hiệu đều chẵn.
# (1,3), (1,5), (1,7), (3,5), (3,7), (5,7)

print(f"Ví dụ 4: {dem_cap_hieu_chan_thobao([10, 21, 14, 35, 42])}") # Output: 4
# Chẵn: 10, 14, 42. Lẻ: 21, 35
# Cặp chẵn-chẵn: (10,14), (10,42), (14,42) -> 3 cặp
# Cặp lẻ-lẻ: (21,35) -> 1 cặp
# Tổng cộng: 3 + 1 = 4

print(f"Ví dụ 5: {dem_cap_hieu_chan_thobao([])}") # Output: 0

print(f"Ví dụ 6: {dem_cap_hieu_chan_thobao([100])}") # Output: 0

Giải thích mã nguồn:

1. Hàm dem_cap_hieu_chan_thobao nhận một danh sách danh_sach làm đầu vào.
2. Khởi tạo biến so_luong_cap bằng 0 để đếm số lượng cặp thỏa mãn.
3. Lấy độ dài của danh sách là n.
4. Vòng lặp ngoài chạy từ i = 0 đến n - 2. Tại sao đến n - 2? Vì chúng ta cần ít nhất một phần tử nữa (j) sau i để tạo thành một cặp.
5. Vòng lặp trong chạy từ j = i + 1 đến n - 1. Tại sao bắt đầu từ i + 1? Điều này đảm bảo chúng ta chỉ xét các cặp mà chỉ số thứ hai (j) lớn hơn chỉ số thứ nhất (i). Điều này ngăn chặn việc đếm cùng một cặp hai lần ((a, b) và (b, a)) và bỏ qua các cặp mà hai phần tử là cùng một vị trí ((a, a)).
6. Bên trong vòng lặp trong, chúng ta lấy hai số so1 và so2 tại các vị trí i và j.
7. Chúng ta kiểm tra điều kiện (so1 - so2) % 2 == 0. Toán tử % lấy phần dư của phép chia. Nếu hiệu chia cho 2 có phần dư bằng 0, nghĩa là hiệu đó là số chẵn.
8. Nếu điều kiện đúng, chúng ta tăng biến đếm so_luong_cap lên 1.
9. Sau khi duyệt hết tất cả các cặp có thể, hàm trả về tổng số lượng cặp đã đếm được.

Cách tiếp cận này đúng và đơn giản để hiểu. Tuy nhiên, nó có nhược điểm về hiệu suất. Với hai vòng lặp lồng nhau, độ phức tạp về thời gian của giải thuật này là O(n^2), trong đó n là số phần tử trong danh sách. Điều này có nghĩa là nếu danh sách có 1000 phần tử, chúng ta sẽ thực hiện khoảng 1 triệu phép kiểm tra. Nếu danh sách có 1 triệu phần tử, chúng ta sẽ thực hiện khoảng 1 nghìn tỷ phép kiểm tra - điều này sẽ rất chậm!

Vậy có cách nào hiệu quả hơn không?

Cách Tiếp Cận 2: Tối Ưu Hơn - Dựa Vào Tính Chẵn Lẻ

Như chúng ta đã phân tích ban đầu, hiệu của hai số là chẵn khi chúng cùng tính chẵn lẻ. Điều này có nghĩa là chúng ta chỉ cần đếm:

1. Số lượng các cặp mà cả hai số đều là số chẵn.
2. Số lượng các cặp mà cả hai số đều là số lẻ.

Tổng của hai số lượng này chính là đáp án bài toán!

Làm thế nào để đếm số lượng các cặp cùng tính chẵn lẻ?

Giả sử chúng ta có count_even số chẵn và count_odd số lẻ trong danh sách.

• Số lượng cặp (chẵn, chẵn): Chúng ta cần chọn 2 số từ count_even số chẵn có sẵn. Số cách chọn 2 phần tử từ k phần tử (không lặp lại, không xét thứ tự) là công thức tổ hợp C(k, 2), được tính bằng k * (k - 1) / 2. Áp dụng vào đây, số lượng cặp (chẵn, chẵn) là count_even * (count_even - 1) // 2. (Sử dụng // cho phép chia lấy phần nguyên trong Python 3 để đảm bảo kết quả là số nguyên). Nếu count_even nhỏ hơn 2, kết quả là 0.
• Số lượng cặp (lẻ, lẻ): Tương tự, số lượng cặp (lẻ, lẻ) là count_odd * (count_odd - 1) // 2. Nếu count_odd nhỏ hơn 2, kết quả là 0.

Tổng số lượng cặp có hiệu chẵn sẽ là (số cặp chẵn-chẵn) + (số cặp lẻ-lẻ).

Mã nguồn:

def dem_cap_hieu_chan_toi_uu(danh_sach):
    """
    Đếm số cặp có hiệu chẵn bằng cách đếm số chẵn, số lẻ 
    và áp dụng công thức tổ hợp.

    Args:
        danh_sach: Danh sách các số nguyên.

    Returns:
        Số lượng các cặp (a, b) trong danh sách (không xét thứ tự, 
        a và b khác vị trí) sao cho a - b là số chẵn.
    """
    so_luong_chan = 0
    so_luong_le = 0

    # Bước 1: Duyệt qua danh sách để đếm số chẵn và số lẻ
    for so in danh_sach:
        if so % 2 == 0: # Kiểm tra số chẵn
            so_luong_chan += 1
        else: # Là số lẻ
            so_luong_le += 1

    # Bước 2: Tính số cặp chẵn-chẵn
    # Công thức tổ hợp C(k, 2) = k * (k-1) / 2
    # Cần kiểm tra k >= 2 để tránh lỗi hoặc kết quả không hợp lý
    if so_luong_chan >= 2:
        cap_chan_chan = so_luong_chan * (so_luong_chan - 1) // 2
    else:
        cap_chan_chan = 0

    # Bước 3: Tính số cặp lẻ-lẻ
    if so_luong_le >= 2:
        cap_le_le = so_luong_le * (so_luong_le - 1) // 2
    else:
        cap_le_le = 0

    # Bước 4: Tổng số cặp hiệu chẵn
    tong_so_cap = cap_chan_chan + cap_le_le

    return tong_so_cap

# Ví dụ minh họa (sử dụng lại các ví dụ trước để so sánh)
print(f"Ví dụ 1 (Tối ưu): {dem_cap_hieu_chan_toi_uu([1, 2, 3, 4, 5])}") # Output: 4
# Chẵn: 2, 4 (2 số chẵn). Lẻ: 1, 3, 5 (3 số lẻ)
# Cặp chẵn-chẵn: 2*(2-1)//2 = 1
# Cặp lẻ-lẻ: 3*(3-1)//2 = 3
# Tổng: 1 + 3 = 4

print(f"Ví dụ 2 (Tối ưu): {dem_cap_hieu_chan_toi_uu([2, 4, 6, 8])}") # Output: 6
# Chẵn: 2, 4, 6, 8 (4 số chẵn). Lẻ: (0 số lẻ)
# Cặp chẵn-chẵn: 4*(4-1)//2 = 6
# Cặp lẻ-lẻ: 0*(0-1)//2 = 0
# Tổng: 6 + 0 = 6

print(f"Ví dụ 3 (Tối ưu): {dem_cap_hieu_chan_toi_uu([1, 3, 5, 7])}") # Output: 6
# Chẵn: (0 số chẵn). Lẻ: 1, 3, 5, 7 (4 số lẻ)
# Cặp chẵn-chẵn: 0*(0-1)//2 = 0
# Cặp lẻ-lẻ: 4*(4-1)//2 = 6
# Tổng: 0 + 6 = 6

print(f"Ví dụ 4 (Tối ưu): {dem_cap_hieu_chan_toi_uu([10, 21, 14, 35, 42])}") # Output: 4
# Chẵn: 10, 14, 42 (3 số chẵn). Lẻ: 21, 35 (2 số lẻ)
# Cặp chẵn-chẵn: 3*(3-1)//2 = 3
# Cặp lẻ-lẻ: 2*(2-1)//2 = 1
# Tổng: 3 + 1 = 4

print(f"Ví dụ 5 (Tối ưu): {dem_cap_hieu_chan_toi_uu([])}") # Output: 0
# Chẵn: 0. Lẻ: 0.
# Cặp chẵn-chẵn: 0. Cặp lẻ-lẻ: 0. Tổng: 0.

print(f"Ví dụ 6 (Tối ưu): {dem_cap_hieu_chan_toi_uu([100])}") # Output: 0
# Chẵn: 1. Lẻ: 0.
# Cặp chẵn-chẵn: 0. Cặp lẻ-lẻ: 0. Tổng: 0.

Giải thích mã nguồn:

1. Hàm dem_cap_hieu_chan_toi_uu nhận danh sách danh_sach.
2. Khởi tạo hai biến đếm: so_luong_chan và so_luong_le đều bằng 0.
3. Chúng ta chỉ cần một vòng lặp để duyệt qua toàn bộ danh sách.
4. Trong vòng lặp, với mỗi so trong danh sách, chúng ta kiểm tra tính chẵn lẻ của nó bằng so % 2.
5. Nếu so % 2 == 0, đó là số chẵn, tăng so_luong_chan lên 1.
6. Ngược lại, đó là số lẻ, tăng so_luong_le lên 1.
7. Sau khi vòng lặp kết thúc, chúng ta đã có tổng số lượng số chẵn và số lẻ trong danh sách.
8. Áp dụng công thức tổ hợp để tính số cặp (chẵn, chẵn): so_luong_chan * (so_luong_chan - 1) // 2. Điều kiện if so_luong_chan >= 2 được thêm vào để đảm bảo chúng ta chỉ thực hiện phép tính khi có ít nhất 2 số chẵn.
9. Tương tự, tính số cặp (lẻ, lẻ) với so_luong_le * (so_luong_le - 1) // 2.
10. Tổng hai giá trị này chính là kết quả cuối cùng.

Cách tiếp cận này hiệu quả hơn đáng kể. Chúng ta chỉ cần một lần duyệt qua danh sách để đếm số chẵn và số lẻ. Sau đó, việc tính toán dựa vào công thức tổ hợp là các phép toán cơ bản (nhân, trừ, chia), không phụ thuộc vào kích thước n của danh sách. Do đó, độ phức tạp về thời gian của giải thuật này là O(n), nhanh hơn rất nhiều so với O(n^2) khi n lớn.

So Sánh Hai Cách Tiếp Cận

Rõ ràng, cách tiếp cận thứ hai dựa vào tính chất của số chẵn/lẻ và công thức tổ hợp là ưu việt hơn về mặt hiệu suất đối với danh sách có kích thước lớn. Cách "thô bạo" có thể hữu ích để bắt đầu suy nghĩ về vấn đề hoặc khi danh sách rất nhỏ và hiệu suất không phải là vấn đề chính. Tuy nhiên, trong môi trường thực tế, giải pháp O(n) luôn được ưu tiên hơn O(n^2) khi có thể.

Hy vọng qua bài tập này, bạn không chỉ giải được bài toán mà còn thấy được sức mạnh của việc phân tích vấn đề (như tính chất chẵn lẻ) để tìm ra giải pháp tối ưu hơn.

Chúc bạn luyện tập vui vẻ!