Mảng hai chiều, thường thể hiện là một bảng số, trong toán học được gọi là ma trận. Ngoài ra, mảng hai chiều cũng được xem là mảng một chiều mà mỗi phần tử là một mảng một chiều.
Ví dụ: Đây là một bảng dữ liệu 2 chiều có 2 dòng và 2 cột
Khai báo: a[2][2] = {{4,5},{7,9}}
Một mảng có 4 hàng, 3 cột
Khai báo: a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}}
Truy xuất đến một phần tử:
a[0][0]: là phần tử đầu tiên
a[2][3] là phần tử giao nhau giữa dòng thứ 3 và cột thứ 4
Các bài toán duyệt mảng hai chiều bạn sẽ thấy rõ trong các trò chơi đánh cờ, bảng tính Excel v.v.v.
Các bài toán phổ biến trên mảng hai chiều như sau:
- Tìm một phần tử trong mảng
- Tìm phần tử lớn nhất, nhỏ nhất
- Tính tổng tất cả các phần tử trong mảng
- Đổ dữ liệu sang mảng một chiều và ngược lại
Đây là các bài toán thường gặp, với hi vọng sẽ giúp bạn tự tin hơn khi làm việc với mảng một chiều.
Yêu cầu
Viết chương trình khởi tạo một mảng hai chiều có n hàng, m cột với các phần tử là số nguyên, sau đó nhập vào một phần tử x nào đó và kiểm tra xem phần tử x đã có trong mảng hay chưa?
Phân tích và tìm cách giải
- Đầu vào: mảng các phần tử a[2,3] ={{3,7,9},{2,4,1}}, giá trị x
- Đầu ra: In ra thông báo x có trong mảng hay chưa?
- Phân tích:
- Cần duyệt qua các phần tử của mảng, rồi so sánh x và các giá trị trong mảng.
- Nếu xuất hiện thì thông báo tìm thấy và dừng
Các bước thực hiện:
Khởi tạo mảng a[], khởi tại biến cờ found = false (chưa tìm thấy)
Nhập vào giá trị x
Cho lặp biến i từ 0 đến n-1, với n là số hàng
Lặp biên j từ 0 đến m-1, với m số cột
Nếu x=a[i][j]
Dựng cờ đã tìm thấy found=true
Dừng vòng lặp / Việc dừng vòng lặp không cần thiết sẽ giúp tăng hiệu năng của thuật toán.
Căn cứ vào kết quả biến found để thông báo kết quả có tìm thấy hay không
Cách biểu diễn thuật toán
Trong trường hợp này, tôi sử dụng ngôn ngữ giả.
Declare int a[2,3] ={{3,7,9},{2,4,1}},x, i,j, n,m
boolean found=false
Input x
n= a.lengh
m=a[0].lengh
Loop i=0 to n-1
Loop j=0 to m-1
If(x=a[i][j])
found = true
Break //Thoát khỏi vòng lặp
If (found)
Print ‘X có trong mảng’
Else
Print ‘X không có trong mảng’
Kết quả Dry Run của mảng này như sau
Các thuật toán tính tổng tương tự như bài toán tính tổng n số tự nhiên. Bài toán tìm giá trị lớn nhất, nhỏ nhất tương tự mảng một chiều. Các bạn hãy tự thực hiện.
Bài tiếp: Thuật toán đổ dữ liệu về mảng một chiều và ngược lại
