BÀI TẬP CHƯƠNG 3 Bài 1: Giả sử có hai đội A và B tham gia một trận thi đấu thể thao, đội nào thắng trước n hiệp thì sẽ thắng cuộc. Chẳng hạn một trận thi đấu bóng chuyền 5 hiệp, đội nào thắng trước 3 hiệp thì sẽ tháng cuộc. Giả sử hai đội ngang tài ngang sức. Đội A cần thắng thêm i hiệp để thắng cuộc còn đội B thì cần thắng thêm j hiệp nữa. Gọi P(i,j) là xác suất để đội A cần i hiệp nữa để chiến thắng, B cần j hiệp. Dĩ. | Giải thuật Kĩ thuật thiết kế giải thuật BÀI TẬP CHƯƠNG 3 Bài 1 Giả sử có hai đội A và B tham gia một trận thi đấu thể thao đội nào thắng trước n hiệp thì sẽ thắng cuộc. Chẳng hạn một trận thi đấu bóng chuyền 5 hiệp đội nào thắng trước 3 hiệp thì sẽ tháng cuộc. Giả sử hai đội ngang tài ngang sức. Đội A cần thắng thêm i hiệp để thắng cuộc còn đội B thì cần thắng thêm j hiệp nữa. Gọi P i j là xác suất để đội A cần i hiệp nữa để chiến thắng B cần j hiệp. Dĩ nhiên i j đều là các số nguyên không âm. Để tính P i j ta thấy rằng nếu i 0 tức là đội A đã thắng nên P 0 j 1. Tương tự nếu j 0 tức là đội B đã thắng nên P i 0 0. Nếu i và j đều lớn hơn không thì ít nhất còn một hiệp nữa phải đấu và hai đội có khả năng 5 ăn 5 thua trong hiệp này. Như vậy P i j là trung bình cộng của P i-1 j và P i j-1 . Trong đó P i-1 j là xác suất để đội A thắng cuộc nếu nó thắng hiệp đó và P i j-1 là xác suất để A thắng cuộc nếu nó thua hiệp đó. Tóm lại ta có công thức tính P i j như sau P i j 1 Nếu i 0 P i j 0 Nếu j 0 P i j P i-1 j P i j-1 2 Nếu i 0 và j 0 1. Viết một hàm đệ quy để tính P i j . Tính độ phức tạp của hàm đó. 2. Dùng kĩ thuật quy hoạch động để viết hàm tính P i j . Tính độ phức tạp của hàm đó. 3. Viết hàm P i j bằng kĩ thuật quy hoach động nhưng chỉ dùng mảng một chiều để tiết kiệm bộ nhớ . Bài 2 Bài toán phân công lao động Có n công nhân có thể làm n công việc. Công nhân i làm công việc j trong một khoảng thời gian tij. Phải tìm một phương án phân công như thế nào để các công việc đều được hoàn thành các công nhân đều có việc làm mỗi công nhân chỉ làm một công việc và mỗi công việc chỉ do một công nhân thực hiện đồng thời tổng thời gian là nhỏ nhất. 1. Mô tả kĩ thuật tham ăn greedy cho bài toán phân công lao động. 2. Tìm phương án theo giải thuật háu ăn cho bài toán phân công lao động được cho trong bảng sau. Trong đó mỗi dòng là một công nhân mỗi cột là một công Nguyễn Văn Linh Trang 82 Sưu tầm bởi Giải thuật Kĩ thuật thiết kế giải thuật việc ô i j ghi thời gian
