tailieunhanh - Cẩm nang thuật toán tập 2 part 2

Tham khảo tài liệu 'cẩm nang thuật toán tập 2 part 2', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | .V KHT QUÀ THỰC HIỆN BÀI TẬP - . . . 1. Giả sử bạn dã biết trước bíio ĩôi của một tập điểm là hỉnh tam giác. Tìm một thuật toán để xác định nhanh chóng tam giác này. Tương tự tìm bao tòi nếu biết trước nó là một tứ giác. 2. Tìm một phương pháp hiệu quả để xác định xem một điểm có nhm trong một đa giác tôi hay không. 3. Hoàn thiện thuật toán tìm bao tôi giống như thuật toán sắp xếp chèn dùng phương pháp của bọn trong bài tập trước. 4. Trong quét Graham có thật sự cân thiết tót đâu từ một điểm được biết chác là ỡ trên bao Giải thích tại sao có tại sao không. 5. Trong phương pháp bọc-gói có thật sự càn thiết bắt đâu từ một điểm được biết chắc là ở trôn bao Giâi thích tại sao có tại sao không. 6. Tìm một tập diem sao cho phương pháp quét Graham tim bao ĩôi mất hiệu qua. 7. Phương pháp quét Graham có tìm được bao Tôi của một tập điểm tạo ra các đỉnh của một đa giác đơn 1 lất kỳ không Giải thích tại sao và cho một phan ví dụ chứng tỏ tụi sao không. 8. Tìm 4 điếm để dùng cho phương pháp loại tó phân trong nếu tập điểm được cho lã phân Ixí ngầu nhiên trôn hình tròn. 9. So sánh theo kinh nghiệm phương pháp quét Graham và phương pháp bọc gói cho một tập nhiêu điểm với các toạ độ X y trong khoang 0 đến 100. 10. Cài đặt phương pháp khử phán trong và xác định theo kỉnh nghiệm N nên lớn bao nhiêu để loại được khoảng 50 điểm khi dùng phương pháp này trôn tập điểm với X và y xấp xỉ nhau trong khoáng 0 và 100. 26 TÌM THEO KHOẢNG Cho một tập điểm trong mặt phảng một câu hòi tự nhièn là tìm các điểm rơi trong một vùng đã cho nào đó. Liệt kê tất câ các thành phố trong phạm vi 50 dặm kể từ Princeton là một câu hỏi thuộc loại này với tập điểm là các thành phố trên bân đò Mỹ. Khi dạng hình học của vùng tìm được giói hạn là hình chữ nhụt vấn đê này dễ dàng được mồ rộng cho các bài toán kh ng hình học. Ví dụ Liệt kê những người từ 21 đến 25 tuổi với thu nhập từ G0000 đến 100000 tìm những điểm trong tập tin dữ liệu chứa tên-tuổi-thu nhập rơi trong mặt phÃng tuổi-thu nhập. Viộc mô rộng ngay