›
›

Bài giảng Phương pháp lập trình - Bài 7: Mảng hai chiều - Ngô Hữu Dũng

pdf 33 trang ngocly 3240
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phương pháp lập trình - Bài 7: Mảng hai chiều - Ngô Hữu Dũng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_phuong_phap_lap_trinh_bai_7_mang_hai_chieu_ngo_huu.pdf

Nội dung text: Bài giảng Phương pháp lập trình - Bài 7: Mảng hai chiều - Ngô Hữu Dũng

  1. TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Phương pháp lập trình Mảng hai chiều TS. Ngô Hữu Dũng
  2. Nội dung  Mảng hai chiều  Vòng lặp lồng nhau Phương pháp lập trình - Mảng hai chiều
  3. Ma Trận 0 1 n-1 0 n-1 0 0 Am,n An m-1 n-1 Phương pháp lập trình - Mảng hai chiều
  4. Ma Trận 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 Phương pháp lập trình - Mảng hai chiều
  5. Khai báo kiểu mảng 2 chiều  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 Phương pháp lập trình - Mảng hai chiều
  6. Khai báo biến mảng 2 chiều  Cú pháp  Tường minh [ ][ ];  Không tường minh (thông qua kiểu) typedef [ ][ ]; ; , ; Phương pháp lập trình - Mảng hai chiều
  7. Khai báo biến mảng 2 chiều  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; Phương pháp lập trình - Mảng hai chiều
  8. Truy xuất đến một phần tử  Thông qua chỉ số [ ][ ]  Ví dụ  Cho mảng 2 chiều như sau 0 1 2 3 int a[3][4]; 0  Các truy xuất 1  Hợp lệ: a[0][0], a[0][1], , a[2][2], a[2][3] 2  Không hợp lệ: a[-1][0], a[2][4], a[3][3] Phương pháp lập trình - Mảng hai chiều
  9. Gán dữ liệu kiểu mảng  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ử = ; //sai [ ][giá trị cs2] = ;  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]; Phương pháp lập trình - Mảng hai chiều
  10. Truyền mảng cho hàm  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]); Phương pháp lập trình - Mảng hai chiều
  11. Truyền mảng cho hàm  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); } Phương pháp lập trình - Mảng hai chiều
  12. Một số bài toán cơ bản  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  Phương pháp lập trình - Mảng hai chiều
  13. Một số quy ước  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. Phương pháp lập trình - Mảng hai chiều
  14. Thủ tục HoanVi & Hàm LaSNT void HoanVi(int &x, int &y){ int tam = x; x = y; y = tam; } bool LaSNT(int n){ int i=2; while(i<n){ if(n%i==0) break; else i++; } if(i==n) return true; return false; } Phương pháp lập trình - Mảng hai chiều
  15. Nhập Ma Trận  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]. Phương pháp lập trình - Mảng hai chiều
  16. Hàm Nhập Ma Trận 1. void NhapMaTran(int a[][MAXC], int &m, int &n) 2. { 3. printf(“Nhap so dong, so cot cua ma tran: ”); 4. scanf(“%d%d”, &m, &n); 5. int i, j; 6. for (i=0; i<m; i++) 7. for (j=0; j<n; j++) 8. { 9. printf(“Nhap a[%d][%d]: ”, i, j); 10. scanf(“%d”, &a[i][j]); 11. } 12.} Phương pháp lập trình - Mảng hai chiều
  17. Xuất Ma Trận  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 đó. Phương pháp lập trình - Mảng hai chiều
  18. Hàm Xuất Ma Trận 1. void XuatMaTran(int a[][MAXC], int m, int n) 2. { 3. int i, j; 4. for (i=0; i<m; i++) 5. { 6. for (j=0; j<n; j++) 7. printf(“%d ”, a[i][j]); 8. printf(“\n”); 9. } 10.} Phương pháp lập trình - Mảng hai chiều
  19. Tìm kiếm một phần tử trong Ma Trận  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). Phương pháp lập trình - Mảng hai chiều
  20. Hàm Tìm Kiếm 1. int TimKiem(int a[][MAXC], int m, int n, int x) 2. { 3. int i, j; 4. for (i=0; i<m; i++) 5. for (j=0; j<n; j++) 6. if (a[i][j] == x) 7. return 1; 8. return 0; 9. } Phương pháp lập trình - Mảng hai chiều
  21. Kiểm tra tính chất của mảng  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ố. Phương pháp lập trình - Mảng hai chiều
  22. Hàm Kiểm Tra (Cách 1) 1. int KiemTra_C1(int a[][MAXC], int m, int n) 2. { 3. int i, j, dem = 0; 4. for (i=0; i<m; i++) 5. for (j=0; j<n; j++) 6. if (LaSNT(a[i][j]==1) 7. dem++; 8. if (dem == m*n) 9. return 1; 10. return 0; 11.} Phương pháp lập trình - Mảng hai chiều
  23. Hàm Kiểm Tra (Cách 2) 1. int KiemTra_C2(int a[][MAXC], int m, int n) 2. { 3. int i, j, dem = 0; 4. for (i=0; i<m; i++) 5. for (j=0; j<n; j++) 6. if (LaSNT(a[i][j]==0) 7. dem++; 8. if (dem == 0) 9. return 1; 10. return 0; 11.} Phương pháp lập trình - Mảng hai chiều
  24. Hàm Kiểm Tra (Cách 2) 1. int KiemTra_C3(int a[][MAXC], int m, int n) 2. { 3. int i, j, dem = 0; 4. for (i=0; i<m; i++) 5. for (j=0; j<n; j++) 6. if (LaSNT(a[i][j]==0) 7. return 0; 8. return 1; 9. } Phương pháp lập trình - Mảng hai chiều
  25. Tính tổng các phần tử  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. Phương pháp lập trình - Mảng hai chiều
  26. Hàm tính tổng trên dòng 1. int TongDong(int a[][MAXC], int m, int n, int d) 2. { 3. int j, tong; 4. tong = 0; 5. for (j=0; j<n; j++) // Duyệt các cột 6. tong = tong + a[d][j]; 7. return tong; 8. } Phương pháp lập trình - Mảng hai chiều
  27. Hàm tính tổng trên cột 1. int TongCot(int a[][MAXC], int m, int c) 2. { 3. int i, tong; 4. tong = 0; 5. for (i=0; i<m; i++) // Duyệt các dòng 6. tong = tong + a[i][c]; 7. return tong; 8. } Phương pháp lập trình - Mảng hai chiều
  28. Hàm tính tổng đường chéo chính 1. int TongDCChinh(int a[][MAXC], int n) 2. { 3. int i, tong; 4. tong = 0; 5. for (i=0; i<n; i++) 6. tong = tong + a[i][i]; 7. return tong; 8. } Phương pháp lập trình - Mảng hai chiều
  29. Hàm tính tổng trên đường chéo chính 1. int TongTrenDCChinh(int a[][MAXC], int n) 2. { 3. int i, j, tong; 4. tong = 0; 5. for (i=0; i<n; i++) 6. for (j=0; j<n; j++) 7. if (i < j) 8. tong = tong + a[i][j]; 9. return tong; 10.} Phương pháp lập trình - Mảng hai chiều
  30. Hàm tính tổng dưới đường chéo chính 1. int TongTrenDCChinh(int a[][MAXC], int n) 2. { 3. int i, j, tong; 4. tong = 0; 5. for (i=0; i j) 8. tong = tong + a[i][j]; 9. return tong; 10.} Phương pháp lập trình - Mảng hai chiều
  31. Hàm tính tổng trên đường chéo phụ 1. int TongDCPhu(int a[][MAXC], int n) 2. { 3. int i, tong; 4. tong = 0; 5. for (i=0; i<n; i++) 6. tong = tong + a[i][n-i-1]; 7. return tong; 8. } Phương pháp lập trình - Mảng hai chiều
  32. Tìm giá trị lớn nhất của Ma Trận  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. Phương pháp lập trình - Mảng hai chiều
  33. Hàm tìm Max 1. int TimMax(int a[][MAXC], int m, int n) 2. { 3. int i, j, max; 4. max = a[0][0]; 5. for (i=0; i max) 8. max = a[i][j]; 9. return max; 10.} Phương pháp lập trình - Mảng hai chiều