Just algorithm!
Square Fields



สมมติมีจุดหลายๆ จุดอยู่บนพื้นที่

เราต้องวางสี่เหลี่ยมจตุรัสจำนวน k อัน

เพื่อครอบคลุมจุดทั้งหมด โดยต้องวางขนานกับแกน x y

คำถามคือ ต้องใช้สี่เหลี่ยมขนาดเล็กที่สุดขนาดเท่าไหร่ถึงจะครอบคลุมจุดทั้งหมด

อ่านเพิ่มเติม ที่นี่



เนื่องจากโจทย์กำหนดว่า ขนาดของพื้นที่ที่ใหญ่ที่สุดคือ 64,000

ดังนั้น วิธีการแก้ปัญหาคือ Binary Search

เราแค่ต้องหาว่า สี่เหลี่ยมขนาด x จำนวน k อัน จะครอบคลุมจุดทั้งหมดได้หรือไม่



เริ่มจาก ประกาศ function
let solve sets sqrs =

sets คือจุดต่างๆ

sqrs คือจำนวนสี่เหลี่ยมจตุรัส



ถัดมาคือ function เพื่อหาว่าสี่เหลี่ยมจตุรัสจะสามารถครอบคลุมจุดทั้งหมดได้หรือไม่
let matchSqr size =
    let rec matchSqrX sets sqrs =
        if Set.count sets <= sqrs then
            Seq.singleton size
        elif sqrs = 0 then
            Seq.empty

function ชื่อ matchSqr

size คือขนาดของสี่เหลี่ยมจตุรัส



เราสร้างอีก function (matchSqrX) เพื่อทำ recursive

ถ้า จำนวนจุดที่เหลือ (sets) <= จำนวนสี่เหลี่ยม (sqrs)

หมายความว่าเราสามารถใช้สี่เหลี่ยมหนึ่งอัน ต่อหนึ่งจุด และได้คำตอบทันที

แต่ถ้า จำนวนสี่เหลี่ยม (sqrs) เหลือ 0 แปลว่าไม่มีคำตอบ



function ยังไม่จบ มีต่อ

        else 
            let x,y = Set.minElement sets
            let ys1 = sets |> Seq.filter (fun (x2,y2) -> x2 > x && x2 <= x+size &&
                                                         y2 >= y-size && y2 <= y)
                           |> Seq.map snd
                           |> Set.ofSeq
            let ys2 = sets |> Seq.filter (fun (x2,y2) -> x2 > x && x2 <= x+size &&
                                                         y2 >= y && y2 <= y+size)
                           |> Seq.map snd
                           |> Seq.map (fun y2 -> y2 - size)
                           |> Set.ofSeq
            let ys = ys1 + ys2 + Set.singleton y
            seq {
               for y in ys do
               let coveredSet = sets |> Seq.filter (fun (x2,y2) -> x2 >= x && x2 <= x+size &&
                                                                   y2 >= y && y2 <= y+size)
                                     |> Set.ofSeq
               for i in matchSqrX (sets-coveredSet) (sqrs-1do
               yield i
            }
    matchSqrX sets sqrs

ตอนแรก เราดีงเฉพาะจุดที่น้อยที่สุด (x,y) ออกมาจาก sets

เนื่องจาก x น้อยที่สุด เราแน่ใจได้เลยว่ามันจะเป็นจุดที่อยู่ซ้ายที่สุด

เราสามารถวางสี่เหลี่ยมชนจุดทางด้านซ้ายได้เลย



ต่อมาเราก็เลื่อนสี่เหลี่ยมไปบนสุด คือด้านล่างของสี่เหลี่ยมชนจุด y

แล้วเราก็ list จุด y ต่างๆ ที่เจอออกมา (ys1)

เช่นเดียวกัน ทีนี้ลองเลื่อนสี่เหลี่ยมไปล่างสุด ด้านบนของสี่เหลี่ยมชนจุด y

แล้วเราก็ list จุด y ต่างๆ ออกมา (ys2)



ys ก็คือจุด y ทั้งหมดที่สี่เหลี่ยมจะเลื่อนขึ้นและลงได้

ทีนี้ก็ loop เลยครับ ลองทุกวิธี

coveredSet คือ จุดที่โดนครอบโดยสี่เหลี่ยม

แล้วเราก็ recursive เพื่อลองต่อไป



สุดท้าย ก็หาขนาดที่เล็กที่สุดด้วย binary search
let rec binarySearch min max =
    if min = max then
        max
    else 
        let mid = (min + max) / 2
        let result = matchSqr mid
        if Seq.isEmpty result then
            binarySearch (mid+1) max
        else
            binarySearch min mid
binarySearch 1 64000 |> string

จบ






Create Date : 06 กรกฎาคม 2557
Last Update : 6 กรกฎาคม 2557 22:37:33 น. 0 comments
Counter : 157 Pageviews.

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 
รหัสส่งข้อความ
กรุณายืนยันรหัสส่งข้อความ

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]









New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.