Ôn thi HSG Tin học THPT – Bài 4: Cấu trúc dữ liệu List (Mảng 1 chiều, 2 chiều)

1. Mục tiêu

Nắm vững các thao tác cơ bản với cấu trúc dữ liệu list trong Python, bao gồm: khai báo, truy cập, thay đổi và cắt lát (slicing).
Hiểu và vận dụng được kỹ thuật sử dụng list lồng nhau để mô phỏng và thao tác với mảng hai chiều.

2. Giới thiệu và phạm vi ứng dụng

Trong ngôn ngữ lập trình Python, list là một trong những cấu trúc dữ liệu tuần tự (sequence) cốt lõi và linh hoạt nhất. Một list là một tập hợp các phần tử có thứ tự và có thể thay đổi (mutable). Do tính chất này, list thường được sử dụng để triển khai cấu trúc mảng một chiều.

Trong lập trình thi đấu, việc xử lý các tập hợp dữ liệu là yêu cầu cơ bản. Cấu trúc list cung cấp một cơ chế hiệu quả để lưu trữ, quản lý và truy xuất dữ liệu, từ các dãy số đơn giản (mảng một chiều) đến các cấu trúc phức tạp hơn như ma trận hoặc bảng (mảng hai chiều). Việc thành thạo list là nền tảng bắt buộc để giải quyết phần lớn các bài toán.

3. Cú pháp và ví dụ minh họa

3.1. Các thao tác cơ bản với List (Mảng 1 chiều)

3.1.1. Khai báo

Một list được tạo ra bằng cách đặt các phần tử bên trong cặp dấu ngoặc vuông [], phân tách nhau bởi dấu phẩy.

# Khai báo một list rỗng
empty_list = []

# Khai báo một list chứa các số nguyên
numbers = [10, 20, 30, 40, 50]

# Khai báo một list chứa các kiểu dữ liệu khác nhau
mixed_list = [1, "hello", 3.14, True]

print(numbers)
# Output: [10, 20, 30, 40, 50]

3.1.2. Truy cập phần tử

Các phần tử trong list được truy cập thông qua chỉ số (index), bắt đầu từ 0.

numbers = [10, 20, 30, 40, 50]

# Truy cập phần tử đầu tiên (chỉ số 0)
first_element = numbers[0]
print(f"Phần tử đầu tiên: {first_element}") # Output: Phần tử đầu tiên: 10

# Truy cập phần tử cuối cùng (chỉ số -1)
last_element = numbers[-1]
print(f"Phần tử cuối cùng: {last_element}") # Output: Phần tử cuối cùng: 50

3.1.3. Thay đổi phần tử

Vì list là cấu trúc có thể thay đổi (mutable), giá trị của các phần tử có thể được cập nhật trực tiếp thông qua chỉ số.

numbers = [10, 20, 30, 40, 50]
print(f"List ban đầu: {numbers}")

# Thay đổi giá trị của phần tử tại chỉ số 2
numbers[2] = 99
print(f"List sau khi thay đổi: {numbers}")
# Output:
# List ban đầu: [10, 20, 30, 40, 50]
# List sau khi thay đổi: [10, 20, 99, 40, 50]

3.1.4. Cắt lát (Slicing)

Cắt lát là kỹ thuật trích xuất một list con từ list ban đầu. Cú pháp chung là my_list[start:stop:step].

start: Chỉ số bắt đầu (bao gồm). Mặc định là 0.
stop: Chỉ số kết thúc (không bao gồm). Mặc định là độ dài của list.
step: Bước nhảy. Mặc định là 1.

numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Lấy các phần tử từ chỉ số 2 đến 4 (không bao gồm 5)
sub_list1 = numbers[2:5]
print(f"numbers[2:5] -> {sub_list1}") # Output: numbers[2:5] -> [2, 3, 4]

# Lấy các phần tử từ đầu đến chỉ số 3 (không bao gồm 4)
sub_list2 = numbers[:4]
print(f"numbers[:4] -> {sub_list2}") # Output: numbers[:4] -> [0, 1, 2, 3]

# Lấy các phần tử từ chỉ số 5 đến cuối
sub_list3 = numbers[5:]
print(f"numbers[5:] -> {sub_list3}") # Output: numbers[5:] -> [5, 6, 7, 8, 9]

# Lấy toàn bộ list với bước nhảy 2
sub_list4 = numbers[::2]
print(f"numbers[::2] -> {sub_list4}") # Output: numbers[::2] -> [0, 2, 4, 6, 8]

3.2. Ví dụ 1: Thao tác trên mảng 1 chiều

Duyệt qua các phần tử của một list và tính tổng của chúng.

# Khởi tạo một list các điểm số
scores = [8, 9, 10, 7, 8, 6]

# Tính tổng các điểm số
total_score = 0
# Vòng lặp for duyệt qua từng phần tử trong list
for score in scores:
    total_score += score

# Tính điểm trung bình
average_score = total_score / len(scores)

