剣指offer--カエルがjavaScriptを踊る実現
1303 ワード
1匹のカエルは一度に1段の階段を飛び上がることができて、2段も飛び上がることができます.このカエルが1つのn級の階段を飛び上がるのが全部で何種類の跳び方があることを求めます(前後の順序が異なって異なる結果を計算します).
解析:まずジャンプの最小回数(n/2)を見つけ,可能なジャンプの回数はn/2~nであり,回数が1を足すごとに1段のステップの数が2を足す場合,数学的な配列の組合せを用いて異なる回数に対応するどの程度のジャンプ法を計算することができるか(組合せC規則に合致する).同時にnが奇数か偶数かを分けて議論する.
解析:まずジャンプの最小回数(n/2)を見つけ,可能なジャンプの回数はn/2~nであり,回数が1を足すごとに1段のステップの数が2を足す場合,数学的な配列の組合せを用いて異なる回数に対応するどの程度のジャンプ法を計算することができるか(組合せC規則に合致する).同時にnが奇数か偶数かを分けて議論する.
function jumpFloor(number)
{
// write code here
//
var min=Math.ceil(number/2);
var i=min,j=0;
var type=0;
if(number%2==0){
while(i<=number){
type+=combination(i,j);
i=i+1;
j=j+2;
}
}else{
j=1;
while(i<=number){
type+=combination(i,j);
i=i+1;
j=j+2;
}
}
return type;
}
// ( C)
function combination(m,n){
return factorial(m,n)/factorial(n,n);// Cmn( n, m) = Amn( n, m)/Ann( n)
}
// , n , m , 1, factorial(5,4) 5*(5-1)*(5-2)*(5-3), 4
function factorial(m,n){
var num = 1;
var count = 0;
for(var i = m;i > 0;i--){
if(count == n){// , for
break;
}
num = num * i;
count++;
}
return num;
}