Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan

1. Stub và driver Stub: Viết các prototype trước Viết dummy code để thử nghiệm Ví dụ: bool user says yes( ) { return(true); } Driver: Viết một chương trình nhỏ để kiểm tra Thư viện cá nhân: Gom các hàm dùng chung thành thư viện 11 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
2. Trò chơi Life Luật: Một ma trận các tế bào là sống hay chết Các tế bào lân cận được tính là tám ô xung quanh Quá trình tiến hoá áp dụng cho một trạng thái hiện tại Một tế bào sống là sống ở thế hệ kế nếu có 2 hoặc 3 tế bào sống lân cận và chết trong trường hợp khác Một tế bào đang chết sẽ sống ở thế hệ kế nếu nó có chính xác 3 tế bào sống lân cận, nếu không nó vẫn chết tiếp. Tất cả các tế bào được kiểm chứng cùng một lúc để quyết định trạng thái sống, chết ở thế hệ kế 12 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
3. Trò chơi Life – Ví dụ 13 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
4. Trò chơi Life – Thiết kế phương thức 14 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
5. Trò chơi Life – Thiết kế class const int maxrow = 20 const maxcol = 60; class Life { public: void initialize( ); void print( ); void update( ); private: int grid[maxrow][maxcol]; int neighbor_count(int row, int col); }; 15 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
6. Trò chơi Life – Đếm số tế bào sống lân cận Mã C++: count = 0 for (i = row − 1; i <= row + 1; i++) for (j = col − 1; j <= col + 1; j++) count += grid[i][j]; count −= grid[row][col]; Sai chỗ nào? Nếu như row hoặc col là ngay các biên của array Các giá trị của các tế bào không là 1 hoặc 0 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
7. Trò chơi Life – Thay đổi thiết kế Giải pháp: Thêm vào 2 cột và 2 hàng giả có giá trị luôn là 0 Khai báo dữ liệu: grid[maxrow + 2][maxcol + 2] 17 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
8. Trò chơi Life – Giải thuật cập nhật Algorithm Update Input: một trạng thái sống Output: trạng thái của thế hệ kế tiếp 1. Khai báo một grid mới 2. Duyệt qua toàn bộ tế bào của trạng thái hiện tại 2.1. Đếm số tế bào sống xung quanh ô hiện tại 2.2. Nếu là 2 thì trạng thái mới chính là trạng thái cũ 2.3. Nếu là 3 thì trạng thái mới là sống 2.4. Ngược lại là chết 3. Cập nhật grid mới vào trong grid cũ End Update 18 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
9. Trò chơi Life – Mã C++ cập nhật void Life::update() /* Pre: grid đang chứa một trạng thái của thực thể sống Post: grid sẽ chứa trạng thái tiến hóa mới của thực thể sống này */ { int row, col; int new_grid[maxrow + 2][maxcol + 2]; //Chứa trạng thái mới vào đây for (row = 1; row <= maxrow; row++) for (col = 1; col <= maxcol; col++) switch (neighbor_count(row, col)) { case 2: //Trạng thái của tế bào không đổi new_grid[row][col] = grid[row][col]; break; case 3: //Tế bào sẽ sống new_grid[row][col] = 1; break; default: //Tế bào sẽ chết new_grid[row][col] = 0; } for (row = 1; row <= maxrow; row++) for (col = 1; col <= maxcol; col++) grid[row][col] = new_grid[row][col]; //Cập nhật các tế bào cùng lúc } 19 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan
10. Kết luận Sự liên quan giữa CTDL và giải thuật: Cấu trúc dữ liệu cụ thể: chọn giải thuật Giải thuật cụ thể: chọn cấu trúc dữ liệu Cấu trúc dữ liệu trừu tượng: Dữ liệu cụ thể bên trong Các phương thức: interface ra bên ngoài Thích hợp cho phương pháp hướng đối tượng 20 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan