棒の切り分け

棒の切り分け

問題

長さn[cm]の一本の棒を1[cm]単位に切り分ける。 ただし、一本の棒を一度に切れるのは一人だけ。 最大m人がいるとき、最短何回で切り分けられるか。

考え方

1回毎に以下の条件を考える。
* n本切り分けが完了していたら終了。
* 切り分け可能な木の棒がm以下である場合、すべての棒を切り分けることができる。
* 切り分け可能な木の棒がm以上である場合、m本だけ棒を切り分けることができる。

コード

using System;

namespace pazzle_q04
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("{0}", cutDown(20, 3, 1));
            Console.WriteLine("{0}", cutDown(100, 5, 1));
        }

        static int cutDown(int n, int m, int cutNum)
        {
            if(cutNum > n)
            {
                return 0;
            }else if(cutNum < m)
            {
                return (1 + cutDown(n, m, cutNum * 2));
            }else
            {
                return (1 + cutDown(n, m, cutNum + m));
            }
        }
    }
}

その他

 CutDown再帰的に呼び出している。

リンク

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

リンク2

ちなみに、これはYahooのリンクです。

っということで、Markdown記法も勉強してみましたよっと。

広告を非表示にする