[C로 쓴 자료구조론] 1장 연습문제-9번(이항계수) 풀이

 

 

 

 

 

9번 문제

 

---

9. 이항 계수를 계산하는 반복 함수를 작성하고 이를 순환함수로 변환하라

---

 

일단 이 문제는 두가지 방법으로 풀이 할 예정입니다.

첫 번째 방법은 정의로, 두 번째 방법은 성질로 풀 예정입니다.

 

 

일단 이항 계수는 우리가 확통시간에 배운 C입니다. 조합이요

이게 정의입니다. 혹시라도 모르시는 분들을 위해.

 

이렇게 하면 그냥 팩토리얼로 계산만 하면 되죠?

 

 

팩토리얼 구현에 대한 함수는 전글 보시면 될 것 같습니다.

링크는 여기

https://dokhakdubini.tistory.com/191?category=847037

[C로 쓴 자료구조론] 1장 연습문제-7번(팩토리얼) 풀이

 

 

그래서 저 정의를 토대로 코딩을 하면 다음과 같은 결과가 나옵니다.

 

 

#include <stdio.h>

int factorial(int n);
int combination(int n, int k);

int main() {
	int n, k;
	printf("차례대로 n과 k를 입력해주세요: ");
	scanf(" %d %d", &n, &k);

	printf("%dC%d = %d",n, k, combination(n, k));

	return 0;
}

int factorial(int n) {
	if (n <= 1)
		return 1;
	else
		return n * factorial(n - 1);
}

int combination(int n, int k) {
	if (k<0 || k >n)
		return 0;
	else
		return factorial(n) / (factorial(k)*factorial(n - k));
}

 

 

근데 제가 이항계수에는 성질도 하나 있다고 했죠?

파스칼 삼각형의 법칙 중 하나인데,

 

 

이 식을 이용하려고 합니다.

위에 두개 더하면 그 사이 아래 값이 나온다는거 고등학교때 배운적 있죠?

 

이걸 재귀함수와 엮어서 이용합시다.

 

재귀함수가 어려운 사람은 여기로

https://dokhakdubini.tistory.com/190?category=814319

[재귀함수] 재귀함수 구현할 때 염두에 두면 좋은 것들

 

 

어차피 파스칼의 삼각형의 테두리? 바깥쪽의 값들(nC0, nCn)의 값들은 모두 1이므로 기본 틀은 k=0이나 k=n일때 1을 반환하도록 하고 이를 이용해 재귀함수 식을 작성하면 될 것 같습니다.

 

#include <stdio.h>

int combination(int n, int k);

int main() {
	int n, k;
	printf("차례대로 n과 k를 입력해주세요: ");
	scanf(" %d %d", &n, &k);

	printf("%dC%d = %d",n, k, combination(n, k));

	return 0;
}

int combination(int n, int k) {
	if (k == 0 || k == n)
		return 1;
	else
		return combination(n - 1, k - 1) + combination(n - 1, k);
}

 

 

끝