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 a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `0 a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `1

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ả.

` a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `2

` a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `3

` a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `4

` a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `5

` a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `6

` a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `7

` a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `8

` a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}} `9

`a[0][0]`0

`a[0][0]`1

`a[0][0]`2

`a[0][0]`3

`a[0][0]`4

`a[0][0]`5

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.

## Cơ bản nhất Trong C++, sắp xếp một mảng là một hoạt động phổ biến để xếp các phần tử trong mảng theo một thứ tự cụ thể. C++ cung cấp một hàm tích hợp sẵn gọi là `std::sort` trong thư viện `algorithm` giúp chúng ta dễ dàng thực hiện việc này. **Cú pháp:** ```cpp

include std::sort(start_iterator, end_iterator); ``` Trong đó: - `start_iterator`: Con trỏ hoặc iterator trỏ đến phần tử đầu tiên của mảng hoặc dãy cần sắp xếp. - `end_iterator`: Con trỏ hoặc iterator trỏ đến vị trí sau phần tử cuối cùng của mảng hoặc dãy cần sắp xếp. **Ví dụ:** ```cpp

include

include int main() { int arr[] = {5, 2, 8, 3, 1}; std::sort(arr, arr + 5); std::cout << "Mảng đã được sắp xếp: "; for (int i = 0; i < 5; ++i) { std::cout << arr[i] << " "; } return 0; } ``` **Kết quả:** ``` Mảng đã được sắp xếp: 1 2 3 5 8 ``` Trong ví dụ trên, chúng ta sử dụng hàm `std::sort` để sắp xếp mảng `arr` từ phần tử đầu tiên đến phần tử cuối cùng. Sau khi thực hiện sắp xếp, mảng `arr` đã được sắp xếp theo thứ tự tăng dần. **Lưu ý:** - Hàm `std::sort` sử dụng toán tử `<` mặc định để so sánh các phần tử trong mảng. Nếu bạn muốn sắp xếp theo thứ tự giảm dần hoặc tuỳ chỉnh thứ tự sắp xếp, bạn có thể sử dụng một hàm so sánh tùy chỉnh. - Đảm bảo thư viện `algorithm` được bao gồm bằng cách thêm `

