본문 바로가기

프로그래밍/알고리즘

조합, 이항계수 계산 코드

#include <stdio.h>

#define MAX 200

 

unsigned int C[MAX + 1][MAX + 1] = { 0 };

void calcBino() {    //이항계수 계산

    for (int i = 0; i <= MAX; i++) {

        C[i][0] = C[i][i] = 1;

        for (int j = 1; ji; j++)

            C[i][j] = C[i-1][j-1] + C[i-1][j];

    }

}

int main() {

    calcBino();

    printf("%u", C[45][6]);

}

C 코드지만 사실 언어적인 의미가 없는 코드라 따로 언어 카테고리에 넣지 않았습니다.



MAX개 만큼 조합의 경우의 수를 미리 계산하여놓는 코드 입니다.

즉 여기선 최대 200C200 까지 계산을 해놓습니다.


코드를 실행하면 이러한 테이블이 만들어집니다.


좌우 대칭이니

사실 for(j) 부분을

for (int j = 1; j <= i / 2; j++)

C[i][j] = C[i][i-j] = C[i-1][j-1] + C[i-1][j];

이렇게 절반까지만 돌아도 모두 채울 수 있습니다.