tailieunhanh - Toán học và Tin học

Tài liệu "Toán học và Tin học" trình bày về các bài toán ứng dụng trong tin học như bài toán xác định trọng tâm của một hình đa giác bất kỳ, bài toán về số Pi, bài toán mã đi tuần, phương pháp phân rã hình học để giải quyết bài toán trong tin học,. Để biết rõ hơn về nội dung chi tiết, . | TOÁN HỌC VÀ TIN HỌC 1. Phương pháp phân rã hình học Trong các kỳ thi Tin học lập trình, tỉ lệ xuất hiện bài toán về hình học là rất cao. Mà đó lại thường là những bài mà học sinh vấp váp, vì một trong các lý do sau đây: - Thuật giải quá khó, không nghĩ ra. - Nghĩ ra được thuật giải, nhưng không cài đặt được vì quá phức tạp. - Thuật giải tốt, cài đặt xong, nhưng vẫn không ổn do những lỗi nho nhỏ tinh vi và khó tránh. Trong bài viết này, tôi xin được trình bày về một phương pháp có thể áp dụng cho một lớp rất lớn các bài toán tin có nội dung hình học: đó là phân rã bài toán ban đầu ra, đưa nó về một vài mô hình thật là đơn giản và cài đặt chỉ cần trình độ trung bình khá là ổn. Nội dung chính của phương pháp này mà tôi muốn nói cùng các bạn là: - Coi một góc là tập hợp vi phân các góc nhỏ liên tiếp. (1) - Coi một bao hình là một tập hợp vi phân các điểm liên tiếp. (2) Tất nhiên từ “vi phân” ở đây chỉ mang tính hình tượng, tức là một số vừa đủ lớn các góc vi phân, hay các điểm vi phân để cho (1) và (2) có thể coi như là đúng. Chúng ta sẽ đưa vấn đề đi cụ thể hơn sau khi phân tích một số bài tin sau đây: 1. Diện tích trong tam giác (Problem G - The 2004 ACM Asia Programming Contest - Beijing): Cho một tam giác và một vòng dây kín có độ dài biết trước. Hãy dùng vòng dây đó để khoanh một vùng kín nằm gọn trong tam giác sao cho diện tích phần thu được là lớn nhất. Input: Gồm nhiều bộ test, mỗi bộ gồm đúng bốn số dương được viết trên cùng một dọ̀ng. Ba số đầu tiên là độ dài ba cạnh của tam giác, số cuối cùng là chu vi vòng dây. Độ dài các cạnh của mảnh vườn không quá 100. Độ dài vòng dây không lớn hơn chu vi tam giác. Output: Gồm nhiều dọ̀ng, mỗi dọ̀ng ứng với một dọ̀ng trong input, chỉ ghi một số là diện tích lớn nhất có thể được, làm trọ̀n với đúng hai chữ số sau dấu thập phân Ví dụ: Input: Output: Có thể không khó khăn lắm để nhận ra được thuật .