2項係数

定義通り計算すれば良いが、「複合代入演算子」による落とし穴があるので注意。

コード例.

#include <stdio.h>
int binomial(int a, int n);
int main()
{
	int a = 7;
	for (int i = 0; i <= a; i++)
	{
		printf("binomial(%d,%d)=%d\n", a, i, binomial(a, i));
	}
}
int binomial(int a, int n) {
	int b = 1;
	int i;
	for (i = 0; i < n; i++)
	{
		b = b * (a - i) / (i + 1);
	}
	return b;
}

実行結果.

binomial(7,0)=1
binomial(7,1)=7
binomial(7,2)=21
binomial(7,3)=35
binomial(7,4)=35
binomial(7,5)=21
binomial(7,6)=7
binomial(7,7)=1

複合代入演算子利用の注意

上のコード中、binomialの定義の個所で

b = b * (a - i) / (i + 1);

を複合代入演算子を用いて

b *= (a - i) / (i + 1);

とつい書いてしまいそうになるが、このように変更すると

実行結果

binomial(7,0)=1
binomial(7,1)=7
binomial(7,2)=21
binomial(7,3)=21 // おかしい
binomial(7,4)=21 // おかしい
binomial(7,5)=0 // おかしい
binomial(7,6)=0  // おかしい
binomial(7,7)=0  // おかしい

となって結果が合わなくなる。これは x *= a が x = (x)*(a) のように計算されていると理解すればよい。

以下 b *= (a - i) / (i + 1); と書きかえたコードのbinomialの処理のステップを見る。

Step1 b=1.
Step2 b=(1)*(7/1)=7.
Step3 b=(7)*(6/2)=21.
Step4 b=(21)*(5/3)=21.
Step5 b=(21)*(4/4)=21.
Step6 b=(21)*(3/5)=0.
Step7 b=(0)*(2/6)=0.
Step8 b=(0)*(1/7)=0.

このように()をつけて考えると、なぜこのような現象が起きるのかを理解しやすい。つまり、 演算順序が変わってしまい、実行結果も変わってしまったということである。 数学的には、かけ算と割り算の順序はどちらを先に行っても良いが、C言語の場合は、純粋な割り算でない( 上のケースでは「商」だけを計算している)ため、演算順序が実行結果に影響する。

例(かけ算と割り算の順序に関する注意すべき点)

(3*2)/3 = 6/3 = 2
は普通の計算と変わらないが、順序を変えるとC言語では
3*(2/3)= 3*0 = 0 となってしまう。