แบบฝึกทักษะ
(8)
8.
เมืองเมืองหนึ่งได้จัดวางผังเมืองเป็นรูปสี่เหลี่ยมผืนผ้า
มีถนนตัดกันเป็นมุมฉาก ดังรูป
ถ้าต้องการเดินทางจากจุด A
ไปจุด B โดยมีเงื่อนไขว่าให้เลือกไปทางทิศเหนือหรือทิศตะวันออกได้เท่านั้น จะมีเส้นทางที่แตกต่างกันทั้งหมดกี่เส้นทาง เช่น
จากจุด M ไปจุด B มี 3
เส้นทาง คือ (1) เหนือ–เหนือ–ตะวันออก , (2) เหนือ–ตะวันออก–เหนือ และ (3) ตะวันออก–เหนือ–เหนือ
ข้อ 8 ตอบ การเดินทางจากจุด A ไปจุด B มีเส้นทางให้เลือกทั้งหมด 70
เส้นทาง
แนวคิด ใช้ยุทธวิธีคิดย้อนกลับ จากจุดสิ้นสุด
B กลับไปจุดเริ่มต้นที่จุด A โดยจะพิจารณาจุดที่เป็นสามแยกหรือสี่แยกเพราะเป็นจุดที่ทำให้เกิดทางเลือก
ตามเงื่อนไขที่ว่าเลือกทางเดินได้เฉพาะไปทิศเหนือ
หรือไปทิศตะวันออกเท่านั้น
เราจะดูว่าจากจุดสามแยกหรือสี่แยกต่างๆ
นั้น มีเส้นทางให้เลือกเดินทางมาที่จุด B ได้กี่เส้นทาง โดยจะเริ่มพิจารณาจุดที่อยู่ใกล้จุด B มากที่สุดก่อน ดังนี้
จะเห็นได้ว่าจากจุด
C ไปจุด B มี 1 เส้นทาง
จากจุด D
มี 2 เส้นทาง และจากจุด E มี 1
เส้นทาง
พิจารณาต่อไป
จากจุด F มี 1
เส้นทาง จากจุด G มี 3 เส้นทาง จากจุด H มี 6
เส้นทาง จากจุด I มี 3
เส้นทาง และ จากจุด J มี 1
เส้นทาง
จะสังเกตเห็นได้ว่าจำนวนเส้นทางจากจุด
H จะเท่ากับผลบวกของจำนวนเส้นทางจากจุด
G และจุด I ซึ่งจะเกิดในลักษณะเดียวกันนี้กับจุดอื่นๆ
ด้วย และเมื่อพิจารณาย้อนกลับไปจนถึงจุด A จะได้ผลดังรูป
q
ปัญหาข้อนี้สามารถคำนวณได้โดยใช้ความรู้เรื่อง วิธีเรียงสับเปลี่ยน ( Permutation )
ไม่มีความคิดเห็น:
แสดงความคิดเห็น