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

TOÁN HỌC VÀ TIN HỌC<br /> 1. Phương pháp phân rã hình học<br /> 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à<br /> đó 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:<br /> - Thuật giải quá khó, không nghĩ ra.<br /> - Nghĩ ra được thuật giải, nhưng không cài đặt được vì quá phức tạp.<br /> - 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à<br /> khó tránh.<br /> 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<br /> 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<br /> 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<br /> 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à:<br /> - Coi một góc là tập hợp vi phân các góc nhỏ liên tiếp. (1)<br /> - 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)<br /> 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<br /> góc vi phân, hay các điểm vi phân để cho (1) và (2) có thể coi như là đúng.<br /> 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:<br /> 1. Diện tích trong tam giác (Problem G - The 2004 ACM Asia Programming Contest<br /> - Beijing):<br /> <br /> 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 đó<br /> để 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à<br /> lớn nhất.<br /> <br /> 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<br /> 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.<br /> Độ 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<br /> vi tam giác.<br /> 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à<br /> 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<br /> Ví dụ:<br /> Input:<br /> 12.0000 23.0000 17.0000<br /> 40.0000<br /> 84.0000 35.0000 91.0000<br /> 210.0000<br /> 100.0000 100.0000 100.0000<br /> 181.3800<br /> Output:<br /> 89.35<br /> 1470.00<br /> 2618.00<br /> Có thể không khó khăn lắm để nhận ra được thuật giải của bài toán này như sau:<br /> Tìm O là giao ba đuờng phân giác của tam giác đó. Ta gọi R là bán kính đường tròn<br /> tâm O (bạn cứ coi là có R rồi). Phần diện tích tối ưu là phần mà vừa nằm trong<br /> đường tròn vừa nằm trong tam giác, đồng thời chu vi của phần diện tích đó đúng<br /> bằng L là chu vi vòng dây. Còn để tìm R thì ta chặt nhị phân.<br /> Chúng ta sẽ không bàn nhiều về thuật giải bài toán, cứ coi là bạn biết rồi đi. Vậy vấn<br /> đề là bạn sẽ cài đặt nó như thế nào? Quả thật rất khó để có thể hoàn thành bài này<br /> trong thời gian cho phép nếu như ta cứ cài đặt một cách thuần túy thông thường.<br /> Như vậy thì chẳng những mất thời gian mà hiệu quả đạt được còn là rất thấp.<br /> Sở dĩ bài này khó cài đặt là bởi vì ứng với mỗi R ta có rất nhiều trường hợp có thể<br /> xảy ra về vị trí tương đối của hình tròn (O) và tam giác ABC. Số điểm giao nhau có<br /> thể không có, có thể có một, có hai,..., hoặc có sáu giao điểm. Các giao điểm lại<br /> không xếp theo quy luật gì nên lúc thực sự tính toán lại nảy sinh nhiều vấn đề rất<br /> phức tạp, ví dụ như trên mỗi cạnh có mấy giao điểm? Điều này phải xác định rõ<br /> ràng, nếu không thì không thể tính được chu vi và diện tích của hình cần thiết. Tính<br /> sơ sơ ra số trường hợp cần xét cũng quá lớn và trong mỗi trường hợp cũng đủ rắc rối<br /> để cho ta có thể giải quyết bài này một cách nhanh gọn và chính xác (Tôi đã làm thử<br /> <br /> rồi). Vậy nếu đây là một bài thi quan trọng thì trong phòng thi liệu bạn có đủ bình<br /> tĩnh để làm một cách chính quy như trên? Tôi xin phát biểu phương án về cách phân<br /> rã bài toán này, để biến nó thành một bài toán đơn giản và rất dễ cài đặt, và từ đó<br /> tổng quát hóa lên một phương án tuyệt vời:<br /> Đầu tiên phải thấy được là cái khó chỉ là làm sao xác định rõ những giao điểm cần<br /> thiết. Gọi (T) là hình tạo bởi (0) và ABC ứng với R biết trước. Rõ ràng là (T) là một<br /> hình gồm có những phần đoạn thẳng (thuộc tam giác ABC) và những phần đường<br /> tròn (thuộc (O). Bây giờ ta không quan niệm (T) như vậy nữa, ta coi nó gần đúng là<br /> một đa giác (T') gồm rất nhiều điểm Mi, với 1 ≤ i ≤ P, với P bạn khai báo const ở<br /> đầu chương trình, P càng lớn càng tốt, nhưng không nên quá lớn vì chương trình sẽ<br /> chạy lâu hơn.<br /> Xác định các điểm Mi: Ta chia góc 3600 tại O ra làm P góc đều nhau. Ứng với góc<br /> thứ i đó ta vẽ một tia Oi, sau đó ta xác định xem tia Oi cắt hình tròn trước hay cắt<br /> tam giác trước. Michính là giao điểm gần O nhất trong hai giao điểm đó.<br /> Như vậy là thay vì phải tính toán với miền (T) vô cùng rắc rối, nếu ta coi nó như là<br /> một đa giác (T') gồm P đỉnh và xác định các điểm Mi dễ dàng như trên, thì công việc<br /> còn lại thật vô cùng đơn giản. Nhưng còn vấn đề sai số? Ta có thể khắc phục nó<br /> bằng một thủ thuật như sau:<br /> Đặt M0 = MP và MP+1 = M1. Xác định 6 điểm i mà góc giữa Mi-1, Mi, Mi+1 là<br /> lớn nhất. Đó chính là sáu giao điểm gần như thực sự của (T). Bây giờ ta tính toán<br /> trực tiếp trên (T) bằng cách dùng các công thức chính xác cho cung tròn và đoạn<br /> thẳng thì vấn đề sai số coi như không còn.<br /> <br /> Bạn thấy đó, cùng là một bài toán, nhưng nếu ta quan niệm nó khác đi một chút thì<br /> công việc sẽ được giảm tải đi rất nhiều lần. Không phải cứ cái gì tốt nhất về mặt lý<br /> thuyết cũng là tốt nhất với ta, nhất là trong các kỳ thi. Điều quan trọng là tính hiệu<br /> quả và thực tế của chương trình. Việc phân rã một hình (T) ra thành đa giác (T')<br /> cũng là điều thường gặp ở nhiều nơi, nhưng thủ thuật tách ra để rồi ghép lại thì quả<br /> là rất độc đáo. Thủ thuật này trong toán thường gặp khi phải tính tổng của một chuỗi<br /> số S, hay một chuỗi hàm f. Khi đó người ta hay vi phân vế trái, tính toán một hồi<br /> cho nó thật gọn rồi lại tích phân chính vế trái đó. Nếu như bạn để ý, về bản chất thì<br /> đó cũng là điều mà bài tin kia đã sử dụng, cho dù nó đã bị “tin hóa” đi bởi tham số<br /> P. Nhưng bạn cứ yên tâm, không có gì là tuyệt đối cả, nếu như P đủ lớn (khoảng vài<br /> nghìn) thì kết quả sẽ luôn ra tối ưu. Bài tin trên đã áp dụng cả (1) và (2) để giải<br /> quyết hiệu quả vấn đề. Có lẽ bạn vẫn chưa hình dung ra phương pháp này ra sao?<br /> Chúng ra hãy cùng bàn tiếp trong bài tiếp theo:<br /> 2. Chocolate<br /> Nhà máy sản xuất bánh kẹo Fishburg sản xuất ra một loại bánh chocolate hình đa<br /> giác lồi. Kiđy và Carlson mua một cái và họ muốn cắt nó ra làm hai phần bằng nhau<br /> với một nhát cắt có độ dài nhỏ nhất. Viết chương trình tìm độ dài nhỏ nhất để cắt<br /> miếng bánh sử dụng những gì bạn được cho biết về miếng bánh. Tổng số đỉnh N là<br /> một số nguyên (3 ≤ N ≤ 50). Tọa độ của các đỉnh là tập hợp các cặp số thực -100 ≤<br /> xi, yi≤100.<br /> Input: Dòng đầu của input file gồm số N - số lượng đỉnh của đa giác. N dòng sau<br /> gồm toạ độ của các đỉnh liên tiếp nhau của đa giác.<br /> Output: gồm độ dài nhỏ nhất của đường cắt chính xác đến 0,0001.<br /> Ví dụ:<br /> Input:<br /> 4<br /> 00<br /> 03<br /> 43<br /> 40<br /> Output:<br /> 3<br /> Thuật giải tốt của bài này theo tôi là không phù hợp để bàn ra ở đây vì cái lõi toán<br /> của nó nhiều quá. Nói chung để mà vừa nghĩ thuật giải tốt hẳn và cài đặt xong nó<br /> <br /> chắc cũng phải vất vả nhiều lắm mà cũng chẳng biết là liệu mình có kiểm soát được<br /> không nữa. Vậy chúng ta cùng bàn cách phân rã bài này ra cho nó đơn giản đi nhé.<br /> Cách đơn giản nhất ai cũng có thể nghĩ ra là coi như đa giác này là một tập hợp các<br /> điểm rời rạc, sau đó ta lấy hai trong số những điểm đó, rồi kiểm tra xem đoạn thẳng<br /> nối hai điểm này có chia đôi được đa giác hay không, nếu như được rồi thì cập nhật<br /> kết quả thôi. Cải tiến của cách này là chỉ chọn một điểm thôi, điểm còn lại thì chặt<br /> nhị phân. Cách này về tư tưởng phân rã thì là tốt nhưng trên thực tế không phải là<br /> không có vấn đề. Điều kiện các tọa độ của đa giác có trị tuyệt đối không quá 100<br /> cho nên sẽ vẫn có những test mà chu vi của nó sẽ khá là lớn (có thể lên tới hàng<br /> vạn). Mà theo như cách phân rã này thì độ sai số sẽ tỉ lệ theo chu vi của đa giác. Nếu<br /> chia đa giác thành P điểm, với độ phức tạp của cách này vượt quá Plog(P), thì rõ<br /> ràng muốn chạy nhanh được thì P không thể tới hàng vạn, cho nên khả năng chính<br /> xác tới nhiều chữ số sau dấu thập phân khi chu vi của đa giác quá lớn là điều không<br /> tưởng. Vậy (2) không dùng được ở đây.<br /> Cách thứ hai có thể khắc phục nhược điểm trên, là ta phân rã các góc ra thành vô số<br /> các góc nhỏ vi phân. Giả sử số góc là P, thì một góc sẽ có giá trị là dP = 3600/P.<br /> Chắc hẳn đọc đề bài lần đầu ai cũng tưởng tượng là đa giác thì đứng yên, còn đường<br /> thẳng chia đôi đa giác sẽ xiên xiên. Ta hãy tưởng tượng ngược lại một chút như sau:<br /> Đường thẳng chia đôi đa giác thì luôn nằm ngang, có thể tịnh tiến lên xuống, còn đa<br /> giác thì có thể xoay. Về bản chất thì vẫn không có gì thay đổi, nhưng nó sẽ giúp ích<br /> nhiều cho ta. Tóm lại thuật giải sẽ như sau:<br /> - Xoay đa giác đi một góc dP.<br /> - Chặt nhị phân để tịnh tiến đường thẳng nằm ngang sao cho nó chia đôi đa giác kia.<br /> Nếu không chia vừa thì bằng cách chặt nhị phân ta có thể tịnh tiến đường thẳng này<br /> lên xuống đến bao giờ bằng nhau thì thôi.<br /> - Sau khi đã chia đôi đa giác, cập nhật lại độ dài tốt nhất của nhát cắt. Sau khi xoay<br /> đi P lần, mỗi lần một góc dP thì đa giác sẽ quay về đúng vị trí ban đầu. Nếu như có<br /> bạn nào chưa biết công thức xoay hình, tôi xin được viết luôn ra đây:<br /> xmới = xcũ.cos(alpha) – ycũ.sin(alpha).<br /> ymới = xcũ.sin(alpha) + y cũ.cos(alpha).<br /> Trong đó alpha là góc quay.<br /> Tất nhiên P càng lớn thì càng tốt. Đối với bài này tôi để P = 35000/N và chạy đúng<br /> hết tất cả các test. Đó chính là kết quả của việc áp dụng tính phân rã thứ (1).<br /> <br />