Kĩ thuật lập trình - Mảng hai chiều

Nội dung text: Kĩ thuật lập trình - Mảng hai chiều

1. Trường Cao đẳng Kỹ thuật Công nghệ Đồng Nai Khoa Công nghệ thông tin NHẬP MÔN LẬP TRÌNH Phạm Đình Sắc dinhsac@gmail.com MẢNG HAI CHIỀU 1 && VCVC Nội dung BBBB 1 Khái niệm 2 Khai báo 3 Truy xuất dữ liệu kiểu mảng 4 Một số bài toán trên mảng 2 chiều NMLT - Mảng hai chiều 2
2. && VCVC Ma Trận BBBB 0 1 n-1 0 n-1 0 0 Am,n An m-1 n-1 NMLT - Mảng hai chiều 3 && VCVC Ma Trận BBBB 0 n-1 0 n-1 0 n-1 0 0 0 An n-1 n-1 n-1 dòng = cột dòng > cột dòng n-1 dòng + cột < n-1 NMLT - Mảng hai chiều 4
3. && VCVC Khai báo kiểu mảng 2 chiều BBBB Cú pháp typedef [ ][ ]; ể ơ ở ể . N1, N2: số lượng phần tử mỗi chiều Ví dụ typedef int MaTran[3][4]; 0 1 2 3 0 Kiểu MaTran 1 2 NMLT - Mảng hai chiều 5 && VCVC Khai báo biến mảng 2 chiều BBBB Cú pháp . Tường minh [ ][ ]; ể ơ ở ế . Không tường minh (thông qua kiểu) typedef [ ][ ]; ể ơ ở ể ; ể ế , ; ể ế ế NMLT - Mảng hai chiều 6
4. && VCVC Khai báo biến mảng 2 chiều BBBB Ví dụ . Tường minh int a[10][20], b[10][20]; int c[5][10]; int d[10][20]; . Không tường minh (thông qua kiểu) typedef int MaTran10x20[10][20]; typedef int MaTran5x10[5][10]; MaTran10x20 a, b; MaTran11x11 c; MaTran10x20 d; NMLT - Mảng hai chiều 7 && VCVC Truy xuất đến một phần tử BBBB Thông qua chỉ số [ ][ ] ế ả ị ị Ví dụ 0 1 2 3 . Cho mảng 2 chiều như sau 0 1 int a[3][4]; 2 . Các truy xuất • Hợp lệ: a[0][0], a[0][1], , a[2][2], a[2][3] • Không hợp lệ: a[-1][0], a[2][4], a[3][3] NMLT - Mảng hai chiều 8
5. && VCVC Gán dữ liệu kiểu mảng BBBB Không được sử dụng phép gán thông thường mà phải gán trực tiếp giữa các phần tử Ví dụ int a[5][10], b[5][10]; b = a; // Sai int i, j; for (i = 0; i < 5; i++) for (j = 0; j < 10; j++) b[i][j] = a[i][j]; NMLT - Mảng hai chiều 9 && VCVC Truyền mảng cho hàm BBBB Truyền mảng cho hàm . Tham số kiểu mảng trong khai báo hàm giống như khai báo biến mảng void NhapMaTran(int a[50][100]); . Tham số kiểu mảng truyền cho hàm chính là địa chỉ của phần tử đầu tiên của mảng • Có thể bỏ số lượng phần tử chiều thứ 2 hoặc con trỏ. • Mảng có thể thay đổi nội dung sau khi thực hiện hàm. void NhapMaTran(int a[][100]); void NhapMaTran(int (*a)[100]); NMLT - Mảng hai chiều 10
6. && VCVC Truyền mảng cho hàm BBBB Truyền mảng cho hàm . Số lượng phần tử thực sự truyền qua biến khác void XuatMaTran(int a[50][100], int m, int n); void XuatMaTran(int a[][100], int m, int n); void XuatMaTran(int (*a)[100], int m, int n); Lời gọi hàm void NhapMaTran(int a[][100], int &m, int &n); void XuatMaTran(int a[][100], int m, int n); void main() { int a[50][100], m, n; NhapMaTran(a, m, n); XuatMaTran(a, m, n); } NMLT - Mảng hai chiều 11 && VCVC Một số bài toán cơ bản BBBB Viết chương trình con thực hiện các yêu cầu sau . Nhập mảng . Xuất mảng . Tìm kiếm một phần tử trong mảng . Kiểm tra tính chất của mảng . Tính tổng các phần tử trên dòng/cột/toàn ma trận/đường chéo chính/nửa trên/nửa dưới . Tìm giá trị nhỏ nhất/lớn nhất của mảng . NMLT - Mảng hai chiều 12
7. && VCVC Một số quy ước BBBB Kiểu dữ liệu #define MAXD 50 #define MAXC 100 Các chương trình con . Hàm void HoanVi(int x, int y): hoán vị giá trị của hai số nguyên. . Hàm int LaSNT(int n): kiểm tra một số có phải là số nguyên tố. Trả về 1 nếu n là số nguyên tố, ngược lại trả về 0. NMLT - Mảng hai chiều 13 && VCVC Thủ tục HoanVi & Hàm LaSNT BBBB NMLT - Mảng hai chiều 14
8. && VCVC Nhập Ma Trận BBBB Yêu cầu . Cho phép nhập mảng a, m dòng, n cột Ý tưởng . Cho trước một mảng 2 chiều có dòng tối đa là MAXD, số cột tối đa là MAXC. . Nhập số lượng phần tử thực sự m, n của mỗi chiều. . Nhập từng phần tử từ [0][0] đến [m-1][n-1]. NMLT - Mảng hai chiều 15 && VCVC Hàm Nhập Ma Trận BBBB void NhapMaTran(int a[][MAXC], int &m, int &n) { printf( Nhap so dong, so cot cua ma tran: ); “ ” scanf( %d%d , &m, &n); “ ” int i, j; for (i=0; i<m; i++) for (j=0; j<n; j++) { printf( Nhap a[%d][%d]: , i, j); “ ” scanf( %d , &a[i][j]); “ ” } } NMLT - Mảng hai chiều 16
9. && VCVC Xuất Ma Trận BBBB Yêu cầu . Cho phép nhập mảng a, m dòng, n cột Ý tưởng . Xuất giá trị từng phần tử của mảng 2 chiều từ dòng có 0 đến dòng m-1, mỗi dòng xuất giá giá trị của cột 0 đến cột n-1 trên dòng đó. NMLT - Mảng hai chiều 17 && VCVC Hàm Xuất Ma Trận BBBB void XuatMaTran(int a[][MAXC], int m, int n) { int i, j; for (i=0; i<m; i++) { for (j=0; j<n; j++) printf( %d , a[i][j]); “ ” printf( \n ); “ ” } } NMLT - Mảng hai chiều 18
10. && VCVC Tìm kiếm một phần tử trong Ma Trận BBBB Yêu cầu . Tìm xem phần tử x có nằm trong ma trận a kích thước mxn hay không? Ý tưởng . Duyệt từng phần của ma trận a. Nếu phần tử đang xét bằng x thì trả về có (1), ngược lại trả về không có (0). NMLT - Mảng hai chiều 19 && VCVC Hàm Tìm Kiếm BBBB int TimKiem(int a[][MAXC], int m, int n, int x) { int i, j; for (i=0; i<m; i++) for (j=0; j<n; j++) if (a[i][j] == x) return 1; return 0; } NMLT - Mảng hai chiều 20
11. && VCVC Kiểm tra tính chất của mảng BBBB Yêu cầu . Cho trước ma trận a kích thước mxn. Ma trận a có phải là ma trậntoàn các số nguyên tố hay không? Ý tưởng . Cách 1: Đếm số lượng số ngtố của ma trận. Nếu số lượng này bằng đúng mxn thì ma trận toàn ngtố. . Cách 2: Đếm số lượng số không phải ngtố của ma trận. Nếu số lượng này bằng 0 thì ma trận toàn ngtố. . Cách 3: Tìm xem có phần tử nào không phải số ngtố không. Nếu có thì ma trận không toàn số ngtố. NMLT - Mảng hai chiều 21 && VCVC Hàm Kiểm Tra (Cách 1) BBBB int KiemTra_C1(int a[][MAXC], int m, int n) { int i, j, dem = 0; for (i=0; i<m; i++) for (j=0; j<n; j++) if (LaSNT(a[i][j]==1) dem++; if (dem == m*n) return 1; return 0; } NMLT - Mảng hai chiều 22
12. && VCVC Hàm Kiểm Tra (Cách 2) BBBB int KiemTra_C2(int a[][MAXC], int m, int n) { int i, j, dem = 0; for (i=0; i<m; i++) for (j=0; j<n; j++) if (LaSNT(a[i][j]==0) dem++; if (dem == 0) return 1; return 0; } NMLT - Mảng hai chiều 23 && VCVC Hàm Kiểm Tra (Cách 2) BBBB int KiemTra_C3(int a[][MAXC], int m, int n) { int i, j, dem = 0; for (i=0; i<m; i++) for (j=0; j<n; j++) if (LaSNT(a[i][j]==0) return 0; return 1; } NMLT - Mảng hai chiều 24
13. && VCVC Tính tổng các phần tử BBBB Yêu cầu . Cho trước ma trận a, kích thước mxn. Tính tổng các phần tử trên: • Dòng d, cột c • Đường chéo chính, đường chéo phụ (ma trận vuông) • Nửa trên/dưới đường chéo chính (ma trận vuông) • Nửa trên/dưới đường chéo phụ (ma trận vuông) Ý tưởng . Duyệt ma trận và cộng dồn các phần tử có tọa độ (dòng, cột) thỏa yêu cầu. NMLT - Mảng hai chiều 25 && VCVC Hàm tính tổng trên dòng BBBB int TongDong(int a[][MAXC], int m, int n, int d) { int j, tong; tong = 0; for (j=0; j<n; j++) // Duy t các c t ệ ộ tong = tong + a[d][j]; return tong; } NMLT - Mảng hai chiều 26
14. && VCVC Hàm tính tổng trên cột BBBB int TongCot(int a[][MAXC], int m, int c) { int i, tong; tong = 0; for (i=0; i<m; i++) // Duy t các dòng ệ tong = tong + a[i][c]; return tong; } NMLT - Mảng hai chiều 27 && VCVC Hàm tính tổng đường chéo chính BBBB int TongDCChinh(int a[][MAXC], int n) { int i, tong; tong = 0; for (i=0; i<n; i++) tong = tong + a[i][i]; return tong; } NMLT - Mảng hai chiều 28
15. && VCVC Hàm tính tổng trên đường chéo chính BBBB int TongTrenDCChinh(int a[][MAXC], int n) { int i, j, tong; tong = 0; for (i=0; i j) tong = tong + a[i][j]; return tong; } NMLT - Mảng hai chiều 30
16. && VCVC Hàm tính tổng trên đường chéo phụ BBBB int TongDCPhu(int a[][MAXC], int n) { int i, tong; tong = 0; for (i=0; i<n; i++) tong = tong + a[i][n-i-1]; return tong; } NMLT - Mảng hai chiều 31 && VCVC Tìm giá trị lớn nhất của Ma Trận BBBB Yêu cầu . Cho trước ma trận a, kích thước mxn. Tìm giá trị lớn nhất trong ma trận a (gọi là max) Ý tưởng . Giả sử giá trị max hiện tại là giá trị phần tử đầu tiên a[0][0] . Lần lượt kiểm tra các phần tử còn lại để cập nhật max. NMLT - Mảng hai chiều 32
17. && VCVC Hàm tìm Max BBBB int TimMax(int a[][MAXC], int m, int n) { int i, j, max; max = a[0][0]; for (i=0; i max) max = a[i][j]; return max; } NMLT - Mảng hai chiều 33