C 언어로 구현하는 이항 계수 테이블 출력 프로그램

양의 정수 값(예: val)이 하나 주어졌을 때, 0부터 val 사이의 임의의 n과 k에 대해 이항 계수 B(n, k)의 값을 계산하고 그 결과를 표 형태로 출력하는 것이 이번 글의 목표입니다.

이항 계수란 무엇인가?

이항 계수 (n, k)는 주어진 n개의 대상 가운데 k개를 선택하는 경우의 수를 의미합니다. n과 k가 양수일 때 이항 계수의 값은 아래 공식으로 구할 수 있습니다.

$$C_k^n=\frac{n!}{(n-k)!k!}$$

단, n ≥ k 여야 합니다.

계산 예시

입력: B(9,2)
출력:

$$B_2^9=\frac{9!}{(9-2)!\,2!}=\frac{9!}{7!\times 2!}=\frac{362{}880}{10{}080}=36$$

즉, 9개 중에서 2개를 선택하는 조합의 수는 36가지입니다.

이항 계수 테이블이란?

이항 계수 테이블은 n과 k가 달라질 때마다 생성되는 여러 값을 일일이 계산하지 않고 한눈에 확인할 수 있도록 만든 표입니다. 흔히 파스칼의 삼각형 형태로 나타내며, 각 행은 n값을, 행 안의 각 위치는 k값에 해당하는 계수를 의미합니다.

테이블 생성 예시

입력: value = 5
출력:

프로그램의 접근 방식

• 테이블을 생성하기 위해 사용자로부터 변수 'val'을 입력받습니다.
• 이항 계수의 값은 0부터 'val' 사이 범위에 존재하므로, 루프를 0부터 'val'까지 반복합니다.
• n과 k가 0이 아닌 경우에는 아래 점화식 공식을 적용합니다.
  B(m, x) = B(m, x - 1) * (m - x + 1) / x
• 계산된 결과를 순서대로 출력합니다.

알고리즘

시작
1단계 -> 이항 계수 테이블용 함수 선언
    int bin_table(int val)
    int i = 0 부터 i <= val 까지 반복(i++)
        i 값 출력
        int num = 1 선언
        int j = 0 부터 j <= i 까지 반복(j++)
            if (i != 0 && j != 0)
                num = num * (i - j + 1) / j 설정
            num 값 출력
        반복 종료
    줄바꿈(\n) 출력
2단계 -> main() 함수에서
    int value = 5 선언
    bin_table(value) 호출
종료

C 언어 예제 코드

#include <stdio.h>
// 이항 계수 테이블을 위한 함수
int bin_table(int val) {
    for (int i = 0; i <= val; i++) {
        printf("%2d", i);
        int num = 1;
        for (int j = 0; j <= i; j++) {
            if (i != 0 && j != 0)
                num = num * (i - j + 1) / j;
            printf("%4d", num);
        }
        printf("\n");
    }
}
int main() {
    int value = 5;
    bin_table(value);
    return 0;
}

실행 결과

위 코드를 실행하면 value가 5일 때 다음과 같은 이항 계수 테이블이 출력됩니다.