棒の切り分け
棒の切り分け
問題
長さ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
を再帰的に呼び出している。
リンク2
ちなみに、これはYahooのリンクです。
っということで、Markdown記法も勉強してみましたよっと。