จงหาวิธีคิด การสุ่มหาตัวเลขที่ต้องการ ให้ได้จำนวนการสุ่มที่น้อยที่สุด

Q & A

จงหาวิธีคิด การสุ่มหาตัวเลขที่ต้องการ ให้ได้จำนวนการสุ่มที่น้อยที่สุด

ถ้าผมสุ่มเลข 2 หลัก จะเลขอะไรก้ได้ขอแค่มันเป็น 2 หลัก
มีวิธีการหามันเจอได้อย่างไร โดยให้โปรแกรมใช้จำนวนรอบในการค้น น้อยที่สุด

A : binary search ครับ น่าจะเร็วสุด

B : ถ้าจะใช้ Binary Search เวลาทายผิดต้องมีการบอกใบ้ว่า มากกว่าหรือน้อยกว่าด้วยป่ะครับ แต่ถ้าไม่มีการบอกใบ้ผมว่าทำใน 10 รอบไม่ได้อะ

C : การสุ่มตัวเลขมา โดยให้ค้นหาให้หา จาก 00 - 99 โดยไม่มีตัวเลขซ้ำ ซึ่งข้อมูลเรียงกันแล้ว ผมว่าไม่ต้องวนลูป ก็รู้ตำแหน่งแล้วครับ แต่ถ้าข้อมูลไม่ได้เรียง ก็จะใช้ Binary Search ไม่ได้เช่นกัน

D : ของ D การทายเลขสองหลักเหมือนกัน แต่เป็นไบนารี่ สมมติ ตัวเลขที่สุ่มคือ 27 แปลงเป็นไบนารีคือ

001 1011

คำถามแรกคือ เป็นเลขคู่ใช่หรือไม่ > ไม่ใช่ บิตแรกเป็นหนึ่ง
คำถามที่สองคือ บิตที่สองเป็นบิตคู่ใช่หรือไม่ > ไม่ใช่ บิตนี้เป็นหนึ่ง
คำถามที่สาม บิตที่สามเป็นบิตคู่ใช่หรือไม่ > ใช่ บิตนี้เป็นศูนย์
คำถามที่สี่ บิตที่สี่เป็นบิตคู่หรือไม่ > ไม่ใช่ บิตนี้เป็นหนึ่ง
คำถามที่ห้า บิตที่ห้าเป็นบิตคู่หรือไม่ > ไม่ใช่ บิตนี้เป็นหนึ่ง
คำถามที่หก บิตที่หกเป็นบิตคู่หรือไม่ > ใช่ บิตนี้เป็นศูนย์
คำถามที่เจ็ด บิตที่เจ็ดเป็นบิตคู่หรือไม่ > ใช่ บิตนี้เป็นศูนย์

ก็จะได้ 001 1011

:Cr // สมาคมโปรแกรมเมอร์ไทย

เสริมๆอีกคร้าบ

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

แต่ข้อมูลทั้งหมดเนี่ยให้มาเพื่อ "หลอกควาย" คำถามอยู่ที่ โอกาสแพ้ ซึ่งเป็นไบนารี ไม่แพ้ก็ชนะ โอกาสแพ้ 0.5 โอกาสชนะ 0.5 ทั้งสองคนผลัดกันทายจึงมีโอกาสแพ้และชนะเท่ากัน สัดส่วนจำนวนเท่าของความน่าจะเป็นที่คนทายก่อนจะแพ้ ต่อความน่าจะเป็นที่คนทายทีหลังจะแพ้ คือ 0.5/0.5 = 1