Xét một trò chơi có 6 viên bi, hai người thay phiên nhau nhặt từ 1 đến 3 viên. Người phải nhặt chỉ một viên bi cuối cùng thì bị thua. 1. 2. Vẽ toán bộ cây trò chơi Sử dụng kĩ thuật cắt tỉa alpha-beta định trị cho nút sẽ thắng trong trò chơi này nếu hai người đều đi những nước tốt nhất. Hãy cho một nhận xét về trường hợp tổng quát khi ban đầu có n viên bi và mỗi lần có thể nhặt từ 1 đến m viên. Bài 6: Xét một trò chơi. | Bài 5 Xét một trò chơi có 6 viên bi hai người thay phiên nhau nhặt từ 1 đến 3 viên. Người phải nhặt chỉ một viên bi cuối cùng thì bị thua. 1. Vẽ toán bộ cây trò chơi 2. Sử dụng kĩ thuật cắt tỉa alpha-beta định trị cho nút gốc 3. Ai sẽ thắng trong trò chơi này nếu hai người đều đi những nước tốt nhất. Hãy cho một nhận xét về trường hợp tổng quát khi ban đầu có n viên bi và mỗi lần có thể nhặt từ 1 đến m viên. Bài 6 Xét một trò chơi có 7 cái đĩa. Người chơi 1 chia thành 2 chồng có số đĩa không bằng nhau. Người chơi 2 chọn một chồng trong số các chồng có thể chia và tiếp tục chia thành hai chồng không bằng nhau. Hai người luân phiên nhau chia đĩa như vậy cho đến khi không thể chia được nữa thì thua. 1. Vẽ toàn bộ cây trò chơi. 2. Sử dụng kĩ thuật cắt tỉa alpha-beta định trị cho nút gốc 3. Ai sẽ thắng trong trò chơi này nếu hai người đều đi những nước tốt nhất. Bài 7 Cho bài toán cái ba lô với trọng lượng của ba lô W 30 và 5 loại đồ vật được cho trong bảng bên. Tất cả các loại đồ vật đều chỉ có một cái. 1. Giải bài toán bằng kỹ thuật Tham ăn Greedy . 2. Giải bài toán bằng kỹ thuật nhánh cận. Loại đồ vật Trọng lượng Giá trị A 15 30 B 10 25 C 2 2 D 4 6 E 8 24 Nguyễn Văn Linh Trang 84 Giải thuật CTDL và giải thuật lưu trữ ngoài CHƯƠNG 4 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI TỔNG QUAN Mục tiêu Sau khi học chương này sinh viên cần nắm được các vấn đề sau Tiêu chuẩn đế đánh giá giải thuật xử lý ngoài. Giải thuật sắp xếp trộn để sắp xếp ngoài và phương pháp cải tiến tốc độ sắp xếp trộn. Cách thức tổ chức lưu trữ và các giải thuật tìm kiếm xen xoá thông tin trên các tập tin tuần tự tập tin chỉ mục tập tin bảng băm và đặc biệt là tập tin B-cây. Kiến thức cơ bản cần thiết Cấu trúc dữ liệu danh sách liên kết. Các cấu trúc dữ liệu cây và bảng băm. Vấn đề tìm kiếm tuần tự và tìm kiếm nhị phân. Các thao tác trên kiểu dữ liệu tập tin. Tài liệu tham khảo . Aho . Hopcroft . Ullman Data Structures and Algorithms Addison-Wesley 1983. Chapter 10 . .