print(f"Danh sách điểm: {scores}")
print(f"Tổng điểm: {total_score}")
print(f"Điểm trung bình: {average_score:.2f}") # Làm tròn đến 2 chữ số thập phân

3.3. Ví dụ 2: Mô phỏng mảng 2 chiều bằng list lồng nhau

Mảng 2 chiều (ma trận) có thể được mô phỏng bằng một list chứa các list khác, trong đó mỗi list con đại diện cho một hàng.

# Khai báo một ma trận 3x4 (3 hàng, 4 cột)
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]

# Truy cập phần tử ở hàng 1, cột 2 (chỉ số là [0][1])
# Lưu ý: chỉ số hàng và cột đều bắt đầu từ 0
element = matrix[0][1]
print(f"Phần tử tại hàng 1, cột 2 là: {element}") # Output: Phần tử tại hàng 1, cột 2 là: 2

# Thay đổi giá trị phần tử ở hàng 3, cột 4 (chỉ số [2][3])
matrix[2][3] = 99

# Duyệt và in toàn bộ ma trận
print("Ma trận sau khi cập nhật:")
for row in matrix:
    # row là một list con, đại diện cho một hàng
    for item in row:
        # In từng phần tử trên cùng một dòng, cách nhau bởi một khoảng trắng
        print(item, end=" ")
    # Xuống dòng sau khi in xong một hàng
    print()

# Output:
# Ma trận sau khi cập nhật:
# 1 2 3 4
# 5 6 7 8
# 9 10 11 99

4. Trực quan hóa và gỡ lỗi với Thonny

Thonny là một môi trường phát triển tích hợp (IDE) lý tưởng cho người mới bắt đầu học Python. Công cụ “Variables” của Thonny cho phép trực quan hóa cấu trúc của các biến trong chương trình một cách rõ ràng.

Khi làm việc với list lồng nhau để tạo mảng 2 chiều, Thonny sẽ hiển thị list cha và các list con bên trong nó. Điều này giúp người học dễ dàng hình dung được cấu trúc hàng và cột, cũng như cách các phần tử được lưu trữ và tham chiếu thông qua hai chỉ số [hàng][cột]. Việc sử dụng trình gỡ lỗi (debugger) của Thonny để đi từng bước qua các vòng lặp lồng nhau sẽ làm sáng tỏ quá trình duyệt và xử lý ma trận.

5. Bài tập vận dụng

5.1. Bài tập 1

5.1.1. Đề bài

Viết chương trình Python thực hiện các yêu cầu sau:
a. Nhập vào từ bàn phím một số nguyên dương N.
b. Nhập N số nguyên từ bàn phím và lưu vào một list.
c. Tìm và in ra màn hình giá trị lớn nhất (max) và giá trị nhỏ nhất (min) trong list vừa nhập.

5.1.2. Lời giải và phân tích

# Bước a: Nhập số nguyên dương N
try:
    n = int(input("Nhập số lượng phần tử N: "))
    if n <= 0:
        print("N phải là số nguyên dương.")
    else:
        # Khởi tạo list rỗng để lưu các số
        numbers = []

        # Bước b: Nhập N số nguyên và lưu vào list
        print(f"Nhập {n} số nguyên, mỗi số trên một dòng:")
        for i in range(n):
            # Nhập, ép kiểu và thêm vào cuối list
            num = int(input())
            numbers.append(num)

        # Bước c: Tìm giá trị lớn nhất và nhỏ nhất
        # Giả định phần tử đầu tiên là cả max và min
        max_val = numbers[0]
        min_val = numbers[0]

        # Duyệt qua các phần tử còn lại để so sánh
        for i in range(1, n):
            if numbers[i] > max_val:
                max_val = numbers[i]
            if numbers[i] < min_val:
                min_val = numbers[i]
        
        # In kết quả
        print(f"List đã nhập: {numbers}")
        print(f"Giá trị lớn nhất: {max_val}")
        print(f"Giá trị nhỏ nhất: {min_val}")

        # Ghi chú: Python có các hàm tích hợp sẵn là max() và min()
        # print(f"Max (dùng hàm sẵn có): {max(numbers)}")
        # print(f"Min (dùng hàm sẵn có): {min(numbers)}")

except ValueError:
    print("Dữ liệu nhập vào không hợp lệ. Vui lòng nhập số nguyên.")

Phân tích thuật toán:
1. Khởi tạo hai biến max_val và min_val bằng giá trị của phần tử đầu tiên trong list.
2. Sử dụng một vòng lặp for để duyệt qua các phần tử của list, bắt đầu từ phần tử thứ hai (chỉ số 1).
3. Trong mỗi vòng lặp, so sánh phần tử hiện tại với max_val và min_val. Nếu phần tử hiện tại lớn hơn max_val, cập nhật max_val. Tương tự, nếu nhỏ hơn min_val, cập nhật min_val.
4. Sau khi vòng lặp kết thúc, max_val và min_val sẽ lưu giữ giá trị lớn nhất và nhỏ nhất trong list.
Phân tích cài đặt: Chương trình sử dụng vòng lặp for i in range(n) để đảm bảo nhập đủ N phần tử. Phương thức append() được dùng để thêm phần tử mới vào cuối list. Logic tìm max/min được cài đặt theo thuật toán đã phân tích.

