すみません！いそいでます！お願いします！！！

質問

すみません！いそいでます！お願いします！！！

c言語で、nPr と nCr はどんな式になりますか？

回答No.5

麻野 なぎ（@AsanoNagi）

先のソースで、再帰呼び出しによる組み合わせのは、本質的に足し算だけで構成しているので、計算途中の（普通の式なら階乗計算で）オーバーフローを防止できます。
ただし、呼び出しが深くなって（オーバーフローより先に）スタックがあふれるんじゃないかという問題もありますが。

そこで、組み合わせのほうは、こういうソースも有効です。
このソースの特徴は、
result *= n;
result /= i;
を連続で実行することで（ついでに、n も小さい方からかけることで）途中の計算におけるオーバーフローをなるべく避けるというものです。
このソースで、「/= i が割り切れないときに誤差が出るのではないか？」という気もしますが、この場合、全ステップで必ず割り切れることも証明可能です。
※連続する n個の整数の積は必ずnの倍数になることをいえばいい。
※いいかえると、連続するn個の整数の中には、必ずnの倍数があることをいえばいい。

int c(int n, int r)
{
int result = 1;
int i;
n -= r;

for(i = 1; i <= r; i++, n++)
{
result *= n;
result /= i;
}

return n;
}