|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
||||
|
||||
รบกวนรังนกหน่อยครับ ผมว่ามันยากมากๆเลย
ในการสร้างห้องแล็บแห่งหนึ่งที่มีห้องวิจัยย่อย 15 ห้องและมีเครื่องเซิฟเวอร์ 10 เครื่อง โดยในช่วงเวลาหนึ่งเครื่องเซิฟเวอร์แต่ละเครื่องจะถูกใช้ได้จากห้องวิจัยย่อยเพียง 1 ห้องเท่านั้น จะต้องมีการเดินสายระหว่างห้องวิจัยกับเครื่องเซิฟเวอร์อย่างน้อยที่สุดกี่สายจึงจะมั่นใจได้ว่า เมื่อมีการใช้ห้องวิจัยไม่เกิน10ห้อง แต่ละห้องจะสามารถเข้าใช้เครื่องเซิฟเวอร์ได้
โจทย์ยาวหน่อยนะครับ IDEA มันคืออะไรครับข้อนี้ แล้วเขียนอย่างไรจึงจะได้คะแนนเต็ม |
#2
|
||||
|
||||
เหมือนกับเป็นโจทย์ที่อาจารย์สอนในค่ายนะครับ
ลองวาดรูปดูเเล้วพิจารณาหลายๆรูปสิครับเเล้วนำความสัมพันธ์มาเชื่อมกันครับ
__________________
God does mathematics. |
#3
|
||||
|
||||
โจทย์นี้ อ. เอามาจากหนังสือ combi ของ Tucker แน่ๆ
ใช้รังนกแบบปรับปรุงนิดหน่อย กับใช้ข้อขัดแย้งช่วย รวดเดียวออก ตอบ 60 ครับ
__________________
คนไทยร่วมใจอย่าใช้ภาษาวิบัติ ฝึกพิมพ์สัญลักษณ์สักนิด ชีวิต(คนตอบและคนถาม)จะง่ายขึ้นเยอะ (จริงๆนะ) Stay Hungry. Stay Foolish. |
#4
|
||||
|
||||
รบกวนเขียน Sol ให้ทีสิครับ ผมคิดไม่ออกจริงๆ
|
#5
|
||||
|
||||
Let $S_i, 1\le i\le 10$ be the set of servers and $W_j, 1\le j\le 15$ be the set of workstations. Connect $W_k$ to $S_k$ for $1\le k\le 10.$ Then connect $W_k$ for $11\le k\le 15$ to $S_i,1\le i\le 10.$ Clearly, one requires 60 cables. Assume that there are fewer than 60 connections between workstations and servers. Hence some servers would be connected to at most $\lfloor \frac{59}{10}\rfloor =5$ workstations. Thus, the remaining 9 servers are not enough to allow the other 10 workstations to simultaneously access different servers.
__________________
คนไทยร่วมใจอย่าใช้ภาษาวิบัติ ฝึกพิมพ์สัญลักษณ์สักนิด ชีวิต(คนตอบและคนถาม)จะง่ายขึ้นเยอะ (จริงๆนะ) Stay Hungry. Stay Foolish. |
#6
|
||||
|
||||
แล้วเรามั่นใจได้หรอครับว่า59สายที่ทำไม่ได้นั้นเราต่อแบบดีที่สุดแล้ว
ยังงงตรง59สายอะครับ 30 มีนาคม 2012 14:53 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ polsk133 |
#7
|
||||
|
||||
#6 คุณ nongtum แสดงให้ดูแล้วว่าต้องมีอย่างน้อย 60 สาย แต่ที่ผมสงสัยคือต้องแสดงอีกว่า 60 สายนั้นเป็นไปได้ใช่ไหมครับ ซึ่งตรงนี้ไม่รู้จะแสดงยังไงครับ ช่วย Hint เพิ่มหน่อยครับ
__________________
----/---~Alice~ จงรับรู้ไว้ ชื่อแห่งสีสันหนึ่งเดียวที่แสดงผล ---/---- ~Blue~ นี่คือ สีแห่งความหลังอันกว้างใหญ่ของเว็บบอร์ดนี้ |
#8
|
|||
|
|||
สมมติให้เครื่องservers10เครื่องเป็น$1, 2, 3, 4, 5, 6, 7, 8, 9,10$
ห้องวิจัย15ห้องเป็น $A, B, C, D, E, F, G, H, I, J, K, L, M, N, O$ วิธีคือ ให้ต่อสาย10ห้องใดๆกับเครื่อง servers เต็ม10 ห้องก่อน 10 ห้องก็ใช้ 10 สาย ที่เหลือ 5 ห้องก็ต่อสายห้องละ 10 สายกับเครื่อง servers ทั้ง 10 เครื่อง 5ห้องก็เป็น 50 สาย เพราะฉะนั้นใช้สายทั้งหมดอย่างน้อย $=10+50=60$ สาย |
#9
|
||||
|
||||
Hence some servers would be connected to at most 5 workstations.
แล้วสรุปได้อย่างไรว่าได้9ห้องหรอครับ |
#10
|
||||
|
||||
แต่ละ server ต้องมีอย่างน้อย 6 ห้องที่ต่อ
เพราะถ้ามี server A ต่อน้อยกว่า 6 ห้อง จะมีห้องที่ไม่ได้ต่อมากกว่าหรือเท่ากับ 10 ห้อง เลือกห้องวิจัยที่ไม่ได้ต่อมา 10 ห้อง จะไม่มีห้องใดต่อกับ server A เลย อีก 9 servers ที่เหลือจึงไม่เพียงพอต่อการต่อสายจึงเกิดข้อขัดแย้งครับ
__________________
----/---~Alice~ จงรับรู้ไว้ ชื่อแห่งสีสันหนึ่งเดียวที่แสดงผล ---/---- ~Blue~ นี่คือ สีแห่งความหลังอันกว้างใหญ่ของเว็บบอร์ดนี้ 30 มีนาคม 2012 22:23 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Thgx0312555 |
#11
|
||||
|
||||
อ่อ ขอบคุณมากครับ
แล้วก็ขอแสดงความยินดีกับคุณ Thgx0312555 ที่ได้ สพฐ เหรียญทองครับ |
#12
|
||||
|
||||
ขอบคุณครับ
__________________
----/---~Alice~ จงรับรู้ไว้ ชื่อแห่งสีสันหนึ่งเดียวที่แสดงผล ---/---- ~Blue~ นี่คือ สีแห่งความหลังอันกว้างใหญ่ของเว็บบอร์ดนี้ |
#13
|
|||
|
|||
#10 ผมว่า idea ถูกต้องแล้วครับที่ servers แต่ละเครื่องจะต้องต่อกับห้องวิจัยอย่างน้อย 6 ห้องใดๆ
แต่คำอธิบายแบบ hint ของคุณnongtumจะชัดเจนกว่านะครับ ไม่งง 31 มีนาคม 2012 11:25 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ artty60 |
#14
|
|||
|
|||
แสดงว่าไม่เจอหนังสือดี โชคร้ายจัง
|
#15
|
|||
|
|||
จริงๆแล้วตกลงข้อนี้เฉลยเป็นยังไงครับ
เพราะไปคิดดูแล้วถ้า 60 สายนี่เวลาใช้งานจริงๆอาจทำให้บางช่วงเวลาแต่ละห้องวิจัยใดๆ อาจใช้เครื่องเซิฟเวอร์ไม่ได้เพราะไม่ได้ต่อสายกับเซิฟเวอร์เครื่องที่ว่างอยู่นั้น จะต้องไปใช้ห้องวิจัยที่ว่างอยู่และได้ต่อเชื่อมกับเครื่องเซิฟเวอร์ที่ว่างนั้น ก็จะขัดกับโจทย์ ที่ว่าถ้ามีห้องวิจัยใช้เครื่องเซิฟเวอร์ไม่เกิน 10 ห้อง ห้องใดๆจะเข้าใช้เครื่องเซิฟเวอร์ที่ว่านั้นได้ หรือไม่ก็ต้องswitchสายซึ่งอาจทำให้การใช้งานเครื่องเซิฟเวอร์(ที่สำคัญมากๆ)ของบางห้องวิจัยต้องถูกรบกวนหรือขาดช่วง หรือว่าผมตีโจทย์ผิด หรือคิดมากไป ผมจึงอยากรู้คำอธิบายของเฉลยจริงๆข้อนี้ครับ 10 เมษายน 2012 09:19 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ artty60 |
|
|