「棒を切る」をErlangで

最強最速アルゴリズマー養成講座:トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター に出てきた 棒を切る問題 が自力で解けたので、記念にアップします。

毎日お風呂に入りながら考えて2週間くらいかかりました (遅すぎ (^^;))

自分で後で見てコードの意味がわかるように解説:

  • 与えられた最大切断数以下の回数で棒を切る関数cutと、cutを呼び出しながら最適な切断長さを探す関数findでできています。
  • findは長さの上限(H)と下限(L)を持ち、その中央の値(M)でcutを呼び出します。
  • cutの結果、中央の値(M)以上の長さを持つ棒がK本以上あったら、もっと長く取れると判断して下限(L)を中央の値(M)に引き上げます。
  • 反対にK本以上なかったら、もっと短くする必要があると判断して上限(H)を中央の値(M)に引き下げます。

今回の問題で、上限と下限の範囲を狭めて探索していく方法を学びました。あと、Erlangでは変数名を1文字にするとすっきり書けることがわかりました。頭がだいぶ関数型に慣れてきたようです。