[C로 쓴 자료구조론] 1장 연습문제-10번(Ackermann 함수) 풀이

 

 

 

 

 

 

 

 

 

 

10번 문제

---

Ackermann 함수 A(m, n)은 다음과 같이 정의된다.

 

이 함수는 m, n의 값이 아주 작은 값에서도 급속히 증가하는 성질이 있다.

이 함수를 계산하는 순환함수와 반복 함수를 작성하여라.

---

 

 

뭐하는 함수인지 궁금해서 좀 찾아보았습니다.

그냥 재귀함수에서 대표적으로 쓰이는 함수인 것 같네요.

 

혹시나 궁금한 분들은 위키피디아ㄱㄱ

https://ko.wikipedia.org/wiki/%EC%95%84%EC%BB%A4%EB%A7%8C_%ED%95%A8%EC%88%98

아커만 함수 - 위키백과, 우리 모두의 백과사전

 

 

 

아무튼 이 문제는 재귀함수와 반복함수로 구현해보겠습니다.

재귀함수는 너무 쉽죠?

혹시나 재귀함수가 어려우신분들은 아래 링크 참고해보세요. 전반전인 재귀함수에 대한 이해에 도움이 됩니다.

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

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

 

 

 

일단 재귀함수 구현은 한번 익히면 너무 쉽기때문에

바로 보겠습니당

 

#include <stdio.h>

int ackermann(int m, int n);

int main() {
	int m, n;

	printf("이 프로그램은 ackemann함수의 값을 계산하는 함수입니다.\n");
	printf("순서대로 A(m, n)에서 m과 n의 값을 입력해 주세요: ");
	scanf("%d %d", &m, &n);

	printf("A(%d, %d) = %d\n", m, n, ackermann(m, n));

	return 0;
}

int ackermann(int m, int n) {
	if (m == 0)
		return (n + 1);
	else if (n == 0)
		return ackermann(m - 1, 1);
	else
		return ackermann(m - 1, ackermann(m, n - 1));
}

 

 

 

 

 

뭐 다 실행이 잘되는데

 

 

m의 값이 4이상이 되어버리면 값이 출력되지 않고 프로그램이 멈춰버립니다.

이게 어떻게 된일인지 보기위해 count변수를 새로 생성해줄게요.

아까전에 알아볼 때 연산 횟수가 기하급수적으로 늘어난다는 점이 있던게 기억나네요.

 

 

 

#include <stdio.h>

int ackermann(int m, int n);
int count = 0;

int main() {
	int m, n;

	printf("이 프로그램은 ackemann함수의 값을 계산하는 함수입니다.\n");
	printf("순서대로 A(m, n)에서 m과 n의 값을 입력해 주세요: ");
	scanf("%d %d", &m, &n);

	printf("A(%d, %d) = %d\n", m, n, ackermann(m, n));
	printf("count = %d", count);

	return 0;
}

int ackermann(int m, int n) {
	count++;
	if (m == 0)
		return (n + 1);
	else if (n == 0)
		return ackermann(m - 1, 1);
	else
		return ackermann(m - 1, ackermann(m, n - 1));
}

 

 

코드를 다음과 같이 바꿔주고 다시 실행했습니다.

 

 

 

 

네... 이정도만 봐도 얼마나 함수가 많이 실행이 되며, 얼마나 비효율적인지 한눈에 볼 수 있네요.

 

4, 1을 넣으면 프로그램이 종료가 되는데, 대충 어느정도인지 보고싶어서 디버깅 모드로 체크해봤습니다.

 

 

코드에 이렇게 10000단위로 count를 출력시키는 코드를 추가하였고, m=4, n=1로 코드를 돌려보았습니다.

 

 

 

진짜 값이 미친듯이 늘어납니다...

프로그램이 터질만 했네요.

 

안그래도 비효율적인 함수 + 재귀함수의 콜라보인것같습니다.

 

그래서 조금 더 큰 값도 계산하고 싶어서 재귀함수를 이용하지 않고 구현을 한 번 해보았습니다.

 

 

일단 이 ackermann함수를 풀어서 쓰게 되면, A(1, 1)같은 경우에는

 

A(1, 1) = A(0, A(1, 0)) = A(0, A(0, 1)) = A(0, 2) = 3

 

