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 となってしまう。