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

質問

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

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

回答No.8

anicicle

http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1248280462

回答No.7

麻野 なぎ（@AsanoNagi）

No.4 訂正です。

順列は、r == 1 のとき n（通り）
それ以外の時は、最初に n 個のうち、どれを選ぶかで、n 通り、
それぞれについて、n - 1 個から、r - 1 個を選ぶ順列の数だけの可能性があるので、

int p(int n, int r)
{
if (r == 1) return n;
else return n * p(n - 1, r - 1); // n * が抜けてましたね。
}

回答No.6

jacta

> 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;
}

回答No.4

麻野 なぎ（@AsanoNagi）

順列は、r == 1 のとき n（通り）
それ以外の時は、最初に n 個のうち、どれを選ぶかで、n 通り、
それぞれについて、n - 1 個から、r - 1 個を選ぶ順列の数だけの可能性があるので、

int p(int n, int r)
{
if (r == 1) return n;
else return p(n - 1, r - 1);
}

組み合わせは、r == 1 のとき、n （通り）
n == r のとき、１通り。
それ以外の時は、特定の要素に注目すると、それを含む組み合わせが
n - 1 C r - 1 （これに特定の要素を追加）
それを含まない組み合わせが
n - 1 C r
あります。

これの合計が組み合わせの数なので、

int c(int n, int r)
{
if (r == 1) return n;
else if (n == r) return 1;
else return c(n - 1, r - 1) + c(n - 1, r);
}

実際には、n >= r > 0 のチェックも必要になりますが。

回答No.3

piroin654

以下でも。

http://monogusa-math.blogspot.com/2009_08_01_archive.html

回答No.2

piroin654

順列、組み合わせのソースは以下に
サンプルがあります。

http://www5.airnet.ne.jp/tomy/cpro/perm.htm

回答No.1

toda hiro（@hiro_knigh）

質問の意味がわかりません