이런식으로 진행되고, 더 복잡하지만 A(2, 1)같은 경우에는

 

A(2, 1) = A(2, A(2, 0))

= A(1, A(2, A(2, 0)-1))

= A(0, A(1, A(2, A(2, 0)-1)))

= A(0, A(1, A(2, A(1, 1)-1)))

....

 

 

개 복잡하쥬?

저도 복잡해서 더 못쓰겠네영.

 

 

아무튼 위의 식을 보게 된다면 결국 마지막에는 A(0, k)꼴이 되어야 끝나기 때문에, 배열을 통해서 이를 구현했습니다.

 

list 배열이 있다고 하면,

첫번째 인덱스에는 m의 값, 두번째 인덱스에는 n의 값을 넣어둡니다.

그러고 나서 n에 해당하는 부분에 대해서 다시 Ackemann함수를 실행해서 새로운 m, n값을 채워주는 식으로 진행했습니다.

말로 설명하기 어려운 것 같아 위에 예시를 듯 A(1, 1)로 설명을 하자면

 

 

list[10] = {1, 1}

list[10] = {1, 1, 0}

list[10] = {1, 0, 1}

list[10] = {0, 2}

list[10] = {2}

 

 

이런식으로 배열이 채워지겠죠?

물론, 굳이 따지고 보면 뒤에 값들은 따로 값들을 초기화해주지 않았기 때문에 4번째 단계에서는 {0, 2, 1}로 남아있을거고 마지막에는 {2, 2, 1}로 값이 채워져 있겠죠.

편의상 위와 같이 표기했습니다.

 

그러면 여기서 더 필요한건 "현재" m에 해당하는 값은 어떤 값이며, 어떤 상황에서 종료해야 할지 구현해야 합니다.

이를 고려하며 구현하면, 

 

 

#include <stdio.h>

int ackermann(int m, int n);
int A(int m, int n);
int count = 0;

int main() {
	int m, n;

	printf("이 프로그램은 ackemann함수의 값을 계산하는 함수입니다.\n");
	printf("순서대로 A(m, n)에서 m과 n의 값을 입력해 주세요: ");
	scanf("%d %d", &m, &n);

	printf("A(%d, %d) = %d\n", m, n, A(m, n));
	printf("count = %d", count);
	

	return 0;
}

int A(int m, int n) {
	int list[100000];
	int esp = 0;

	list[esp++] = m;
	list[esp] = n;

	while (1) {
		if (esp == 0) {
			return list[esp];
		}
		else if (list[esp - 1] == 0) {
			count++;
			list[esp - 1] = list[esp] + 1;
			esp = esp - 1;
		}
		else if (list[esp] == 0) {
			count++;
			list[esp - 1] = list[esp - 1] - 1;
			list[esp] = 1;
		}
		else {
			count++;
			list[esp + 1] = list[esp] - 1;
			list[esp] = list[esp - 1];
			list[esp - 1] = list[esp - 1] - 1;

			esp = esp + 1;
		}
	}
}

int ackermann(int m, int n) {
	count++;
	if (m == 0)
		return (n + 1);
	else if (n == 0)
		return ackermann(m - 1, 1);
	else
		return ackermann(m - 1, ackermann(m, n - 1));
}

하나의 코드로 구현하고 싶어서 재귀함수 코드도 있습니당..

 

 

이 됩니다.

 

m=4, n=1일때 되는지 얼른 값을 넣어봅시다

 

 

 

와! 결과값!

 

지금 count가 이상하죠?

보아하니 integer overflow가 일어난 것 같은데,

int의 범위가 -2,147,483,648 ~ 2,147,483,647인걸 고려하면 엄청난 횟수의 반복을 한거죠.

혹시라도 integer overflow를 모르시는 분들은 구글링을 해보시는걸 추천합니다.

 

 

아무튼 count가 저렇게 비정상적으로 높은걸 봐선 스택메모리 부족으로 프로그램이 터졌을거 같은데,

뭐 어떻게 잘 실행이 됐네요..?

값이 맞는지는 잘 모르겠습니다...

 

그래도 그나마 반복문으로 하는게 재귀함수보단 효율적이라 프로그램은 안터진거같네요.

 

 

 

 

여기서 마무리하겠습니다 끝!