creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

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




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
McNuggets

ชอบกินนักเก็ตมั้ยครับ? เวลาขายตามพวกแม็คฯหรือเคเอฟซีนี่เขาจะขายกันเป็นกล่อง ๆ มีให้เลือกหลายขนาด สมมติว่ามีกล่อง 6 ชิ้น, 9 ชิ้น กับ 20 ชิ้น (สมมติว่ามีแค่ 3 ขนาด) ปัญหาข้อนี้ให้หาจำนวนเต็ม M ที่น้อยที่สุด ที่ไม่ว่าเราจะสั่งนักเก็ต n ชิ้นใด ๆ ก็ตามที่ n ไม่น้อยกว่า M แล้วเราสามารถสั่งมันได้โดยเลือกจำนวนกล่องผสม ๆ กันจากกล่องสามขนาดที่มีอยู่นั้นเสมอ (ตัวอย่างของคำว่าสั่งได้ เช่น ถ้าคุณสั่ง 7 ชิ้น แบบนี้สั่งไม่ได้, หรือสั่ง 19 ชิ้นก็สั่งไม่ได้ แต่สั่ง 41 ชิ้นได้ เพราะ 41 = 20 + 9 + 6 + 6)

หรือคุณคิดว่าไม่มีค่า M ดังกล่าวอยู่ครับ?



โจทย์เรียบง่ายและสวยดีครับ เพราะถ้าไม่ถาม ก็คิดไม่ถึงว่าจะมีค่า M แบบนี้อยู่ เนื่องจาก 6 เป็นจำนวนน้อยสุดต่อชิ้น ดังนั้นถ้าเราสามารถจัด M, M+1, M+2, M+3, M+4, M+5 ได้ M ที่น้อยที่สุดก็จะเป็นคำตอบ สังเกตว่า (6 mod 3) = (9 mod 3) = 0 ส่วน (20 mod 3) = 2 เรายังขาดผลลัพธ์จากการ mod 3 แล้วเท่ากับ 1 ตัวต่ำสุดที่เป็นไปได้ก็คือ (40 mod 3) = 1 อันนี้มั่นใจได้เลยครับว่า M > 40 ชัวร์! ที่เหลือถ้าเราไม่อยากตั้งสมการหลายตัวแปร ก็ลองแทนค่าครับ 41 = 20 + 9 + 6 + 6, 42 = 9 + 9 + 9 + 9 + 6 แต่ 43 มีปัญหา จัดไม่ได้ 44 = 20 + 9 + 9 + 6, 45 = 9 x 5, 46 = 20 + 20 + 6, 47 = 20 + 9 + 9 + 9, 48 = 6 x 8 และ 49 = (2 x 20) + 9 ดังนั้น M = 44




Create Date : 22 กรกฎาคม 2552
Last Update : 22 กรกฎาคม 2552 17:13:49 น. 0 comments
Counter : 1157 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.