フィボナッチ数列を割と速く算出スル方法(C#)
フィボナッチ数列を割と速く算出スル方法(C#) - Qiita
フィボナッチ数列を求めるアルゴリズムを書くと、普通に挑むとすごい時間がかかってしまいます。(下記のFibonacciクラス)
ちょっとしたキャッシュを入れてやるだけで、n = 139までは割と素早く算出することができます。(下記のFibonacciWithCacheクラス) 139以上は、decimalがoverflowするので、それ以上はC#で普通にやると求められません。
namespace FibonacciOnConsole { class Program { static void Main(string[] args) { var fib = new FibonacciCUI(); fib.Calc(new FibonacciWithCache()); } } }
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); } } }
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