Bỏ qua để đến nội dung

Chương 10. Danh sách hai chiều

Nhiều dữ liệu có dạng bảng: bảng điểm (mỗi hàng một học sinh, mỗi cột một môn), bản đồ ô vuông trong trò chơi, ảnh số (mỗi ô một điểm ảnh). Trong toán học, bảng số gọi là ma trận.

Python biểu diễn bảng bằng một danh sách mà mỗi phần tử là một hàng, mỗi hàng lại là một danh sách:

grid = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
]
print(len(grid), len(grid[0])) # số hàng, số cột
print(grid[1]) # hàng chỉ số 1
print(grid[1][2]) # hàng 1, cột 2
grid[2][0] = 0
print(grid[2])
3 4
[5, 6, 7, 8]
7
[0, 10, 11, 12]

grid[i] là hàng thứ i (một danh sách), grid[i][j] là phần tử ở hàng i, cột j (cả hai chỉ số bắt đầu từ 0). Thứ tự luôn là hàng trước, cột sau.

cột 0cột 1cột 2cột 3
hàng 01234
hàng 15678
hàng 29101112

Tạo ma trận n hàng, m cột toàn số 0:

n, m = 3, 4
grid = [[0] * m for _ in range(n)]
grid[0][0] = 5
print(grid)
[[5, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
wrong = [[0] * 4] * 3
wrong[0][0] = 5
print(wrong)
[[5, 0, 0, 0], [5, 0, 0, 0], [5, 0, 0, 0]]

Với [[0] * m for _ in range(n)], biểu thức [0] * m được tính lại ở mỗi lần lặp, nên mỗi hàng là một danh sách riêng.

Dạng dữ liệu hay gặp: dòng đầu là n, m; n dòng sau, mỗi dòng m số.

n, m = map(int, input().split())
grid = []
for _ in range(n):
row = list(map(int, input().split()))
grid.append(row)
for row in grid:
print(*row)
1 2 3
4 5 6

Viết gọn: grid = [list(map(int, input().split())) for _ in range(n)]. In mỗi hàng trên một dòng bằng print(*row).

Hai vòng lặp lồng nhau: vòng ngoài theo hàng, vòng trong theo cột. Tính tổng từng hàng và tổng từng cột:

grid = [[1, 2, 3], [4, 5, 6]]
n, m = len(grid), len(grid[0])
for i in range(n):
print("hang", i, sum(grid[i]))
for j in range(m):
column_sum = 0
for i in range(n):
column_sum += grid[i][j]
print("cot", j, column_sum)
hang 0 6
hang 1 15
cot 0 5
cot 1 7
cot 2 9

Tổng một hàng có sẵn sum(grid[i]) vì hàng là một danh sách. Cột thì không có sẵn như vậy: phải duyệt grid[i][j] với j cố định, i chạy qua mọi hàng.

Ma trận vuông n × n có hai đường chéo:

  • Đường chéo chính (từ góc trên trái xuống góc dưới phải): các ô có i == j.
  • Đường chéo phụ (từ góc trên phải xuống góc dưới trái): các ô có i + j == n - 1.
a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = len(a)
main_diagonal = sum(a[i][i] for i in range(n))
anti_diagonal = sum(a[i][n - 1 - i] for i in range(n))
print(main_diagonal, anti_diagonal)
15 15

Mỗi đường chéo chỉ cần một vòng lặp, vì biết i là biết luôn j. (Viết sum(... for i in ...) là dạng comprehension không có ngoặc vuông, tính tổng trực tiếp.)

Trong bảng ô vuông, mỗi ô (i, j) có tối đa 8 ô xung quanh (4 ô chung cạnh và 4 ô chung đỉnh). Thay vì viết 8 câu lệnh if, ta lưu 8 hướng đi vào hai danh sách dr (thay đổi hàng) và dc (thay đổi cột):

grid = [
[1, 0, 0],
[0, 1, 1],
[0, 0, 1],
]
n, m = 3, 3
dr = [-1, -1, -1, 0, 0, 1, 1, 1]
dc = [-1, 0, 1, -1, 1, -1, 0, 1]
i, j = 1, 1
count = 0
for k in range(8):
r = i + dr[k]
c = j + dc[k]
if 0 <= r < n and 0 <= c < m and grid[r][c] == 1:
count += 1
print(count)
3

Điều kiện 0 <= r < n and 0 <= c < m kiểm tra ô kề nằm trong bảng; thiếu điều kiện này thì ô ở mép bảng sẽ truy cập ra ngoài. Điều kiện kiểm tra phải đứng trước grid[r][c]: khi ô nằm ngoài, Python dừng ở điều kiện đầu và không truy cập grid[r][c].

Lưu ý thêm: với Python, chỉ số âm không báo lỗi mà lấy phần tử từ cuối (grid[-1] là hàng cuối). Vì vậy quên kiểm tra r >= 0 không gây lỗi mà cho kết quả sai, rất khó phát hiện.

Chỉ xét 4 ô chung cạnh thì dùng dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1].

Ma trận chuyển vị của ma trận n × m là ma trận m × n, có hàng j là cột j của ma trận ban đầu: t[j][i] = a[i][j].

a = [[1, 2, 3], [4, 5, 6]]
n, m = len(a), len(a[0])
t = [[0] * n for _ in range(m)]
for i in range(n):
for j in range(m):
t[j][i] = a[i][j]
for row in t:
print(*row)
1 4
2 5
3 6

Tích của ma trận A (n × m) với ma trận B (m × p) là ma trận C (n × p), trong đó phần tử C[i][j] bằng tổng các tích của hàng i của A với cột j của B:

C[i][j] = A[i][0] × B[0][j] + A[i][1] × B[1][j] + … + A[i][m − 1] × B[m − 1][j]

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
n, m, p = 2, 2, 2
C = [[0] * p for _ in range(n)]
for i in range(n):
for j in range(p):
for k in range(m):
C[i][j] += A[i][k] * B[k][j]
for row in C:
print(*row)
19 22
43 50

Ví dụ C[0][0] = 1 × 5 + 2 × 7 = 19. Ba vòng lặp lồng nhau chạy n × p × m lần: với n = m = p = 100 là 106 lần, Python cần khoảng nửa giây. Số cột của A phải bằng số hàng của B thì mới nhân được.

LỗiHậu quả
Tạo bằng [[0] * m] * ncác hàng là cùng một danh sách, sửa một ô thì cả cột đổi
Nhầm thứ tự a[j][i] thay vì a[i][j]sai kết quả, hoặc IndexError khi ma trận không vuông
Duyệt range(n) cho cột khi số cột là mthiếu hoặc thừa cột
Quên kiểm tra ô kề nằm trong bảngIndexError ở mép dưới/phải; mép trên/trái thì lấy nhầm ô ở cuối (chỉ số âm)
In print(grid)in cả ngoặc vuông, sai định dạng; phải in từng hàng bằng print(*row)
  • Ma trận là danh sách các hàng; a[i][j] là hàng i, cột j; len(a) số hàng, len(a[0]) số cột.
  • Tạo: [[0] * m for _ in range(n)], không dùng [[0] * m] * n.
  • Đọc: [list(map(int, input().split())) for _ in range(n)]; in: for row in a: print(*row).
  • Tổng hàng sum(a[i]); tổng cột phải duyệt i. Chéo chính i == j, chéo phụ i + j == n - 1.
  • Ô kề: mảng hướng dr, dc và kiểm tra 0 <= r < n and 0 <= c < m.
  • Chuyển vị t[j][i] = a[i][j]; nhân ma trận ba vòng lặp lồng nhau.

Chương này có 6 bài tập thực hành:

  • Bài 10.1. Tổng hàng, tổng cột
  • Bài 10.2. Chuyển vị
  • Bài 10.3. Hai đường chéo
  • Bài 10.4. Dò mìn
  • Bài 10.5. Nhân ma trận
  • Bài 10.6. Ma trận xoắn ốc

Đề bài chi tiết (có ví dụ), lời giải từng bài (ý tưởng, các bước, lỗi hay gặp) kèm code Python, bộ test chấm tự động bằng Themis và bài giảng PowerPoint của chương này có trong bộ giáo trình Python đầy đủ.

Thầy cô và các em muốn mua bộ tài liệu đầy đủ vui lòng liên hệ tác giả Th.S Trần Huy Phúc:

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy