Q15 幅優先の二分木を深さ優先探索

PHPのソース

<?php
Solve(  10,   6);
Solve(  10,   8);
Solve(3000,2500);

//mとnを引数として解を求める
function Solve($pM , $pN)
{
    $VisitedArr = array();

    $Stk = new SplStack();
    $Stk->push(1);

    while($Stk->isEmpty() == false){
        $Popped = $Stk->pop();

        $VisitedArr[] = $Popped;
        if(count($VisitedArr) == $pN){
            printf('m=%d,n=%dでの解は、%d',$pM,$pN,$Popped);
            //var_export($VisitedArr);
            echo PHP_EOL;
            return;
        }

        $NextNode1 = $Popped * 2;
        $NextNode2 = $NextNode1 + 1;

        if($NextNode2 <= $pM) $Stk->push($NextNode2);
        if($NextNode1 <= $pM) $Stk->push($NextNode1);
    }
}

実行結果

m=10,n=6での解は、5
m=10,n=8での解は、3
m=3000,n=2500での解は、897

解説

幅優先の二分木が存在すると仮定して、
深さ優先探索してます。