점화식 ( nCr )

오늘의 공부 점화식

nCr 구하기 n개 가운데에세 r개를 선택하는 조합 nCr을 구하기

C의 뜻은 Comination의 머리 글자 임...

주의할사항은

단순 nCr을 계산하면  n!/r!(n-r)!로 계산하게 된다.

n!을 돌리는동안  n의 형이 int이면 버퍼오버플로우가 나타나 쓰레기 값이 나오거나

프로그램이 오류가 날수 있다.

그것을 주의 하여 계산 방법을 다르게 알고리즘을 세우는것이 좋다.


#include <stdio.h>

long combi(int, int);

void main(void){
   int n,r;

   for(n=0;n<=5;n++){
      for(r=0;r<=n;r++){
         printf("%d C %d =%d \n", n, r, combi(n,r));
      }
   }
}

long combi(int n, int r){
   int i;
   long p =1;
   for(i=1;i<=r;i++){
      p = p*(n-i+1)/i;
return p;
}