โอ้ววว…. วันนี้สอบ Algorithm Design ครับ

เป็นการสอบ midterm ครั้งที่ 1 ครับ (midterm สอบ 2 ครั้ง) ครั้งนี้เป็นการสอบที่เตรียมตัวถือว่าน้อยมาก ไม่แน่ใจเหมือนกันว่าเป็นเพราะอะไร แต่เอาเป็นว่ามันก็ผ่านไปแล้ว

จากใจลึกๆ แล้วผมชอบวิชานี้นะครับ (อาจารย์มะนาว แอบดีใจ แฮ่ๆ) เป็นวิชาที่ว่าด้วยกระบวนการคิดต่างๆ นานา ที่สามารถจะเอาไปใช้ได้จริง ในชีวิตประจำวัน

คุณเชื่อหรือไม่ ว่าคุณคิด Algorithm อยู่ตลอดเวลา?

แล้ว Algorithm คืออะไร?

Algorithm พูดง่ายๆ ก็คือ วิธีคิด ฉะนั้น Algorithm Design ก็คือ การออกแบบวิธีคิด

คุณเคยประสบปัญหานี้หรือไม่
“พักเที่ยง 1 ชั่วโมง มีงานต้องทำ 4 อย่าง คือ ไปโอนเงินที่ธนาคาร ไปถ่ายเอกสาร ไปกินข้าว ไปหาอาจารย์”
ที่ยกตัวอย่างนี้เพราะว่า น่าจะเป็นปัญหาที่ใกล้ตัวมากที่สุด (รึปล่าว)

จริงๆ มีปัญหาอีกมากมายเลย แต่วิชานี้ต้องคิดอะไรมากๆ คิดรอบคอบ ยากจิงๆ

ความยากของวิชานี้อยู่ตรงไหน
- เข้าใจโจทย์ (ใช้เวลาเยอะมาก)
- หาวิธีคิด
- พิสูจน์ให้ได้ว่าวิธีของเราถูกต้อง (ยากจริงๆ)
- ต้องใช้เวลาในการทำงานน้อยที่สุด

วันนี้ผมทำไม่ทันครับ ทำไปเพียง 4 ข้อเท่านั้น (จาก 6 ข้อ) โอ้…
ที่ไม่ทันก็เพราะว่าคิดมากเกินไป คิดรอบคอบเกินไป (ก็ใช่ว่าจะถูก) ที่สำคัญไม่ได้เอานาฬิกาเข้าไป ถึงแม้ว่าจะมีอาจารย์คอยบอกเวลาอยู่เรื่อยๆ
… ยอมรับครับ แต่ผมก็ทำดีที่สุดแล้วครับ … ไว้แก้ตัวสอบครั้งที่ 2 แล้วกัน ฮ่าๆๆ (ปลอบใจตัวเอง)

แต่จริงๆ แล้ว เอนทรี่นี้ไม่ได้ต้องการจะมาอธิบายหรือบ่นเกี่ยวกับวิชานี้ ฮ่าๆๆ
แต่ผมมีเกมมาให้เล่นหนึ่งเกม

** ** ** ** ** ** ** ** ** ** ** ** ** ** **

เกม AB
เรามีรางความยาว 2n+n หน่วย แบ่งเป็นช่องย่อยๆ 2n+2 ช่อง เรามีกล่องสีแดง (แทนด้วยอักษร A) n กล่อง และกล่องสีน้ำเงิน (แทนด้วยอักษร B) อีก n กล่อง กล่องดังกล่าววางอยู่ในแต่งละช่อง ตัวอย่างของสถานะเริ่มเต้นเช่น

| A | B | B | A |  -  |  -  | A | B | A | B |
ให้
| A | คือ ช่องที่มีกล่อง A
| B | คือ ช่องที่มีกล่อง B
|  -  | คือช่องว่าง

สิ่งที่เราต้องการคือ
| A | A | A | A |  -  |  -  | B | B | B | B |

กติกา
สิ่งที่คุณทำได้คือการยกกล่องสองกล่องที่ติดกันไปวางแทนที่ช่องว่าง (โดยห้ามสลับกล่องที่ยกไปวาง)
เป้าหมายของเกมนี้คือ การยกกล่องในวิธีดังกล่าวเพื่อทำให้กล่องสีแดงเรียงติดกันโดยเริ่มจากช่องริ่มสุดทางด้านซ้าย และกล่องสีน้ำเงินเรียงติดกันโดยเริ่มจากกล่องริมสุดทางด้านขวา

โจทย์
ให้หาวิธีการยกกล่องที่ใช้จำนวนครั้งในการยกน้อยที่สุด

ตัวอย่างในการยก
| A | B | B | A |  -  |  -  | A | B | A | B |
| A | B |  -  |  -  | B | A | A | B | A | B |
| A | B | A | A | B |  -  |  -  | B | A | B |
แบบนี้ยกได้

** ** ** ** ** ** ** ** ** ** ** ** ** ** **

- เกมข้างต้น เป็นเกมซึ่งดัดแปลงโดยผมเอง ซึ่งเป็นส่วนหนึ่งของข้อสอบ Midterm ครั้งที่ 1 วิชา Algorithm Design ออกโดย อ.จิตร์ทัศน์ ฝักเจริญผล ภาควิชาวิศวกรรมคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์
- จริงๆ แล้วโจทย์ในข้อสอบ ไม่ได้เป็นแบบนี้ แต่จะคล้ายๆ แบบนี้
- ใครงงโจทย์ทิ้งคำถามไว้ได้นะครับ
- ลองเล่นกันดูนะครับ ขำๆ อย่าไปเครียด

ขอแปะลิงค์อีกนิดนึง
- เว็บไซต์วิชาเรียน
- Algorithm in Wikipedia
- เว็บไซต์วิชาเรียนของจุฬาฯ (น่าจะมีประโยชน์ถ้าได้เอามาอ่าน)

ปล.
- ถ้าเอนทรี่นี้ทำให้ใครปวดหัว ขอโทษด้วยนะครับ ฮ่าๆ
- หยุด 9 วัน  แต่ สอบ 6 วิชา + สอบ SCJP
- จะได้ N82 มั้ยน้อ?