เขียนฟังก์ชัน C# หาเลข Fibonacci ลำดับที่ N

ชุดเลข Fibonacci คือลำดับที่แต่ละตัวเป็นผลรวมของ 2 ตัวก่อนหน้า: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

อัลกอริทึมแบบ Iterative (แนะนำ - O(n) Time, O(1) Space)

public static long Fibonacci(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

ตัวอย่างโค้ดสมบูรณ์ (Array-based - ตามต้นฉบับ)

using System;

public class Demo {
    public static void Main(string[] args) {
        Demo g = new Demo();
        int a = g.DisplayFibonacci(7);  // หาตัวที่ 7 (0-indexed: 0,1,1,2,3,5,8)
        Console.WriteLine(a);  // 8
    }

    public int DisplayFibonacci(int num) {
        int n = num - 1;              // แปลงเป็น 0-based index
        int[] val = new int[n + 1];   // Array เก็บค่าทุกตัว
        
        val[0] = 0;  // F(0)
        val[1] = 1;  // F(1)
        
        for (int i = 2; i <= n; i++) {
            val[i] = val[i - 2] + val[i - 1];  // F(n) = F(n-2) + F(n-1)
        }
        
        return val[n];
    }
}

ผลลัพธ์

8

วิธีการอื่นๆ

1. Recursive (เรียกตัวเอง) - O(2^n) ไม่แนะนำสำหรับ n ใหญ่

public static long FibRecursive(int n) {
    if (n <= 1) return n;
    return FibRecursive(n - 1) + FibRecursive(n - 2);
}

2. Recursive with Memoization - O(n) Time, O(n) Space

private static Dictionary _memo = new();

public static long FibMemoized(int n) {
    if (n <= 1) return n;
    if (_memo.TryGetValue(n, out var cached)) return cached;
    
    _memo[n] = FibMemoized(n - 1) + FibMemoized(n - 2);
    return _memo[n];
}

3. Iterator (yield return) - สร้าง Sequence

public static IEnumerable FibonacciSequence() {
    long a = 0, b = 1;
    while (true) {
        yield return a;
        (a, b) = (b, a + b);  // Tuple deconstruction
    }
}

// ใช้งาน
var first10 = FibonacciSequence().Take(10).ToList();
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

4. Matrix Exponentiation - O(log n) Time

public static long FibFastDoubling(int n) {
    (long a, long b) = FibPair(n);
    return a;
}

private static (long, long) FibPair(int n) {
    if (n == 0) return (0, 1);
    
    var (a, b) = FibPair(n >> 1);  // n/2
    long c = a * (2 * b - a);
    long d = a * a + b * b;
    
    if ((n & 1) == 1)  // n odd
        return (d, c + d);
    else
        return (c, d);
}

Benchmark Comparison (n = 50)

ข้อควรระวัง

• Overflow: int ทนได้ถึง F(46) = 1,836,311,903 ใช้ long (ถึง F(92)) หรือ BigInteger สำหรับค่ามาก
• Indexing: ชัดเจนว่า 0-based (F(0)=0) หรือ 1-based (F(1)=1)
• Negative n: ให้ Return 0 หรือ Throw Exception

BigInteger Version (Unlimited Size)

using System.Numerics;

public static BigInteger FibBig(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    BigInteger a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        (a, b) = (b, a + b);
    }
    return b;
}