include ` vào đầu chương trình. ## Kết hợp với hàm compare(so sánh) để tùy chỉnh cách sắp xếp. **Sắp xếp mảng trong C++ với hàm `std::sort` và hàm so sánh tùy chỉnh** Trong C++, hàm `std::sort` trong thư viện `algorithm` được sử dụng để sắp xếp một mảng các phần tử theo thứ tự tăng dần bằng mặc định. Tuy nhiên, có thể bạn muốn sắp xếp theo một tiêu chí riêng, chẳng hạn như sắp xếp giảm dần, sắp xếp dựa trên một trường hoặc thuộc tính cụ thể của đối tượng trong mảng. Để làm điều này, bạn có thể sử dụng hàm so sánh tùy chỉnh trong `std::sort`. **Cú pháp của hàm so sánh tùy chỉnh:** ```cpp bool compare(const T& a, const T& b) { // Trả về true nếu a đứng trước b trong thứ tự sắp xếp, ngược lại trả về false } ``` Trong đó: - `T` là kiểu dữ liệu của các phần tử trong mảng cần sắp xếp. - `a` và `b` là hai phần tử cần so sánh để xác định thứ tự sắp xếp. **Ví dụ về sắp xếp mảng các số nguyên giảm dần:** ```cpp

include

include bool compare(int a, int b) { return a > b; // Sắp xếp giảm dần } int main() { int arr[] = {5, 2, 8, 3, 1}; std::sort(arr, arr + 5, compare); std::cout << "Mảng đã được sắp xếp giảm dần: "; for (int i = 0; i < 5; i) { std::cout << arr[i] << " "; } return 0; } ``` **Kết quả:** ``` Mảng đã được sắp xếp giảm dần: 8 5 3 2 1 ``` Trong ví dụ này, chúng ta đã định nghĩa hàm so sánh tùy chỉnh `compare` để sắp xếp mảng `arr` giảm dần thay vì tăng dần như mặc định. Khi gọi hàm `std::sort`, chúng ta truyền hàm so sánh tùy chỉnh `compare` làm đối số thứ ba. **Lưu ý:** - Nếu bạn không cần sắp xếp theo tiêu chí riêng, chỉ cần sắp xếp tăng dần, bạn có thể bỏ qua hàm so sánh tùy chỉnh trong `std::sort`, vì mặc định nó sẽ sắp xếp tăng dần. - Hàm so sánh tùy chỉnh có thể được sử dụng cho một loạt các kiểu dữ liệu, không chỉ giới hạn trong trường hợp sắp xếp mảng số nguyên như ví dụ trên. ## Hàm reverse() ```cpp ## Hàm `reverse` trong C - Đảo ngược mảng sử dụng `algorithm` Trong ngôn ngữ lập trình C++, thư viện `algorithm` cung cấp hàm `reverse`, cho phép chúng ta đảo ngược thứ tự các phần tử trong mảng một cách thuận tiện. Điều này giúp chúng ta không cần phải tự triển khai hàm `reverse`, mà chỉ cần sử dụng hàm đã được xây dựng sẵn. Dưới đây là cách sử dụng hàm `reverse` trong C++: ```cpp

include

include // Thư viện chứa hàm reverse int main() { int arr[] = {1, 2, 3, 4, 5}; int size = sizeof(arr) / sizeof(arr[0]); std::cout << "Mảng trước khi đảo ngược: "; for (int i = 0; i < size; i++) { std::cout << arr[i] << " "; } // Sử dụng hàm reverse từ thư viện algorithm std::reverse(arr, arr + size); std::cout << "\nMảng sau khi đảo ngược: "; for (int i = 0; i < size; i++) { std::cout << arr[i] << " "; } return 0; } ``` Kết quả đầu ra sẽ là: ``` Mảng trước khi đảo ngược: 1 2 3 4 5 Mảng sau khi đảo ngược: 5 4 3 2 1 ``` Hàm `reverse` từ thư viện `algorithm` được sử dụng để đảo ngược thứ tự các phần tử trong mảng `arr`. Ta chỉ cần truyền con trỏ đến phần tử đầu tiên và phần tử sau phần tử cuối cùng của mảng để thực hiện đảo ngược. ## Sử dụng sort() với các kiểu dữ liệu theo bộ. (pair - bộ 2) ### Giới thiệu kiểu dữ liệu pair (bộ 2) **Giới thiệu kiểu dữ liệu `std::pair` trong C++** Trong C++, `std::pair` là một lớp template trong thư viện chuẩn (``) được sử dụng để lưu trữ cặp giá trị có kiểu dữ liệu khác nhau. Một `std::pair` bao gồm hai thành phần: `first` và `second`, mỗi thành phần có thể là bất kỳ kiểu dữ liệu nào. **Cú pháp khai báo một `std::pair`:** ```cpp std::pair variable_name; ``` Trong đó: - `type1` và `type2` là hai kiểu dữ liệu tùy chỉnh cho hai thành phần của cặp. - `variable_name` là tên của biến `std::pair` bạn muốn tạo. **Ví dụ sử dụng `std::pair` để lưu trữ thông tin sinh viên:** ```cpp

include

include int main() { std::pair student; // Định nghĩa một std::pair lưu trữ thông tin sinh viên student.first = "John"; // Thành phần first lưu tên sinh viên (kiểu std::string) student.second = 20; // Thành phần second lưu tuổi của sinh viên (kiểu int) std::cout << "Tên sinh viên: " << student.first << std::endl; std::cout << "Tuổi sinh viên: " << student.second << std::endl; return 0; } ``` **Kết quả:** ``` Tên sinh viên: John Tuổi sinh viên: 20 ``` Trong ví dụ này, chúng ta đã sử dụng `std::pair` để lưu trữ thông tin sinh viên, trong đó thành phần `first` lưu tên sinh viên kiểu `std::string`, và thành phần `second` lưu tuổi của sinh viên kiểu `int`. **Lợi ích của `std::pair`:** - `std::pair` cho phép lưu trữ hai giá trị có kiểu dữ liệu khác nhau trong một cặp, giúp quản lý dữ liệu dễ dàng hơn khi chúng liên quan tới nhau. - Được sử dụng rộng rãi trong các tình huống cần lưu trữ các cặp thông tin, chẳng hạn như các cặp tọa độ, thông tin đối tượng, hoặc giá trị và chỉ số tương ứng. **Lưu ý:** - Để sử dụng `std::pair`, bạn cần bao gồm thư viện `` trong chương trình C++ của mình. - Ngoài `std::pair`, thư viện `` còn cung cấp nhiều lớp và hàm hữu ích khác, chẳng hạn như `std::make_pair` để tạo một `std::pair` một cách thuận tiện hơn. ### Sử dụng sort() trên mảng có kiểu dữ liệu bộ 2 **Sắp xếp mảng các `pair` trong C++** Trong C++, để sắp xếp một mảng các `pair`, chúng ta sử dụng hàm tích hợp sẵn `std::sort` từ thư viện `algorithm`. Ngoài ra, chúng ta sử dụng thư viện `utility` để sử dụng lớp `std::pair`, giúp lưu trữ các cặp giá trị có kiểu dữ liệu khác nhau. **1. Gọi thư viện `algorithm` và `utility`:** Thư viện `algorithm` cung cấp nhiều hàm tiện ích để thực hiện các thao tác liên quan đến các thuật toán như sắp xếp, tìm kiếm, xóa, hoán đổi, v.v. Trong ví dụ này, chúng ta sử dụng hàm `std::sort` để sắp xếp mảng. Thư viện `utility` cung cấp lớp `std::pair`, cho phép tạo các cặp giá trị. Lớp `std::pair` cho phép lưu trữ hai giá trị có kiểu dữ liệu khác nhau trong một cặp, điều này hữu ích khi muốn lưu trữ hai giá trị liên quan với nhau, như trong ví dụ này, chúng ta lưu trữ các cặp `(a, b)` trong mảng `arr`. **2. Giải thích chi tiết hơn về hàm `std::sort` và hàm `comparePairs`:** - `std::sort`: Đây là một hàm tích hợp sẵn trong thư viện `algorithm` của C++, dùng để sắp xếp các phần tử trong một dãy. Hàm này nhận vào ba tham số: con trỏ đến phần tử đầu tiên của dãy (bắt đầu), con trỏ đến phần tử sau phần tử cuối cùng của dãy (kết thúc), và một hàm so sánh tùy chỉnh (nếu cần). Hàm `std::sort` sẽ sắp xếp các phần tử trong dãy từ phần tử bắt đầu đến phần tử kết thúc bằng cách sử dụng hàm so sánh tùy chỉnh (nếu có) hoặc sử dụng toán tử `<` mặc định nếu không có hàm so sánh tùy chỉnh được cung cấp. Trong ví dụ này, chúng ta sắp xếp mảng `arr` từ phần tử đầu tiên đến phần tử cuối cùng, sử dụng hàm so sánh tùy chỉnh `comparePairs` để xác định thứ tự sắp xếp của các cặp. - `comparePairs`: Đây là hàm so sánh tùy chỉnh mà chúng ta định nghĩa để xác định thứ tự sắp xếp của các cặp trong mảng `arr`. Hàm này nhận vào hai tham số kiểu `const std::pair&` và trả về giá trị kiểu `bool`. Trong hàm `comparePairs`, chúng ta thực hiện logic so sánh tùy chỉnh để xác định thứ tự sắp xếp. Trong ví dụ này, chúng ta sắp xếp các cặp giảm dần theo phần tử đầu tiên của mỗi cặp. Hàm `comparePairs` so sánh hai phần tử `a.first` và `b.first`, nếu giá trị của `a.first` lớn hơn giá trị của `b.first`, thì trả về `true`, ngược lại trả về `false`. **Dưới đây là đoạn code hoàn chỉnh cho ví dụ trên:** ```cpp

include

include

include bool comparePairs(const std::pair& a, const std::pair& b) { return a.first > b.first; } int main() { const int n = 5; // Bạn có thể thay đổi giá trị 'n' ở đây std::pair arr[n] = {{1, 5}, {3, 2}, {2, 7}, {5, 1}, {4, 3}}; std::sort(arr, arr + n, comparePairs); std::cout << "Mảng các cặp đã được sắp xếp:" << std::endl; for (int i = 0; i < n; ++i) { std::cout << "(" << arr[i].first << ", " << arr[i].second << ")" << std::endl; } return 0; } ``` Khi chạy chương trình, bạn sẽ nhận được kết quả là các cặp đã được sắp xếp theo phần tử đầu tiên của mỗi cặp giảm dần. **Các kiểu dữ liệu như bộ 3 (tuple) hay các kiểu dữ liệu theo bộ khác được cài đặt tương tự nên sẽ không trình bày ở đây** ## Sắp xếp các kí tự trong một xâu ```cpp

include

include int main() { string str = "badc0713"; sort(str.begin(), str.end()); cout << str; // in ra 0137abcd return 0; } ```