n개중에서 r개를 뽑는 경우는 nCr이라는 공식을 이용하여 풀수 있다.

nCr =  n! / r! x (n-r)! 이다

하지만 이것을 컴퓨터에게 그대로 적용시켜 계산하게 되면 오버 플로우가 일어날 수 있다.

n!의 경우 n값이 조금만 크더라도 n!값이 엄청 커진다.

이를 방지 하기 위해서 점화식을 이용해서 풀면 된다.

nCr = (n - r + 1) / r * nCr-1
nC0 = 1( r = 0일때)

이런식으로 점화식을 이용해서 풀면 오버 플로우를 막을 수 있다.

double combination( int n, int r )
{

    int i;

    double sum;

    sum = 1;

    for( int i =1; i <= r; i++ )

        sum = sum * (( n - i + 1 ) / (double) i );

   return sum;
}

신고
by danguria 2008.02.27 11:10
| 1 |