結城浩先生が出題されたマヨイロード問題に挑戦しました。
問題を知ったのが締め切り後だったため、回答を提出するには至りませんでした。
.NETのバージョンアップや細かい記法の見直しなどを2020年に行いました。
- 実装言語など
- C#
- .NET Core 3.1
※計算時間などを確認するため、出力形式を要件から少し変更しています。
処理が合っているかどうかを確認するために、まとめて処理する list コマンドを作成しました。
# dotnet MayoiRoad.App.dll list 1 15
※一度計算したフィボナッチ数はキャッシュするため、計算時間は正確ではありません。
Time:00:00:00.005348, N:1, P:2
Time:00:00:00.000003, N:2, P:2
Time:00:00:00.000417, N:3, P:7
Time:00:00:00.000002, N:4, P:7
Time:00:00:00.000003, N:5, P:20
Time:00:00:00.000003, N:6, P:20
Time:00:00:00.000003, N:7, P:54
Time:00:00:00.000003, N:8, P:54
Time:00:00:00.000063, N:9, P:143
Time:00:00:00.000004, N:10, P:143
Time:00:00:00.000004, N:11, P:376
Time:00:00:00.000032, N:12, P:376
Time:00:00:00.000007, N:13, P:986
Time:00:00:00.000010, N:14, P:986
Time:00:00:00.000006, N:15, P:2583今思うと、XUnitでケース作成すればこの機能は不要でした。
# dotnet MayoiRoad.App.dll calc 2015
Time:00:00:00.006264, N:2015, P:24410294683171395267259945469996127000411199333760853190535535281681195871429510314079442068798555059453792431772087225245168879580469159794544170936403149540819320510882801573596907938222922817134288725100817648047405608500267748766714030468003650259685406411646787207097050545802045736020993909154298598218721111963426993884619351338577630868510716463423585020972878819198991971234596733617320373133963970742975210614208問題文から、まずは法則を探しました。あれこれ考えて、フィボナッチ数列は比較的早く見つけることができました。
実装上では、同じフィボナッチ数の計算が何度も出現することに気づいたため、キャッシュして処理時間が短くなるようにしました。
何とか本題（N=2015）でも1秒を切ることができました。
2020 - @ushibutatory