階乗
Factorial
階乗はすぐに巨大な数になってしまうので計算が難しい。→多倍長演算 組み合わせの数を計算するときに多用される。
数が少ないなら、固定値なので表にした方がよい。
$ 0! = 1であることに注意。
組み合わせの数などで使う時、数学的には正しいが、階乗をそのまま計算するのは効率が悪い。
$ \binom{n}{k} = {}_n \mathrm{C}_k = \frac{n!}{(n-k)!k!}
このまま$ n!、$ (n-k)!、$ k!を計算してから乗算除算をするのはナンセンス
分子と分母とで、同じ数は打ち消し合うので、それを使って計算する。
組合せの数の場合、可能な数から1づつ減らして乗算するのが最も簡単。
$ {}_6 \mathrm{C}_3の場合 6通り×5通り×4通り(6を起点に1づつ減らして3回)
単純にループで掛け合わせる実装
code:factorial.js
function factorial(n)
{
if (n < 0)
{
return NaN;
}
var r = 1;
for (var i = 2; i <= n; i++)
{
r *= i;
}
return r;
}
Keyword: 階乗の計算方法