Just algorithm!
์Number Sets



ข้อนี้จะมีจำนวนตั้งแต่ A ถึง B

โดยจะมีเลขจำนวนเฉพาะอย่างน้อย P

ถ้าเลขระหว่าง A ถึง B ตัวไหนหารด้วยจำนวนเฉพาะลงตัว จะถือว่าเลขเหล่านั้นอยู่กลุ่มเดียวกัน

และถ้ามีตัวเลขไหนสามารถหารด้วยจำนวนเฉพาะ 2 ตัวลงตัว


กลุ่มของจำนวนเฉพาะ 2 ตัวนั้นจะรวมกันเป็นกลุ่มเดียวกัน

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



ข้อนี้เขียนเป็น functional ค่อนข้างลำบาก

เช่น จำนวนเฉพาะอาจจะต้องใช้ Sieve

การจัดกลุ่มต้องใช้ Disjoint Set

ซึ่ง data structure ดังกล่าวเป็นแบบ mutable



ข้อดีของ f# อีกอย่างคือ ไม่ใช่ pure functional

หากจำเป็นต้องใช้ mutable data structure ก็ไม่มีปัญหา



เริ่มจาก Prime
let prime = Prime()

อันนี้ผมใช้ prime ที่เขียนเอง อ่านเพิ่มได้ ที่นี่



เริ่มเลย
let solve A B P =
    let mutable size = int (B - A + 1L)
    let primes = prime.FromRange(P, B-A)
    let set = DisjointSet()

size เป็น การประกาศแบบ mutable ซึ่งจะแก้ค่าได้ภายหลัง

primes คือ จำนวนเฉพาะระหว่าง P ถึง B-A

set ก็คือ disjoint set เขียนเองก็ได้ครับ logic ตาม wiki
for p in primes do
    let start = ((A - 1L)/+ 1L)*p
    for n in {start+p..p..B} do
        if set.Union(start, n) then
            size <- size - 1

size |> string

ทีนี้ก็ loop ตาม prime แต่ละตัว

ไล่หาตัวที่หารด้วย prime ลงตัว จาก A ถึง B

แล้วเอาค่าที่ได้ union เข้า disjoint set

ถ้า union สำเร็จก็หัก size ไป 1



ทำจนจบก็ได้คำตอบครับ




Create Date : 15 พฤศจิกายน 2557
Last Update : 15 พฤศจิกายน 2557 23:57:50 น. 0 comments
Counter : 206 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.