嚼的絮絮叨叨

費氏函數

列印如下的數列。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,..............n

公式為

• a₁ = 1
• a₂ = 1
• a_n = a_{n − 1} + a_{n − 2}

C#的解法通常有陣列跟遞迴。當n越大，陣列的速度遠超過遞迴。而陣列也不過用了array[2]跟1個暫存變數。

(聽說是PG的愛用面試考題)

using System;

using System.Collections.Generic;

using System.Text;

namespace 費氏級數

{

    class Program

    {

        static void Main(string[] args)

        {

            Console.Write("請輸入數字：");

            Int64 n;

            if (Int64.TryParse(Console.ReadLine(), out n))

            {

                //遞迴作法

                Console.WriteLine("遞迴作法");

                for (int i = 0; i < n; i++)

                {

                    Console.Write(foo(i).ToString() + ",");

                }

                Console.WriteLine();

                //陣列作法

                Console.WriteLine("陣列作法");

                Int64[] array = new Int64[] { 0, 1 };

                Int64 tmp = 0;

                for (int i = 0; i < n; i++)

                {

                    if (i == 0 || i == 1)

                        Console.Write(array[i].ToString() + ",");

                    else

                    {

                        tmp = array[0] + array[1];

                        Console.Write(tmp.ToString() + ",");

                        array[0] = array[1];

                        array[1] = tmp;

                    }

                }

                Console.WriteLine();

            }

            else

                Console.WriteLine("不是數字！");

        }

        //遞迴作法

        static Int64 foo(Int64 i)

        {

            if (i == 0 || i == 1)

                return i;

            else

                return foo(i - 1) + foo(i - 2);

        }

    }

}