Giải bài toán trên danh sách

Lan ghi số sách mượn trong bốn ngày: 3, 5, 3 và 2. Lan muốn biết tổng số sách, ngày đầu có 3 lượt mượn và thứ tự từ ít đến nhiều. Các thao tác trên danh sách giúp bạn trả lời từng câu hỏi đó.

Các hàm tổng hợp trả lời nhanh về một dãy

Với số sách của bốn ngày, hãy tính tổng và tìm hai giá trị ở hai đầu khoảng:

luot = [3, 5, 3, 2]
print(sum(luot))
print(min(luot))
print(max(luot))

13
2
5

sum cộng các phần tử. min trả về giá trị nhỏ nhất; max trả về giá trị lớn nhất. Chúng trả về giá trị, không trả về vị trí của giá trị đó. Các hàm này không sửa luot.

Một danh sách rỗng có tổng là 0. Tuy nhiên, nó không có phần tử nhỏ nhất hay lớn nhất:

luot = []
print(max(luot))

ValueError: max() iterable argument is empty

Python báo ValueError. Khi có thể nhận danh sách rỗng, hãy kiểm tra độ dài trước khi gọi min hoặc max.

Tự duyệt để tìm cực trị và đếm theo điều kiện

Để hiểu max hoạt động ra sao, bạn có thể giữ giá trị lớn nhất đã gặp:

diem = [-4, -2, -7]
lon_nhat = diem[0]
for x in diem[1:]:
    if x > lon_nhat:
        lon_nhat = x
print(lon_nhat)

-2

Bắt đầu bằng phần tử đầu tiên vì danh sách có ít nhất một phần tử. Mỗi lần gặp x lớn hơn, cập nhật lon_nhat. Dùng 0 làm giá trị đầu sẽ sai nếu mọi điểm đều âm. Để tìm nhỏ nhất, đổi phép so sánh thành < và giữ giá trị nhỏ nhất đã gặp.

Chẳng hạn, một trạm lưu nhiệt độ trong ba giờ. Cùng cách duyệt đó tìm được nhiệt độ thấp nhất:

nhiet_do = [4, -2, 1]
nho_nhat = nhiet_do[0]
for x in nhiet_do[1:]:
    if x < nho_nhat:
        nho_nhat = x
print(nho_nhat)

-2

Sau mỗi lượt, nho_nhat là giá trị nhỏ nhất trong phần đã xét. So sánh nghiêm ngặt < không cập nhật khi gặp giá trị bằng nhau. Điều đó không ảnh hưởng đến giá trị nhỏ nhất. Nếu còn cần vị trí đầu hay cuối của giá trị ấy, bạn phải chọn quy tắc tìm vị trí riêng.

Đếm cần một biến riêng, bắt đầu từ 0. Chỉ tăng biến khi phần tử thỏa điều kiện:

luot = [3, 5, 4, 2]
dem = 0
for x in luot:
    if x >= 4:
        dem += 1
print(dem)

2

dem là số phần tử thỏa điều kiện, không phải tổng các giá trị đó. Với danh sách rỗng, vòng lặp không chạy và kết quả đếm là 0.

Khi dữ liệu đến từ người dùng, bạn có thể đọc một dòng điểm rồi đếm số điểm âm:

2 -3 0 -1

diem = list(map(int, input().split()))
dem = 0
for x in diem:
    if x < 0:
        dem += 1
print(dem)

2

Dòng dữ liệu có hai số âm. Điều kiện < 0 không tính số 0. Nếu cần tính cả số 0, thay điều kiện bằng <= 0; chọn dấu so sánh theo yêu cầu cụ thể.

any và all kiểm tra các giá trị đúng hoặc sai

Hãy đổi từng điểm thành kết quả so sánh, rồi kiểm tra cả danh sách:

diem = [7, 9, 6]
dat = [x >= 8 for x in diem]
print(dat)
print(any(dat))
print(all(dat))

[False, True, False]
True
False

any trả True khi có ít nhất một giá trị đúng. all trả True khi tất cả giá trị đều đúng. Ở đây có điểm đạt 8 nhưng không phải mọi điểm đều đạt. any và all xét giá trị đúng hoặc sai, không đếm số phần tử thỏa mãn.

Trường hợp danh sách rỗng cần được xử lý theo yêu cầu bài toán:

print(any([]))
print(all([]))

False
True

any([]) là False; all([]) là True. Nếu muốn yêu cầu phải có ít nhất một điểm và tất cả đều đạt, kiểm tra cả len(diem) > 0 lẫn all(dat).

Tìm kiếm tuần tự kiểm tra từng vị trí

Lan muốn tìm ngày đầu có 3 lượt. Tìm kiếm tuần tự (linear search) xem lần lượt từng phần tử:

