คำตอบของทีม
ไม่ได้ส่งคำตอบ
ไม่ได้ส่งคำตอบ
คะแนน + โบนัสทำเร็ว
0.0
0.0
แชร์
ไม่ได้ส่งคำตอบ 
คุณเล่นเกมทายเลขกับเพื่อน โดยเพื่อนจะคิดเลขจำนวนเต็มไว้ในใจ มีค่าที่เป็นไปได้ตั้ง แต่ 1
ถึง 1,000 ในการเล่นเกม คุณจะทายตัวเลข เพื่อนจะบอกว่าเลขนั้นมากไป น้อยไป หรือถูกต้อง
เนื่องจากคุณเรียนเรื่องการค้นหาแบบทวิภาคมา คุณจึงจะใช้ขั้นตอนวิธีดังกล่าว กล่าวคือ ในการทาย คุณจะคิดในใจดังนี้
$\cdot$ ก่อนการทำงานทั้งหมด คุณจะให้ L = 1, R = 1000
$\cdot$ ในการทายแต่ละครั้งคุณจะทายค่า g ซึ่งคำนวณดังนี้
$\quad$ g = floor((L+R)/2)
$\quad$ หมายเหตุ: ฟังก์ชัน floor คือการปัดค่าเป็นจำนวนเต็มโดยการปัดลงเสมอ
$\cdot$ เมื่อทายเสร็จ คุณจะได้รับคำตอบว่า มากไป (too large) น้อยไป (too small) และถูกต้อง ถ้าไม่ได้คำตอบว่าถูกต้อง คุณจะปรับค่าดังนี้
$\quad$ if answer = “too large”
$\quad \quad$R = g – 1
$\quad$ if answer = “too small”
$\quad \quad$L = g + 1
ในกรณีที่แย่ที่สุด ด้วยขั้นตอนวิธีนี้คุณจะต้องถามกี่ครั้ง?
ถึง 1,000 ในการเล่นเกม คุณจะทายตัวเลข เพื่อนจะบอกว่าเลขนั้นมากไป น้อยไป หรือถูกต้อง
เนื่องจากคุณเรียนเรื่องการค้นหาแบบทวิภาคมา คุณจึงจะใช้ขั้นตอนวิธีดังกล่าว กล่าวคือ ในการทาย คุณจะคิดในใจดังนี้
$\cdot$ ก่อนการทำงานทั้งหมด คุณจะให้ L = 1, R = 1000
$\cdot$ ในการทายแต่ละครั้งคุณจะทายค่า g ซึ่งคำนวณดังนี้
$\quad$ g = floor((L+R)/2)
$\quad$ หมายเหตุ: ฟังก์ชัน floor คือการปัดค่าเป็นจำนวนเต็มโดยการปัดลงเสมอ
$\cdot$ เมื่อทายเสร็จ คุณจะได้รับคำตอบว่า มากไป (too large) น้อยไป (too small) และถูกต้อง ถ้าไม่ได้คำตอบว่าถูกต้อง คุณจะปรับค่าดังนี้
$\quad$ if answer = “too large”
$\quad \quad$R = g – 1
$\quad$ if answer = “too small”
$\quad \quad$L = g + 1
ในกรณีที่แย่ที่สุด ด้วยขั้นตอนวิธีนี้คุณจะต้องถามกี่ครั้ง?
เฉลย
ตอบ 10 ครั้ง
คำอธิบาย
ในข้อนี้เราสามารถเขียนโปรแกรมเพื่อทดสอบ จะพบว่า ถ้าเพื่อนคิดเลขในใจเป็น 2, 4, 6 หรือ อีกหลาย ๆ เลข จะพบว่าขั้นตอนวิธีจะต้องถาม 10 ครั้ง
อย่างไรก็ตาม ถ้าเราไม่ต้องการค่าเฉพาะเจาะจง เราอาจจะเริ่มโดยการประมาณก่อน สังเกตว่า ทุกครั้งที่ถาม ขอบเขตของคำตอบที่เป็นไปได้จะลดลงประมาณครึ่งหนึ่ง ดังนั้น ถ้าเราถาม 10 ครั้ง ขอบเขตที่ถามจะลดลงไป 210 = 1024 > 1000 เท่า นั่นคือควรจะเหลือค่าที่เป็นไปได้ค่าเดียว แล้วถ้าต้องการคำตอบที่ละเอียดเราจะค่อย ๆ ไล่พิจารณาจำนวนคำตอบที่เป็นไปได้หลังการถามแต่ละครั้ง จะเป็นดังนี้ 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 → 0 นั่นคือถามทั้งสิ้น 10 ครั้ง