การเขียนโปรแกรมแก้ปัญหา "โจทย์รูปทรงสมมาตร"

ผมรู้จักมันในสิ่งที่ผมเรียกว่า "โจทย์ดาว"
คิดว่าทุกคนน่าจะได้เรียนตอนที่เรียน Nested Loop ในวิชา Computer Programming
ซึ่งเป็นสิ่งทีผมไม่ชอบเอามากๆ ... แต่โจทย์จำพวกนี้เรามักจะเจอใน "คอมพิวเตอร์ โอลิมปิค"

และในวันนี้ผมก็ขอหยิบโจทย์หนึ่งใน "การแข่งขันคอมพิวเตอร์ โอลิมปิค" (ลืมปี)
ที่มีชื่อว่า "ฝุ่นธุลีล้อมดาว"

พร้อมกับ 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 นี้เพียงเท่านี้นะครับ สั้นๆ

Popular posts from this blog

[Android Dev] การติดตั้ง Eclipse+AndroidSDK เพื่อพัฒนาโปรแกรมบน Android

12 วิธี การบริการและดูแลลูกค้าในร้าน Starbucks

5 TED Talk ที่จะช่วยให้คุณทำงานดีขึ้น