Bài toán Tìm hạng trong không gian 2D.

[11520161]

Mình đang học môn Phân tích & thiết kế thuật toán...đang gặp phải bài tập Tìm hạng trong không gian 2D dùng phương pháp chia để trị. Mọi người, ai biết bài này hướng dẫn làm với.

[11520371]

Vấn đề nan giải... các anh chị khóa trên vào giúp tụi em với :sad:

[11520246]

Đề có nói rõ hạng là hạng gì vậy? Cho tí manh mối đi.

[11520161]

Bài toán như thế này nè: Cho điểm A(a1,a2) và B(b1,b2). A được gọi là "trội hơn" B nếu a1 >b1 và a2 >b2
Cho tập S có n điểm trong 2D, hạng của điểm X là số lượng các điểm mà X trội hơn. Thiết kế thuật toán để sắp hạng các điểm trong tập S?
Ý tưởng:
Áp dụng phương pháp chia để trị.
Độ phức tạp O(?)
Chia:
. Nếu S chỉ có 1 điểm -> hạng của điểm đó là 0
. Ngược lại, chia S thành 2 tập A, B theo giá trị hoành độ.
Đệ quy:
Tìm hạng các điểm trong A và B.
Trị:
Sắp các điểm A và B theo giá trị trục tung.

[11520246]

Bài toán như thế này nè: Cho điểm A(a1,a2) và B(b1,b2). A được gọi là "trội hơn" B nếu a1 >b1 và a2 >b2
Cho tập S có n điểm trong 2D, hạng của điểm X là số lượng các điểm mà X trội hơn. Thiết kế thuật toán để sắp hạng các điểm trong tập S?
Ý tưởng:
Áp dụng phương pháp chia để trị.
Độ phức tạp O(?)
Chia:
. Nếu S chỉ có 1 điểm -> hạng của điểm đó là 0
. Ngược lại, chia S thành 2 tập A, B theo giá trị hoành độ.
Đệ quy:
Tìm hạng các điểm trong A và B.
Trị:
Sắp các điểm A và B theo giá trị trục tung.

Ý của Nghĩa thì như thế này. Thuật toán có dạng như sau:

[B]Hạng[/B](S, R, left, right):[INDENT]if right <= left: return (S chỉ có 1 điểm)
j =[B] PhânHoạch[/B](S, R, left, right) (Sắp các điểm theo hoành độ)

[B]Hạng[/B](S, R, left, j)
[B]Hạng[/B](S, R, j+1, right)

[B]Trị[/B](S, R, left, right) (Sắp các điểm theo tung độ)
[/INDENT]

R là cái dùng để lưu hạng của các điểm.

Và bây giờ, trước hết chúng ta nhớ lại hai thuật Quicksort và Mergesort nhé.
Ở thuật Quicksort chúng ta có hàm phân hoạch, hàm này có nhiệm vụ chia mảng S đã cho ra làm 3 khúc (thay đổi vị trí các phần tử của mảng), bằng cách tìm một con chốt S[j] nào đó sao cho ra 3 khúc: S[left...j] <= S[j] <= S[j+1..right].
Như vậy ta có thể ăn theo hàm phân hoạch này để sửa đổi tí xíu sao cho "Chia S thành 2 tập A, B theo giá trị hoành độ", bằng cách lúc viết hàm phân hoạch ta so sánh và
hoán đổi các phần tử theo giá trị hoành độ ấy.

j là vị trí của con chốt chia mảng ra làm 3 khúc.
Tiếp theo ở thuật Mergesort từng học, có hàm Merge được thực thi theo kiểu sao chép mảng S ban đầu, rồi thực hiện sắp xếp sao cho 2 mảng con S[left..j] và S[j+1..right] thỏa điều kiện (ở Mergesort thì mục tiêu là 2 mảng con này được sắp xếp tăng dần/giảm dần), còn ở bài của chúng ta, chỉ việc sắp xếp theo tung độ. Ta thực thi hàm Merge này và gọi nó là Trị.
Rõ ràng và cụ thể hơn, thì một điểm có dạng mảng 1 chiều [-3,2], -3 là hoành độ, 2 là tung độ. Tập S là mảng 2 chiều, mỗi phần tử chính là 1 điểm. Ok?

Như thế thì việc tính hạng ra làm sao, ta sẽ tính trong lúc làm hàm phân hoạch, cụ thể khi so sánh theo hoành độ giữa 2 điểm (để sắp xếp theo hoành độ, hãy dựa vào phân hoạch của Quicksort mà viết hàm nhé), ta thêm một câu if so sánh tung độ giữa 2 điểm đó luôn, nếu phát hiện có trội thì tăng hạng của điểm đó lên 1 (cập nhật vào R).
Kết quả cuối cùng nằm trong R!