static void Main(string[] args)
{

    //斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
    //指的是这样一个数列：1、1、2、3、5、8、13、21、34、……，这个数列从第3项开始，每一项都等于前两项之和。
    //递推公式：F(n)=F(n-1)+F(n-2)
    //求第30个数是什么？

    int n = 30;
    
    //方法一：递归解决，递归时存在重复计算的情况，所以当 N 超过50时就会出现很慢的情况，性能不好。
    Console.WriteLine(Fib_1(n));
        
    //方法二：数组解决，保存计算结果，避免重复计算，性能比上面递归解决方案好。
    Console.WriteLine(Fib_2(n));
        
    //方法三：循环解决，不需要操作数组，性能比上面数组解决方案好。
    Console.WriteLine(Fib_3(n));
            
    Console.ReadKey();
}

//方法一：递归解决，递归时存在重复计算的情况，所以当 N 超过50时就会出现很慢的情况，性能不好。
static int Fib_1(int num)
{
    if (num <= 0)
        return 0;
    else if (num >= 1 && num <= 2)
        return 1;
    else
        return Fib_1(num - 1) + Fib_1(num - 2);
}

//方法二：数组解决，保存计算结果，避免重复计算，性能比上面递归解决方案好。
static long Fib_2(int num)
{
    if (num <= 0)
    {
        return 0;
    }
    else if (num >= 1 && num <= 2)
    {
        return 1;
    }
    else
    {
        long[] arr = new long[num];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < num; i++)
        {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[num - 1];
    }
}

//方法三：循环解决，不需要操作数组，性能比上面数组解决方案好。
static long Fib_3(int num)
{
    long last = 1;
    long nextLast = 1;
    long result = 0;
    for (int i = 2; i < num; i++)
    {
        result = last + nextLast;
        nextLast = last;
        last = result;
    }
    return result;
}