Algorithm (อัลกอริทึม) คืออะไร?
ชุดคำสั่งที่จำกัด (Finite) ซึ่งถ้าปฏิบัติตามจะทำภารกิจเฉพาะได้ ต้องผ่านเกณฑ์ 5 ข้อ:
- Input: มี Input 0 หรือมากกว่า จากชุดที่กำหนด
- Output: มี Output 1 หรือมากกว่า เกี่ยวข้องกับ Input
- Definiteness: แต่ละขั้นตอนชัดเจน ไม่คลุมเครือ
- Finiteness: ต้องจบภายในขั้นตอนจำกัด
- Effectiveness: ทุก Operation ทำได้จริงในเวลาจำกัด
วิธีแสดงอัลกอริทึม
- Natural Language: ภาษาธรรมชาติ (ไทย/อังกฤษ) - เข้าใจง่าย แต่อาจคลุมเครือ
- Flowcharts: แผนผังไหล - เหมาะอัลกอริทึมเล็ก/เรียบง่าย
- Pseudocode: รหัสเทียม - ใกล้โค้ดจริง ไม่ผูกภาษา ไม่มี Syntax เหนื่อย
ตัวอย่าง: อัลกอริทึมคำนวณ Factorial
Step 1: Input number n Step 2: final ← 1 Step 3: final ← final × n Step 4: n ← n - 1 Step 5: If n = 0 goto Step 8 Step 6: Else goto Step 3 Step 7: (Loop back) Step 8: Print final
Recursive Algorithms (อัลกอริทึมแบบเวียนเกิด)
ฟังก์ชันเรียกตัวเอง โดยส่งค่ากลับเป็น Parameter ใหม่ Parameter = Input, Return Value = Output
หลักการ: แบ่งปัญหาใหญ่เป็น Sub-problems ลักษณะเดียวกัน ผลลัพธ์ของ Recursion หนึ่งเป็น Input ของอันถัดไป เรียกตัวเองด้วย Input ที่เล็กลงเรื่อยๆ จนถึง Base Case
ตัวอย่าง: Factorial แบบ Recursive
int factorial(int n) {
if (n <= 1) return 1; // Base Case
return n * factorial(n-1); // Recursive Step
}
ตัวอย่างอื่นๆ ของ Recursive Algorithms
- Fibonacci Series
- Tower of Hanoi
- Tree/Graph Traversal (DFS)
- Quick Sort, Merge Sort
ข้อควรระวัง
- ต้องมี Base Case ชัดเจน ไม่อาจ Infinite Recursion
- อาจใช้ Stack Memory มาก (Stack Overflow) → พิจารณา Iterative Version
- บางกรณีต้องใช้ Memoization/Dynamic Programming ป้องกันการคำนวณซ้ำ
