Các Thuật Toán Cơ Bản Về Mảng Hai Chiều - IViettech

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

Bài trước: Bài tập về mảng một chiều