TQC+ C# 認證教學手冊

406、費式數列

☑易 ☐中 ☐難

費式數列如何計算?

0  1  1  2  3  5  8  13  21  34  55  89
  • 0 + 1 = 1
  • 1 + 1 = 2
  • 1 + 2 = 3
  • 2 + 3 = 5
  • ...
  • 34 + 55 = 89

程式怎麼寫?

方法:利用陣列與迴圈!

先初始陣列的前兩個數值。

fib[0] = 0;
fib[1] = 1;

利用 for 迴圈完成剩下的數值計算。

fib[2] = fib[0] + fib[1];

將索引值改為用計算方式求得。

fib[2] = fib[2 - 2] + fib[2 - 1];

因此可以用迴圈來處理:

fib[i] = fib[i - 2] + fib[i - 1];

實作方式

  1. Cache

  2. On-demand

  3. Mix (Cache + On-demand)

注意數值型態的上限

  • int
  • Int16
  • Int32
  • Int64
  • UInt16
  • UInt32
  • UInt64

參考程式碼

Program.cs

using System;

namespace CSD04
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { 1, 5, 7, 11, 50 };

            long[] fib = new long[60];

            fib[0] = 0;
            fib[1] = 1;

            for (int i = 2; i < fib.Length; i++)
            {
                fib[i] = fib[i - 2] + fib[i - 1];
            }

            for (int i = 0; i < nums.Length; i++)
            {
                Console.WriteLine("Fibonacci Number at {0} is {1}",
                    nums[i], fib[nums[i]]);
            }

            Console.ReadLine();
        }
    }
}

參考程式碼 v2

using System;

namespace CSD04
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { 1, 5, 7, 11, 50 };

            for (int i = 0; i < nums.Length; i++)
            {
                Console.WriteLine("Fibonacci Number at {0} is {1}",
                    nums[i], fib(nums[i]));
            }

            Console.ReadLine();
        }

        static long fib(int n)
        {
            if (n == 0)
            {
                return 0;
            }
            if (n == 1)
            {
                return 1;
            }

            long[] fib = new long[n + 1];

            fib[0] = 0;
            fib[1] = 1;

            for (int i = 2; i < fib.Length; i++)
            {
                fib[i] = fib[i - 2] + fib[i - 1];
            }

            return fib[n];
        }
    }
}