luot = [5, 3, 2, 3]
vi_tri = -1
for i in range(len(luot)):
    if luot[i] == 3:
        vi_tri = i
        break
print(vi_tri)

1

-1 báo chưa tìm thấy; đây là quy ước của chương trình này. Khi gặp phần tử phù hợp, break dừng ngay. Kết quả là chỉ số 1, không phải ngày thứ nhất: số thứ tự ngày bằng chỉ số cộng 1.

Để tìm lần cuối, bạn có thể tiếp tục duyệt và cập nhật mỗi khi gặp giá trị cần tìm:

luot = [5, 3, 2, 3]
vi_tri = -1
for i in range(len(luot)):
    if luot[i] == 3:
        vi_tri = i
print(vi_tri)

3

Không có break, nên kết quả giữ chỉ số của lần khớp cuối. Nếu không có giá trị cần tìm, vi_tri vẫn là -1. Đừng dùng ngay luot[vi_tri] trước khi kiểm tra: chỉ số -1 còn có nghĩa là phần tử cuối của danh sách.

Hoán đổi, đảo và xoay thay đổi thứ tự

Đổi chỗ hai phần tử bằng cách gán đồng thời:

so = [4, 8, 2, 6]
so[0], so[-1] = so[-1], so[0]
print(so)

[6, 8, 2, 4]

Hai giá trị bên phải được lấy trước khi gán. Cách này tránh làm mất giá trị đầu. Danh sách phải không rỗng khi truy cập hai đầu.

Đảo thứ tự bằng lát cắt tạo danh sách mới, còn reverse() sửa danh sách hiện tại:

so = [4, 8, 2]
nguoc = so[::-1]
so.reverse()
print(nguoc)
print(so)

[2, 8, 4]
[2, 8, 4]

nguoc là bản riêng. so.reverse() thay đổi so tại chỗ và trả về None; không gán kết quả đó lại cho so.

Xoay (rotation) giữ thứ tự tương đối nhưng đưa một phần ở đầu hoặc cuối sang phía còn lại. Xoay trái một bước đưa phần tử đầu xuống cuối:

so = [4, 8, 2, 6]
xoay = so[1:] + so[:1]
print(xoay)

[8, 2, 6, 4]

Với danh sách rỗng, hai lát cắt đều rỗng. Khi xoay trái k bước trên danh sách không rỗng, dùng k % len(so) để số bước nằm trong khoảng phù hợp. Kiểm tra rỗng trước vì chia dư cho 0 gây lỗi:

so = [4, 8, 2, 6]
k = 6
if len(so) > 0:
    buoc = k % len(so)
    xoay = so[buoc:] + so[:buoc]
else:
    xoay = []
print(xoay)

[2, 6, 4, 8]

Sáu bước trên bốn phần tử tương đương hai bước. Một vòng đủ bốn bước trả danh sách về thứ tự ban đầu. Nhánh else cho phép cùng cách xử lý khi so rỗng mà không tính phần dư.

so = []
print(2 % len(so))

ZeroDivisionError: integer modulo by zero

sorted tạo bản mới còn sort sửa danh sách

Để xếp điểm tăng dần, hãy tạo một danh sách mới:

diem = [8, 5, 9, 5]
sap_xep = sorted(diem)
print(sap_xep)
print(diem)

[5, 5, 8, 9]
[8, 5, 9, 5]

sorted(diem) trả danh sách mới. Giá trị trùng vẫn được giữ đủ. Ngược lại, sort() sửa chính danh sách và trả None:

diem = [8, 5, 9, 5]
diem.sort(reverse=True)
print(diem)

[9, 8, 5, 5]

reverse=True yêu cầu thứ tự giảm. Có thể dùng cùng đối số với sorted. Nếu hai tên cùng trỏ đến một danh sách, gọi sort() qua một tên sẽ làm tên kia thấy thứ tự mới.

Gán kết quả của sort là một lỗi dễ gặp vì phương thức trả None:

diem = [8, 5, 9]
diem = diem.sort()
print(diem[0])

TypeError: 'NoneType' object is not subscriptable

Sau phép gán, diem là None, nên lấy chỉ số gây TypeError. Nếu muốn một biến mới, dùng sap_xep = sorted(diem). Nếu muốn sửa tại chỗ, gọi diem.sort() trên dòng riêng.

key chọn tiêu chí sắp xếp

Tên ngắn có thể được xếp trước tên dài bằng key=len:

ten = ["Binh", "An", "Mai"]
print(sorted(ten, key=len))

['An', 'Mai', 'Binh']

key nhận một hàm; Python gọi hàm đó cho từng phần tử và so sánh kết quả. key=len truyền hàm, còn key=len() cố gọi len khi chưa có đối số và gây lỗi:

ten = ["Binh", "An"]
print(sorted(ten, key=len()))