5.2. Bài tập 2

5.2.1. Đề bài

Viết chương trình Python nhập vào một ma trận vuông cấp N (N hàng, N cột) chứa các số nguyên. Tính và in ra màn hình tổng các phần tử nằm trên đường chéo chính của ma trận. Đường chéo chính là các phần tử có chỉ số hàng bằng chỉ số cột (matrix[i][i]).

5.2.2. Lời giải và Phân tích

# Nhập cấp của ma trận vuông
try:
    n = int(input("Nhập cấp N của ma trận vuông: "))
    if n <= 0:
        print("N phải là số nguyên dương.")
    else:
        matrix = []
        print(f"Nhập các phần tử cho ma trận {n}x{n}:")

        # Nhập dữ liệu cho ma trận
        for i in range(n):
            row = [] # Khởi tạo một hàng mới
            print(f"Nhập {n} phần tử cho hàng {i+1} (cách nhau bởi khoảng trắng):")
            # Đọc cả dòng, tách thành các chuỗi, rồi chuyển từng chuỗi thành số nguyên
            input_row = input().split()
            for item in input_row:
                row.append(int(item))
            matrix.append(row) # Thêm hàng đã hoàn chỉnh vào ma trận

        # Tính tổng đường chéo chính
        diagonal_sum = 0
        for i in range(n):
            # Các phần tử trên đường chéo chính có chỉ số hàng bằng chỉ số cột
            diagonal_sum += matrix[i][i]

        # In kết quả
        print("\nMa trận đã nhập:")
        for row in matrix:
            print(row)
        
        print(f"\nTổng các phần tử trên đường chéo chính là: {diagonal_sum}")

except ValueError:
    print("Dữ liệu nhập vào không hợp lệ.")
except IndexError:
    print("Số lượng phần tử nhập vào mỗi hàng không đủ.")

Phân tích thuật toán:
1. Xác định các phần tử thuộc đường chéo chính. Theo định nghĩa, một phần tử matrix[i][j] nằm trên đường chéo chính nếu và chỉ nếu i = j.
2. Khởi tạo một biến total với giá trị 0.
3. Sử dụng một vòng lặp chạy từ i = 0 đến N-1. Trong mỗi vòng lặp, truy cập phần tử matrix[i][i] và cộng giá trị của nó vào biến total.
4. Sau khi vòng lặp kết thúc, total sẽ là tổng cần tìm.
Phân tích cài đặt: Chương trình sử dụng hai vòng lặp lồng nhau để nhập dữ liệu cho ma trận. Vòng lặp ngoài (for i in range(n)) duyệt qua các hàng. Sau đó, một vòng lặp đơn (for i in range(n)) được sử dụng để duyệt qua các chỉ số từ 0 đến N-1, đủ để truy cập tất cả các phần tử trên đường chéo chính (matrix[i][i]) và cộng chúng lại.

6. Các lưu ý và lỗi thường gặp

IndexError: list index out of range: Lỗi này xảy ra khi cố gắng truy cập một chỉ số không tồn tại trong list (ví dụ: truy cập numbers[5] trong khi list chỉ có 5 phần tử, tức là chỉ số hợp lệ từ 0 đến 4). Luôn đảm bảo chỉ số nằm trong khoảng [-len(list), len(list)-1].
Khởi tạo mảng 2 chiều: Cần cẩn trọng khi khởi tạo mảng 2 chiều. Cách viết matrix = [[0] * cols] * rows sẽ tạo ra một lỗi logic ngầm. Tất cả các hàng sẽ tham chiếu đến cùng một đối tượng list, dẫn đến việc thay đổi một phần tử ở một hàng sẽ làm thay đổi tất cả các hàng khác.
- Cách viết sai: wrong_matrix = [[0] * 3] * 3
- Cách viết đúng: correct_matrix = [[0 for _ in range(3)] for _ in range(3)]
Sự khác biệt giữa append() và extend(): append() thêm toàn bộ đối tượng vào cuối list như một phần tử duy nhất. extend() duyệt qua một đối tượng khả lặp (iterable) và thêm từng phần tử của nó vào cuối list.

7. Tổng kết

Bài học đã giới thiệu về list, một trong những cấu trúc dữ liệu quan trọng và được sử dụng rộng rãi nhất trong Python. Các kiến thức cốt lõi bao gồm cách khai báo, truy cập, sửa đổi, và cắt lát một list (đóng vai trò như mảng 1 chiều). Ngoài ra, bài học cũng trình bày phương pháp sử dụng list lồng nhau để mô phỏng và làm việc với mảng 2 chiều (ma trận), một kỹ thuật cơ bản và phổ biến trong lập trình thi đấu và khoa học máy tính. Việc nắm vững các thao tác này là điều kiện tiên quyết để giải quyết các bài toán phức tạp hơn.