[C/자료구조] Ackermann 함수

C언어를 이용한 자료구조 실습입니다.

 

---

I. 문제

Ackermann 함수는 다음과 같이 정의된다. 다음에 답하시오.

 

A(0, n) = n+1   A(m, 0) = A(m-1,1)   A(m, n) = A(m-1, A(m,n-1)) m, n >= 1

 

a. A(3,2)와 A(2,3)의 값을 각각 구하시오. 그 과정을 보여야 한다.

b.위의 함수를 구하는 C 프로그램을 순환적으로 작성하고, a)에서 구한 A(3,2), A(2,3)을 테스트하라.

c. b)에서 작성한 순환적 함수를 반복적 버전으로 작성하고, b)와 같이 동일하게 테스트하라.

 

 

[예상출력]

 

 

II. 구현

- 순환

#pragma warning (disable : 4996) 
#include <stdio.h>
#include <stdlib.h>

int Acker(int m, int n) {
	if (m == 0)			// m이 0일 때
		return n + 1;
	else if (n == 0)	// n이 0일 때
		return Acker(m - 1, 1); // 재귀

	else //m도 0이 아니고 n도 0이 아닐 때
		return Acker(m - 1, Acker(m, n - 1)); // 재귀
}

int main() {
	int m, n;

	printf("m값을 입력해주세요 : "); 
	scanf("%d", &m);
	printf("n값을 입력해주세요 : "); 
	scanf("%d", &n);

	printf("Ackermann(%d,%d) : %d", m, n, Acker(m, n)); // 출력

	return 0;
}

 

 

- 반복

#pragma warning (disable : 4996) 
#include <stdio.h>
#include <stdlib.h>

int ackermann(int m, int n) {

    int list[400000];
    int p = 0; // 현재 위치

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

    while (1) {
        if (p == 0)          // 위치가 0일 때
            return list[p];  // n 반환

        else if (list[p - 1] == 0){ // m이 0일때
            list[p - 1] = list[p] + 1; // m은  n+1
            p = p - 1;                 // 위치 변경
        }
        else if (list[p] == 0){             // n이 0일때
            list[p - 1] = list[p - 1] - 1;  // m은 -1
            list[p] = 1;                    // n은 1
        }
        else{
              
            list[p + 1] = list[p] - 1;  // n-1 옮기기
            list[p] = list[p - 1];      // m값 옮기기
            list[p - 1] = list[p - 1] - 1;  // m-1 대입
            p = p + 1;                      // 위치 증가
        }

    }
}


int main() {
    int m, n;

    printf("m값을 입력해주세요 : "); // m값 입력받기
    scanf("%d", &m);
    printf("n값을 입력해주세요 : "); // n값 입력받기
    scanf("%d", &n);

    printf("결과 : %d\n", ackermann(m, n));  // 결과 출력

    return 0;
}

 

 

III. 결과

 

- 순환

 

-반복

 

---

 

공부한 내용을 복습/기록하기 위해 작성한 글이므로 내용에 오류가 있을 수 있습니다.