การเขียนโปรแกรมแก้ปัญหา "โจทย์รูปทรงสมมาตร"
ผมรู้จักมันในสิ่งที่ผมเรียกว่า "โจทย์ดาว"
คิดว่าทุกคนน่าจะได้เรียนตอนที่เรียน Nested Loop ในวิชา Computer Programming
** xCenter และ yCenter ไม่จำเป็นต้องมีค่าเท่ากัน เช่นในรูปด้านบน
รูปที่ 1 นั้นจะเห็นว่า ผมเลือก Center คือ xCenter = 3, yCenter = 0
อย่างรูปแรก Input คือ 4 ... แต่ n ที่เราเอามาใช้ จะเป็น 7 นะครับ โดยนับแนวตั้ง (ให้ใช้ด้านที่มากกว่า)
ซึ่งข้อนี้การทำแปลง Input ก็เหมือนเดิมคือ n + (n-1) ...
ซึ่งเป็นสิ่งทีผมไม่ชอบเอามากๆ ... แต่โจทย์จำพวกนี้เรามักจะเจอใน "คอมพิวเตอร์ โอลิมปิค"
และในวันนี้ผมก็ขอหยิบโจทย์หนึ่งใน "การแข่งขันคอมพิวเตอร์ โอลิมปิค" (ลืมปี)
ที่มีชื่อว่า "ฝุ่นธุลีล้อมดาว"
พร้อมกับ Algorithm ที่ผมได้มาจากท่านอาจารย์คนหนึ่งนั่นคือ อาจารย์ภิญโญ แท้ประสาทสิทธิ์
อาจารย์ประจำภาควิชาคอมพิวเตอร์ มหาวิทยาลัยศิลปากร
ซึ่ง Algorithm นี้สามารถนำไปประยุกต์ใช้กับ "โจทย์ดาว" ที่เป็น "รูปทรงสมมาตร" ได้หลายๆ อันเลย
(ณ ตอนนี้ผมไม่มีโจทย์อยู่ในมือ เลยอาจจะได้แค่ 3 - 4 ข้อ)
ว่ากันต่อโจทย์ "ฝุ่นธุลีล้อมดาว" ที่ผมกล่าวถึงเนี่ยจะมีลักษณะ input และ output เป็นแบบนี้ครับ
เรามาดูเรื่องของ Algorithm กันก่อนนะครับ (อาจจะในภาษาที่ผมเข้าใจ)
ขั้นแรกให้วาดตารางครอบคลุมปัญหาย่อยๆ ของเราก่อน
ในที่นี้ผมเลือก Input เป็น 3 เราจะนับจำนวนได้ด้านละ 5 ช่อง
โดยถ้าดูแบบ Array 2 มิติ เราจะได้ว่า ช่องที่ซ้ายบนสุดคือ x = 0, y = 0 นะครับ
Algorithm นี้เป็น Algorithm ที่เราจะคิดสร้าง "รูปทรงสมมาตรจากจุดกึ่งกลาง"
จากนั้นเราก็ต้องหาค่า "Center" ให้เจอ ในที่นี้คือจุดที่ xCenter = 2, yCenter = 2
จากนั้นลองไล่ดูนะครับ จะพบว่า
"ผลรวมของระยะห่างจาก Center ของ x และ y มีค่าไม่เกิน
'ค่าของจุดกึ่งกลาง' ของรูปเลย"
ซึ่งระยะห่างจาก Center ของค่า x และ y มีค่าเท่ากับ
ค่าสัมบูรณ์ (Absolute) ของ (x - xCenter) และ (y - yCenter)
และจะเห็นว่า เมื่อค่า x และ y วนไปจนเป็น 2 ทั้งคู่ให้แสดงตัว * (Asterisk) ออกมา
และเนื่องจาก Input เป็น 3 แต่ถ้า Input เป็น 3 เราต้องการ n ที่เป็น 5 เพื่อแก้โจทย์นี้
ก็ไม่ยากครับ บวกตัวมันเองด้วย n-1 ซะเลย (วิธีที่ง่ายที่สุด และได้ผล)
ปัญหาคือเราต้องคิดให้ออกว่า "เราจะทำให้ Input นั้น Flexible กับรูปแบบของ Algorithm ได้อย่างไร"
ซึ่งโจทย์แต่ละแบบก็ต่างกันไป ...
และขอย้ำอีกครั้งการใช้ Algorithm นี้สิ่งที่สำคัญคือ "หา Center ให้เจอ"
จากที่ผมพิมพ์ไปทั้งหมด ทำให้ได้ Code ภาษา C++ แบบนี้มาครับ
ผมได้นำ Algorithm นี้ไป Solve อีกหลายปัญหาดังนี้ครับ
** xCenter และ yCenter ไม่จำเป็นต้องมีค่าเท่ากัน เช่นในรูปด้านบน
รูปที่ 1 นั้นจะเห็นว่า ผมเลือก Center คือ xCenter = 3, yCenter = 0
อย่างรูปแรก Input คือ 4 ... แต่ n ที่เราเอามาใช้ จะเป็น 7 นะครับ โดยนับแนวตั้ง (ให้ใช้ด้านที่มากกว่า)
ซึ่งข้อนี้การทำแปลง Input ก็เหมือนเดิมคือ n + (n-1) ...
ขอจบ Blog นี้เพียงเท่านี้นะครับ สั้นๆ
Comments
Post a Comment