Fibonacci Series ใน C# - แสดงลำดับฟีโบนัชชี

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

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

public static void PrintFibonacci(int n) {
    if (n <= 0) return;
    
    long a = 0, b = 1;
    
    Console.Write(a);
    if (n == 1) { Console.WriteLine(); return; }
    
    Console.Write(" " + b);
    
    for (int i = 2; i < n; i++) {
        long c = a + b;
        Console.Write(" " + c);
        a = b;
        b = c;
    }
    Console.WriteLine();
}

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

using System;

public class Demo {
    public static void Main(string[] args) {
        int val1 = 0, val2 = 1, val3, i, n;
        n = 7;  // แสดง 7 ตัวแรก
        
        Console.WriteLine("Fibonacci series:");
        Console.Write(val1 + " " + val2 + " ");  // 0 1
        
        for (i = 2; i < n; ++i) {
            val3 = val1 + val2;   // Next = Sum of previous 2
            Console.Write(val3 + " ");
            val1 = val2;          // Shift
            val2 = val3;
        }
    }
}

ผลลัพธ์

Fibonacci series: 0 1 1 2 3 5 8

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

1. ใช้ Iterator (yield return) - Lazy Evaluation

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

// ใช้งาน - เอา 10 ตัวแรก
foreach (var num in FibonacciSequence().Take(10)) {
    Console.Write(num + " ");  // 0 1 1 2 3 5 8 13 21 34
}

2. Recursive (ไม่แนะนำ - O(2^n))

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

// แสดง Series
for (int i = 0; i < 10; i++) {
    Console.Write(FibRecursive(i) + " ");
}

3. Recursive with Memoization (O(n))

private static Dictionary _memo = new();

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

4. Matrix Exponentiation / Fast Doubling (O(log n))

public static long FibFast(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);
    long c = a * (2 * b - a);
    long d = a * a + b * b;
    return (n & 1) == 1 ? (d, c + d) : (c, d);
}

BigInteger สำหรับเลขใหญ่ (Unlimited)

using System.Numerics;

public static IEnumerable BigFibonacci() {
    BigInteger a = 0, b = 1;
    while (true) {
        yield return a;
        (a, b) = (b, a + b);
    }
}

// 100th Fibonacci Number (354224848179261915075)
var fib100 = BigFibonacci().Skip(100).First();
Console.WriteLine(fib100);

Indexing Note: 0-based vs 1-based

Overflow Limits

Best Practice

• ใช้ **Iterative Loop** สำหรับการพิมพ์ Series (Simple, Fast, O(1) Space)
• ใช้ **Iterator (yield)** สำหรับ Sequence Processing / LINQ Integration
• ใช้ **Fast Doubling** สำหรับ Single Large Index (O(log n))
• ใช้ **BigInteger** เมื่อ n > 92
• หลีกเลี่ยง Naive Recursive สำหรับ n > 40