フィボナッチ数列を割と速く算出スル方法(C#)
フィボナッチ数列を求めるアルゴリズムを書くと、普通に挑むとすごい時間がかかってしまいます。(下記のFibonacciクラス)
ちょっとしたキャッシュを入れてやるだけで、n = 139までは割と素早く算出することができます。(下記のFibonacciWithCacheクラス)
139以上は、decimalがoverflowするので、それ以上はC#で普通にやると求められません。
Program.cs
namespace FibonacciOnConsole
{
class Program
{
static void Main(string[] args)
{
var fib = new FibonacciCUI();
fib.Calc(new FibonacciWithCache());
}
}
}
FibonacciCUI.cs
using System;
using System.Diagnostics;
namespace FibonacciOnConsole
{
public class FibonacciCUI
{
public void Calc(IFibonacciStrategy strategy)
{
ConsoleKeyInfo cki;
Console.TreatControlCAsInput = true;
do
{
Console.WriteLine("Please input fibonacci number.");
Console.WriteLine("Press ESC key if you want to finish this console.");
var inputtedString = Console.ReadLine();
var inputtedNum = default(decimal);
if (decimal.TryParse(inputtedString, out inputtedNum))
{
inputtedNum = (inputtedNum >= 139) ? 139 : inputtedNum;
Console.WriteLine("Begin process.");
for (decimal i = 0; i < inputtedNum; i++)
{
var sw = new Stopwatch();
sw.Start();
var ret = strategy.Calc(i);
sw.Stop();
var ts = sw.Elapsed;
Console.WriteLine(string.Format("{0, 4} Fibonacci={1, 30} Time:{2}", i, ret, ts));
}
Console.WriteLine("End process.");
}
else
{
Console.WriteLine("Please input number.");
}
cki = Console.ReadKey();
Console.Clear();
} while (cki.Key != ConsoleKey.Escape);
}
}
}
Fibonacci.cs
using System.Collections.Generic;
namespace FibonacciOnConsole
{
public interface IFibonacciStrategy
{
decimal Calc(decimal i);
}
public class Fibonacci : IFibonacciStrategy
{
public decimal Calc(decimal i)
{
if( i == 0 )
{
return 0;
}
if( i == 1 )
{
return 1;
}
return Calc(i - 1) + Calc(i - 2);
}
}
public class FibonacciWithCache : IFibonacciStrategy
{
Dictionary<decimal, decimal> _cache = new Dictionary<decimal, decimal>();
public decimal Calc(decimal i)
{
if (i == 0)
{
return 0;
}
if (i == 1)
{
return 1;
}
decimal cachedValue = 0;
if (_cache.TryGetValue(i, out cachedValue))
{
return cachedValue;
}
var ret = Calc(i - 1) + Calc(i - 2);
_cache.Add(i, ret);
return ret;
}
}
}
再帰の場合、処理時間を考慮する必要はありますね。
GitHubにもあげてあります。
https://github.com/Koki-Shimizu/Fibonacci.git
Author And Source
この問題について(フィボナッチ数列を割と速く算出スル方法(C#)), 我々は、より多くの情報をここで見つけました https://qiita.com/Koki_jp/items/756a26a04a6ccfbf8d78著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .