動的計画法のテスト

会場案内計画 / rch850

　フィボナッチ数列の40項目まで求めるのにかかった時間は

再帰　00:00:04.7146788
動的　00:00:00.0001436

動的計画法、圧倒的大差で勝利である。

　以下ソースとか。

using System;
using System.Diagnostics;

namespace Fibonacci_number
{
    class Program
    {
        static void Main(string[] args)
        {
            fib f = new fib();

            //フィボナッチ数列を再帰と動的計画法それぞれで40項めを求める
            Debug.WriteLine(f.Recursion(40));
            Debug.WriteLine(f.DP(40));
        }
    }

    //フィボクラス
    class fib
    {
        //ストップウォッチ
        Stopwatch sw = new Stopwatch();

        /// <summary>
        /// 再帰のやつ
        /// </summary>
        /// <param name="n">求める項</param>
        /// <returns>処理時間</returns>
        public String Recursion(int n)
        {
            sw.Reset();
            sw.Start();
            recursion(n);
            sw.Stop();

            return sw.Elapsed.ToString();
        }

        /// <summary>
        /// 動的計画法のやつ
        /// </summary>
        /// <param name="n">求める項</param>
        /// <returns>処理時間</returns>
        public String DP(int n)
        {
            sw.Reset();
            sw.Start();
            dp(n);
            sw.Stop();

            return sw.Elapsed.ToString();
        }

        /// <summary>
        /// 再帰の中身
        /// </summary>
        /// <param name="n">求めるアレ</param>
        /// <returns>アレ</returns>
        private int recursion(int n)
        {
            if (n == 0) return 0;
            if (n == 1) return 1;

            return this.recursion(n - 1) + this.recursion(n - 2);
        }

        /// <summary>
        /// 動的何とかの中身
        /// </summary>
        /// <param name="n">項</param>
        private void dp(int n)
        {
            int[] memo = new int[n + 1];
            memo[0] = 0;
            memo[1] = 1;
            for(int i = 2; i <= n; i++)
            {
                memo[i] = memo[i - 1] + memo[i - 2];
            }
        }

    }
}