Q04 棒の切り分け

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        DeriveCnt(8, 3);
        DeriveCnt(20, 3);
        DeriveCnt(100, 5);
    }

    //NとMを引数として、回数を求める
    static void DeriveCnt(int pN, int pM)
    {
        var BouList = new List<int>() { pN };
        int AnswerCnt = 0;

        while (BouList.Count > 0) {
            AnswerCnt++;

            //切り分け対象Indの上限
            int TargetIndUB = Math.Min(pM - 1, BouList.Count - 1);

            for (int I = 0; I <= TargetIndUB; I++) {
                //半分に切り分けした2つの棒をAdd
                int BouLen = BouList[I];
                int HalfLen = BouLen / 2;
                BouList.Add(HalfLen);
                BouList.Add(BouLen % 2 == 1 ? HalfLen + 1 : HalfLen); //奇数なら余りを加算
            }
            //切り分け前の棒をRemove
            BouList.RemoveRange(0, TargetIndUB + 1);

            //長さ1の棒をRemove
            BouList.RemoveAll(X => X == 1);

            //降順にソート
            BouList.Sort((A, B) => B.CompareTo(A));
        }
        Console.WriteLine("棒の長さ{0}、人の数={1}での回数={2}", pN, pM, AnswerCnt);
    }
}

実行結果

棒の長さ8、人の数=3での回数=4
棒の長さ20、人の数=3での回数=8
棒の長さ100、人の数=5での回数=22

解説

長い棒から順に、半分に切り分けてます。