nCr 을 계산하는 방법.

방법 1. "연속한 n 자리 자연수는 n 의 배수이다." 를 이용합니다.

nCr = n*(n-1)*...(n-r+1)/1*2*...*n

이므로 n*(n-1) 은 2 , n*(n-1)*(n-2) 는 3 을 약수로 가지므로 ...

ans = 1;
for( i = 1 , j = n ; i <= n ; i++,j--){
   ans *= j/i;
}

방법 2. 점화식 이용

문서에서 두 번째 점화식 이용

#include <stdio.h>

unsigned long long f(int  n,int  r)
{
   if ( r == 1) return n;

   return f(n-1,r-1)*n/r; 
}

int main()
{
   int n,r;
   
   scanf("%d %d",&n,&r);

   printf("%d things taken %d at a time is %llu exactly.\n",n,r,f(n,r));
}

---

[홈으로]  [뒤 로]