Sức mạnh của Tìm kiếm nhị phân

Hoài niệm về những năm tháng lớp 11 đầy nhiệt huyết với thuật toán.

Bài toán Bộ sưu tập tiền xu

Bạn Nam có 1 bộ sưu tập tiền xu gồm N đồng xu (N > 2) có hình tròn, đồng xu thứ i có bán kính r[i] (là số thực và dương). Bạn Nam muốn xếp chúng thành 1 vòng tròn, 2 đồng xu kề nhau thì tiếp xúc nhau. Đồng thời phải tồn tại 1 đồng xu thứ N+1 sao cho nếu đặt nó vào giữa vòng tròn thì nó tiếp xúc hết với N đồng xu kia. Bài toán đặt ra là hãy tính bán kính của đồng xu thứ N+1 này!

Ví dụ: với N = 4, r[1] = r[2] = r[3] = r[4] = 2, thì kết quả là 0.8284 như hình dưới đây

Quả thực lần đầu tiên đọc cái đề tôi hoàn toàn mất phương hướng, không biết phải làm sao cho đến khi được gợi ý là dùng Tìm kiếm nhị phân.

Giả sử kích thước của đồng xu cần tìm là rKQ, trước hết ta cần tính xem nó nằm trong khoảng nào? Hay nói cách khác là tìm ngưỡng dưới và ngưỡng trên của nó. Ngưỡng dưới dễ thấy bằng 0, ngưỡng trên tính như sau:

Xem hình vẽ trên, rõ ràng chu vi của đồng xu cần tìm phải nhỏ hơn chu vi của đa giác lồi (màu đỏ) nối N tâm đồng xu đã cho. Chu vi đa giác dễ thấy = 2 * (r[1] + r[2] + … + r[N]), từ công thức tính chu vi đường tròn ta suy ra ngưỡng trên là:

2 * (r[1] + r[2] + … + r[N]) / (2 * pi) = (r[1] + r[2] + … + r[N]) / pi

Đã có ngưỡng dưới và ngưỡng trên của tập tìm kiếm, còn lại để tìm kiếm nhị phân ta cần kiểm tra xem khi đem thử 1 kích thước cho đồng xu nằm ở giữa, nó > hay < hay = rKQ

Gọi kích thước đem thử là R, ta sẽ tính số đo của mỗi N góc mà góc thứ i là góc tạo bởi 2 tiếp tuyến kẻ từ tâm đồng xu nằm giữa đến đồng xu thứ i:

Hình tròn trên là đồng xu thứ i. Để ý tứ giác màu đỏ, nó có 2 góc vuông đối nhau, 2 cạnh nhỏ = nhau = r[i], đường chéo (tô màu xanh lá cây) = (r[i] + R), nhờ các hàm lượng giác tính được góc tô màu xanh da trời.

Gọi tổng N góc đó là SumAngle:

  • Nếu SumAngle = 360 độ –> OK –> R = rKQ và kết thúc tìm kiếm!
  • Nếu SumAngle < 360 độ –> R > rKQ –> tìm kiếm tiếp ở khoảng dưới.
  • Nếu SumAngle > 360 độ –> R < rKQ –> tìm kiếm tiếp ở khoảng trên.

1 lưu ý chung cho các bài toán hình học là: vì máy tính xử lí số thực 1 cách xấp xỉ nên ta cần 1 hằng số epsilon cho việc so sánh > < = các số thực.

Advertisements

2 thoughts on “Sức mạnh của Tìm kiếm nhị phân

  1. Cái phần SumAngle hk hiểu lắm, có vẻ sai rồi. Nếu 2 đồng xu ở ngoài khác bán kính thì đường thẳng nối tâm đồng xu giữa và tiếp điểm không phải là tiếp tuyến. Theo em nghĩ là tính góc tạo bới 2 cạnh R + r[1], R + r[2] của tam giác có 3 cạnh r[1] + r[2], R + r[1], R + r[2] rồi cộng các góc lại xem có đủ 360 thì đúng hơn.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s