Bài giảng Nhập môn lập trình - Bài 7: Mảng đa chiều - Ngô Hữu Dũng
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn lập trình - Bài 7: Mảng đa 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:
- bai_giang_nhap_mon_lap_trinh_bai_7_mang_da_chieu_ngo_huu_dun.pdf
Nội dung text: Bài giảng Nhập môn lập trình - Bài 7: Mảng đa chiều - Ngô Hữu Dũng
- TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Nhập môn lập trình Mảng đa chiều TS. Ngô Hữu Dũng
- Nội dung Mảng hai chiều Vòng lặp lồng nhau 0 1 n-1 0 n-1 0 0 Am,n An m-1 n-1 2 Nhập môn lập trình - Mảng đa chiều
- 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 3 Nhập môn lập trình - Mảng đa chiều
- 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 4 Nhập môn lập trình - Mảng đa chiều
- 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 [ ][ ]; ; , ; 5 Nhập môn lập trình - Mảng đa chiều
- 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; 6 Nhập môn lập trình - Mảng đa chiều
- 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] 7 Nhập môn lập trình - Mảng đa chiều
- 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]; 8 Nhập môn lập trình - Mảng đa chiều
- 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[][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]); 9 Nhập môn lập trình - Mảng đa chiều
- 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); } 10 Nhập môn lập trình - Mảng đa chiều
- 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 11 Nhập môn lập trình - Mảng đa chiều
- 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. 12 Nhập môn lập trình - Mảng đa chiều
- 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; } 13 Nhập môn lập trình - Mảng đa chiều
- 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]. 14 Nhập môn lập trình - Mảng đa chiều
- 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.} 15 Nhập môn lập trình - Mảng đa chiều
- 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 đó. 16 Nhập môn lập trình - Mảng đa chiều
- 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.} 17 Nhập môn lập trình - Mảng đa chiều
- 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). 18 Nhập môn lập trình - Mảng đa chiều
- 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. } 19 Nhập môn lập trình - Mảng đa chiều
- 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ố. 20 Nhập môn lập trình - Mảng đa chiều
- 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.} 21 Nhập môn lập trình - Mảng đa chiều
- 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.} 22 Nhập môn lập trình - Mảng đa chiều
- 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. } 23 Nhập môn lập trình - Mảng đa chiều
- 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. 24 Nhập môn lập trình - Mảng đa chiều
- 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. } 25 Nhập môn lập trình - Mảng đa chiều
- 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. } 26 Nhập môn lập trình - Mảng đa chiều
- 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. } 27 Nhập môn lập trình - Mảng đa chiều
- 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.} 28 Nhập môn lập trình - Mảng đa chiều
- 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.} 29 Nhập môn lập trình - Mảng đa chiều
- 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. } 30 Nhập môn lập trình - Mảng đa chiều
- 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. 31 Nhập môn lập trình - Mảng đa chiều
- 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.} 32 Nhập môn lập trình - Mảng đa chiều