Thuật toán Heuristic số thực

Heuristic bằng số thực

Lưu Tuấn Anh

Trong tin học, các bài toán liên quan đến số thực thường là các bài toán khá phức tạp trong

việc xử lí và thao tác. Ví dụ: Nhân chia số thực chậm hơn rất nhiều so với số nguyên, rất

khó kiểm soát điều kiện bằng nhau, hay lỗi thường gặp là chia cho 0.

Ví dụ bạn sẽ nhận được 1 vòng lặp vô hạn nếu bạn viết:

x:=0;

while x<>1 do x:=x+0.1;

trong khi bạn nghĩ rằng nó sẽ kết thúc sau 10 bước lặp.

Tuy vậy, ta có thể sử dụng chính những tính chất này của số thực để áp dụng vào 1 số bài

toán như là 1 cách Heuristic cho hiệu quả rất tốt.

Heuristic số thực sử dụng 1 số tính chất của số thực: Rất khó tạo ra được 2 số thực bằng

nhau bằng và 2 tổng các số thực bằng nhau bằng hàm RanDom. Vì các test thực tế hay do

ban giám khảo tạo ra hầu hết đều dùng hàm RanDom nên khả năng có 2 số thực (hay 2

tổng) bằng nhau trong bộ test là rất khó.

Bài 1: CIRCLE

Trên mặt phẳng toạ độ cho N điểm, không có 3 điểm nào thẳng hàng. Hãy chọn 3 điểm

trong N điểm này sao cho đường tròn qua 3 điểm được chọn sẽ chứa bên trong nó đúng K￾3 điểm khác.

Dữ liệu : vào từ file CIRCLE.IN

Dòng đầu chứa 2 số nguyên N và K ( 3 ≤ K≤ N ≤ 10000);

N dòng theo tiếp theo, dòng thứ i chứa toạ độ điểm thứ i là cặp số thực xi,yi thể hiện hoành

độ và tung độ của điểm thứ i (giá trị tuyệt đối của các toạ độ không qúa 1000).Kết quả ghi

ra file văn bản CIRCLE.OUT chỉ 1 dòng gồm 3 số thể hiện số hiệu 3 đỉnh được chọn.

IN

5 4

0 0

2 0

0 3

2 1

2 5

OUT

1 2 3

Bài này có thuật toán đơn giản sau:

Lần lượt chọn 2 điểm X,Y. Với các điểm Ai còn lại ta xét góc XAiY, đặt G[i]=XAiY. G[i]

ta có thể tính bằng hàm cosin nhưng theo tôi ta nên dùng hàm Theta thì hơn. Hàm Theta

tính như sau:

function thetăx1, y1, x2, y2 : real) : real;

{ham nay xep cac diem theo thu tu nhu xep theo arctang cua goc tao boi 2 diem (x1,y1) va

(x2,y2) tao voi duong nam ngang}

var dx, dy, t : real;