นั่งมองเหรียญที่วางเรียงกันโดยบังเอิญอยู่บนโต๊ะคอม พาจิตให้คิดถึงเกมเกมนึง,,,

เกมนี้ มีกติกาอยู่ว่า

  • มีเหรียญอยู่จำนวนหนึ่งวางเรียงกันอยู่
  • ผู้เล่นมี 2 ฝ่าย
  • แต่ละฝ่ายสลับกันหยิบเหรียญไปเรื่อยๆ โดยแต่ละครั้ง หยิบเหรียญได้ 1 หรือ 2 เหรียญก็ได้
  • ใครหยิบเหรียญสุดท้าย เป็นฝ่ายชนะ

เนื่องจาก ผมได้รับแรงบันดาลใจจากนักร้องเครางาม นามว่า นิค นิรนาม(ก็ไหงบอกนิรนาม แต่ถามก็ดันตอบว่าชื่อนิค ... ฮ่วย!) จากผลงานอัลบั้มหยิบสิบ(ซึ่งหยิบกันถึงสิบครั้ง เพราะมีถึงสิบอัลบั้ม *..*)

 

ด้วยเหตุนี้ จึงเป็นที่มาของ ,,,

หยิบสิบ หยิบเป็น หยิบตาย!!!


กติกาโคตรง่าย!!! มีเหรียญอยู่ 10 เหรียญ ผู้เล่น 2 คน สลับกันหยิบเหรียญ โดยแต่ละครั้งที่หยิบ จะหยิบครั้งละ 1 เหรียญ หรือ 2 เหรียญ ก็ได้ ตามแต่ใจชอบ ... ผู้ที่หยิบ(เหรียญที่)สิบ คือผู้ชนะ

ก็ลองไปเล่นกับเพื่อนดูนะครับ ถือเป็นการใช้เวลาอู้ให้เกิดประโยชน์

... ... ...

คำถามต่อมาก็คือ ถ้าเราต้องการเป็นผู้ชนะตลอดกาล เราควรจะทำอย่างไร?

  • ตอบง่ายๆแบบกำปั้นทุบดินก็คือ หยิบเหรียญที่สิบให้ได้สิเพ่ *..*)v

และถ้าเราอยากหยิบเหรียญที่สิบให้ได้ เราจะทำอย่างไรเคอะ?

  • เราก็ต้องหยิบเหรียญที่เจ็ดให้ได้


ทำไมล่ะ?

  • เพราะ ถ้าเราหยิบเหรียญที่เจ็ดได้ ไม่ว่าคู่ต่อสู้ของเราจะหยิบ 1 เหรียญ หรือ 2 เหรียญในครั้งถัดไป เราก็จะสามารถหยิบเหรียญที่สิบได้อยู่ดี
  • เช่นเดียวกัน ถ้าเราอยากหยิบเหรียญที่เจ็ดให้ได้ เราก็ต้องหยิบเหรียญที่สี่ให้ได้
  • ถ้าเราอยากหยิบเหรียญที่สี่ให้ได้ เราก็ต้องหยิบเหรียญแรกให้ได้
  • ถ้าเราอยากเป็นคนหยิบเหรียญแรก เราก็ต้องเป็นคนเล่นก่อน


ถ้ามีจำนวนสิบเหรียญ และหยิบได้ทีละไม่เกิน 2 เหรียญ เราจะต้องหยิบเหรียญแรกขึ้นไปก่อน จากนั้น ถ้าคู่ต่อสู้เราหยิบ 1 เหรียญ เราก็จะหยิบ 2 เหรียญ ,,,, และถ้าคู่ต่อสู้เราหยิบ 2 เหรียญ เราก็จะหยิบ 1 เหรียญ ชิมิ

  • ใช่

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

  • ขออธิบายเป็นระเบียบวิธี(อัลกอริธึ่ม) ดังต่อไปนี้ย์
  1. สมมติว่าเหรียญมีทั้งหมด N เหรียญ และหยิบขึ้นไปได้ครั้งละ 1 ถึง k เหรียญ
  2. ให้นำ N/(k+1) ได้เท่าไหร่ ปัดทศนิยมขึ้น แล้วกำหนดให้เป็น M เช่น 12/4 = 3 อันนี้ไม่ต้องปัดเศษ เพราะหารลงตัว กรณีนี้ M = 3 ,,, แต่ถ้า 10/3 =3.3 อันนี้ปัดทศนิยมขึ้นทันที กรณีนี้ M = 4 (ใครเคยเขียนโปรแกรม น่าจะรู้จักฟังก์ชัน ceil นะครับ *w*)
  3. เหรียญที่เราจะต้องหยิบคือ เหรียญที่ N-(i-1)(k+1)โดยที่ i = 1, 2, ..., M
  4. การแทนค่าครั้งสุดท้าย (แทนด้วย M) คือ ลำดับของเหรียญแรกที่เราจะต้องหยิบ ซึ่ง ถ้าหมายเลขออกมา มากกว่าจำนวนเหรียญสูงสุดที่เราสามารถหยิบได้(มากกว่า k) แสดงว่า เราจะต้องให้คู่ต่อสู้หยิบก่อน แล้วเราก็หยิบตามหมายเลขที่เราคำนวนได้ ,,, แต่ถ้า แทนค่าด้วย M แล้ว น้อยกว่า หรือเท่ากับ k ให้เราเป็นผู้เริ่มหยิบก่อน โดยหยิบตามหมายเลขที่เราคำนวณได้
  • ขอยกตัวอย่างด้วยกรณีหยิบสิบข้างบนนู้นนนน
  1. เหรียญมีทั้งหมด 10 เหรียญ และหยิบได้ครั้งละ 1 ถึง 2 เหรียญ ดังนั้น N = 10, k = 2
  2. N/(k+1) = 10/(2+1) = 10/3 = 3.3 มีทศนิยม ให้ปัดขึ้นเป็น 4 ดังนั้น M = 4
  3. เหรียญที่เราจะต้องหยิบได