TypeError: len() takes exactly one argument (0 given)

Hai tên cùng độ dài có cùng khóa. Khi chỉ yêu cầu xếp theo độ dài, thứ tự ban đầu của hai tên đó được giữ:

ten = ["Mai", "An", "Chi", "Binh"]
print(sorted(ten, key=len))

['An', 'Mai', 'Chi', 'Binh']

An ngắn hơn nên đứng đầu. Mai và Chi cùng dài ba ký tự, vì vậy Mai vẫn đứng trước Chi. Quy tắc này gọi là sắp xếp ổn định (stable sort). Nếu muốn phá hòa theo chữ cái, bạn cần cung cấp tiêu chí phụ như phần tiếp theo.

Khi cần một quy tắc ngắn tự viết, dùng hàm vô danh (lambda):

so = [6, 11, 8]
print(sorted(so, key=lambda x: abs(x - 10)))

[11, 8, 6]

lambda x: abs(x - 10) nhận một số x và trả khoảng cách của nó đến 10. Hàm abs lấy giá trị tuyệt đối. Số 11 có khoảng cách 1 nên đứng trước 8 và 6. Nếu các khóa bằng nhau, Python giữ thứ tự ban đầu của các phần tử đó.

Khóa gồm nhiều giá trị phá hòa theo từng tiêu chí

Hãy xếp tên theo độ dài, rồi theo chữ cái khi độ dài bằng nhau:

ten = ["Mai", "An", "Chi", "Bo"]
ket_qua = sorted(ten, key=lambda x: (len(x), x))
print(ket_qua)

['An', 'Bo', 'Chi', 'Mai']

(len(x), x) là một cặp giá trị trong bộ giá trị (tuple). Ở đây chỉ cần xem nó là hai tiêu chí đặt trong ngoặc và ngăn bằng dấu phẩy. Python so sánh độ dài trước; nếu bằng nhau, Python so sánh tên. Bài 13 sẽ học kỹ hơn về tuple.

Để điểm lớn đứng trước, nhưng tên vẫn tăng khi bằng điểm, đổi dấu tiêu chí điểm:

ten = ["Mai", "An", "Chi"]
diem = [8, 9, 8]
thu_tu = sorted(range(len(ten)), key=lambda i: (-diem[i], ten[i]))
print(thu_tu)
for i in thu_tu:
    print(ten[i], diem[i])

[1, 2, 0]
An 9
Chi 8
Mai 8

range(len(ten)) cung cấp các chỉ số 0, 1, 2. Ta sắp xếp các chỉ số, không sắp xếp trực tiếp tên. Với mỗi chỉ số i, diem[i] và ten[i] lấy điểm và tên tương ứng. Kết quả [1, 2, 0] cho biết thứ tự cần dùng để in. Khóa đầu là -diem[i]: điểm 9 thành -9 và được xếp trước -8. Khi điểm bằng nhau, tên quyết định. Dùng reverse=True cho cả khóa sẽ đảo cả thứ tự tên, không chỉ điểm.

Hai vòng lặp đếm các cặp vị trí khác nhau

Bạn muốn đếm các cặp ngày có cùng số lượt mượn. Mỗi cặp chỉ được tính một lần:

luot = [2, 3, 2, 2]
dem = 0
for i in range(len(luot)):
    for j in range(i + 1, len(luot)):
        if luot[i] == luot[j]:
            dem += 1
print(dem)

3

Vòng ngoài chọn vị trí i. Vòng trong chỉ chọn j sau i, nên không ghép một vị trí với chính nó và không đếm lại cặp đảo thứ tự. Ba vị trí chứa 2 tạo ba cặp, dù giá trị của chúng giống nhau. Với dưới hai phần tử, không có cặp nào.

Bạn có thể thay điều kiện bằng một phép kiểm tra khác. Ví dụ, để đếm cặp có tổng lớn hơn 7, dùng if luot[i] + luot[j] > 7: trong cùng cấu trúc. Ý nghĩa của cặp vẫn dựa trên vị trí. Hai thẻ khác vị trí có cùng giá trị vẫn là hai thẻ khác nhau.

Lỗi thường gặp

Tóm tắt

• sum, min, max, any, all tổng hợp thông tin từ danh sách.
• Duyệt tuần tự có thể tìm vị trí, tự tìm cực trị và đếm theo điều kiện.
• Lát cắt giúp tạo bản đảo hoặc xoay; reverse và sort sửa tại chỗ.
• sorted tạo bản mới; key chọn tiêu chí và một tuple có thể kết hợp tiêu chí.
• Hai vòng lặp với j > i duyệt mỗi cặp vị trí đúng một lần.

Kiểm tra nhanh

Đọc thêm

• Built-in Functions
• Sorting HOW TO