Just algorithm!
Train Timetable



คราวนี้สมมติว่าเราเป็นผู้จัดการรถไฟ

ซึ่งมีแค่ 2 สถานี คือ A กับ B

A กับ B มีตารางออกจากสถานีแน่นอน มีระยะเวลาเดินทางแน่นอน และมีระยะเวลาพักรถแน่นอน

เราต้องหาว่า เราต้องหารถมาวางไว้ที่สถานี A กี่คัน และสถานี B กี่คัน

อ่านต่อ ที่นี่



วิธีคิดก็เอาตารางเวลามาเรียงกันทั้งหมด เราหยิบเที่ยวที่ออกเช้าสุดออกมา

เมื่อเดินไปถึงอีกสถานีนึง เราก็มาดูว่าตารางเวลาถัดไปของอีกสถานีนึงคืออะไร แล้วก็ตัดไปเรื่อยๆ



เริ่มกันเลย
let solve t set =

t คือระยะเวลาพักรถ

set คือ Set ของตารางเวลาซึ่งเป็น tuple ซึ่งเรียงดังนี้ เวลาออก เวลาถึง สถานี id

สถานีผมใช้เป็น boolean ถ้าเป็น true คือ สถานี A ถ้า false คือ สถานี B
let rec runTrip startTime station set =
    let findFn (dep,_,i,_) = dep >= startTime && i = station
    match Seq.tryFind findFn set with
    | None     -> set
    | Some(it) -> let _,arr,_,_ = it
                  runTrip (arr+t) (not station) (Set.remove it set)

ถัดมาคือ function เดินรถ เช่น เดินรถจาก A ไป B ถึง B กี่โมง สามารถออกจาก B ไป A ได้อีกหรือไม่

ถ้าได้ (Some(it)) ก็ตัดออกจาก set ไปเรื่อยๆ


แต่ถ้าไม่ได้ (None) ก็คืนค่า set ที่ถูกตัดออกไป
let rec startTrip a b set =
    if set = Set.empty
    then a, b
    else let startTime,_,station,_ = set.MinimumElement
         let newSet = runTrip startTime station set
         if station
         then startTrip (a+1) b newSet
         else startTrip a (b+1) newSet

และถัดมาคือ function ดูว่าต้องมีรถที่ A และ B อย่างละเท่าไหร่

หลักการคือ เอารถเที่ยวแรกออกมา แล้วโยนเข้าไปใน runTrip ก็จะได้ set ใหม่ที่หักตารางของรถคันนี้ออกไป

วนไปเรื่อยๆ จนไม่มี item ใน set (Set.empty) จะได้คำตอบออกมา



สุดท้ายคืนค่า
let a, b = startTrip 0 0 set
sprintf "%A %A" a b

จบ




Create Date : 15 พฤศจิกายน 2557
Last Update : 15 พฤศจิกายน 2557 9:40:52 น. 0 comments
Counter : 110 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

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.