[C#]費氏數列(Fibonacci sequence) 程式邏輯

 定義:

實作:

參數:輸入10

1.依輸入的項目數量顯示數列

  Console.WriteLine("請輸入要顯示的費氏數列項目數量");
            var input = Console.ReadLine();
            //將字串轉為int
            var num = int.TryParse(input, out int output) ? output : 0;
            var a = 0;
            var b = 1;
            Console.WriteLine($"第1項:{b}");
            for (var i = 2; i <= num; i++)
            {
                var temp = a + b;
                Console.WriteLine($"第{i}項:{temp}");
                a = b;
                b = temp;
            }

2.依輸入的項次取得該項次值

static void Main(string[] args)
        {
            Console.WriteLine("請輸入要顯示的費氏數列項目數量");
            var input = Console.ReadLine();
            //將字串轉為int
            var num = int.TryParse(input, out int output) ? output : 0;          
            Console.WriteLine($"遞迴寫法 取得的值:{F(num)}");
            Console.WriteLine($"動態規劃寫法 取得的值:{F(num)}");
            Console.ReadLine();
        }

*遞迴寫法

/// <summary>
        /// 遞迴寫法
        /// </summary>
        /// <param name="n">第幾項</param>
        /// <returns></returns>
        static int F(int n)
        {
            if (n <= 2)
            {
                return 1;
            }
            return F(n - 1) + F(n - 2);
        }

*動態規劃寫法

  /// <summary>
        /// 動態規劃寫法
        /// </summary>
        /// <param name="n">第幾項</param>
        /// <returns></returns>
        static int DynamicF(int n)
        {
            if (n <=2)
            {
                return 1;
            }
            int[] array = new int[n];
            array[0] = 1;
            array[1] = 1;
            for(var i=2;i<n;i++)
            {
                array[i] = array[i-1]+ array[i - 2];
            }
            return array[n - 1];

        }

ps:這邊要介紹「遞迴寫法」與「動態規劃寫法」的原因是因為在輸入的項目數量越大的話會有效能上的顯著差異。

實際上的原因是因為「遞迴寫法」會重複計算許多之前已經計算過且知道答案的值，而「動態規劃寫法」會將我們已經計算過的結果儲存起來，因此在「時間複雜度(Time Complexity)」上會隨著input的值越大，成指數上的差異。