[자료구조] 순환 알고리즘 원리

순환 알고리즘 원리

순환알고리즘의 원리와 관련 문제입니다.

 

1. 다음 함수를 sub(7)로 호출하면 반환값은?

#include <stdio.h>

int sub(int n) {
    if (n < 0) return 0;
    return n + sub(n - 3);
}

int main(void)
{
    printf("%d", sub(7));
    return 0;
}

함수 설명

sub(7)

// 반환형이 정수형이고 매개변수로 정수형을 받는 sub() 함수에 정수 7을 매개변수로 보냅니다

return 7 + sub(4)

// if문에 의해 n의 값 정수 7은 조건에 부합하지 않으므로 그대로 7을 return함과 동시에 7에서 3을 뺀 정수 4를 순환형식으로 다시 호출합니다

return 7 + 4 + sub(1)

// if문에 의해 n의 값 정수 4는 조건에 부합하지 않으므로 그대로 4을 return함과 동시에 4에서 3을 뺀 정수 1을 순환형식으로 다시 호출합니다

return 7 + 4 + 1 + sub(-2)

// if문에 의해 n의 값 정수 1은 조건에 부합하지 않으므로 그대로 1을 return함과 동시에 1에서 3을 뺀 정수 -2를 순환형식으로 다시 호출합니다

return 7 + 4 + 1 + 0 = 12

// if문에 의해 n의 값 정수-2는 조건에 부합하므로 순환을 멈추고 0을 return합니다.

 

최종 반환값 : 12

 

 

 

2. 다음 함수를 sum(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라

#include <stdio.h>

int sum(int n) {
    printf("%d\n", n);
    if (n < 1) return 1;
    else return (n + sum(n - 1));
}

int main(void)
{
    printf("%d", sum(5));
    return 0;
}

함수 설명

sum(5)

// sum() 함수에 5를 매개변수로 보냅니다

printf(”%d\n”, n);

// n의 값으로 들어온 5를 출력하고 줄바꿈합니다

if(n < 1) return 1;

else return (n + sum(n - 1));

= return 5 + sum(4)

// 5는 if문의 조건에 부합하지 않으므로 그대로 5를 return함과 동시에 5 - 1의 값인 정수 4를 순환형식으로 다시 호출합니다

// n의 값으로 들어온 4를 출력하고 줄바꿈합니다

= return 5 + 4 + sum(3)

// 4는 if문의 조건에 부합하지 않으므로 그대로 4를 return함과 동시에 4 - 1의 값인 정수 3을 순환형식으로 다시 호출합니다

// n의 값으로 들어온 3을 출력하고 줄바꿈합니다

= return 5 + 4 + 3 + sum(2)

// 3은 if문의 조건에 부합하지 않으므로 그대로 3을 return함과 동시에 3 - 1의 값인 정수 2를 순환형식으로 다시 호출합니다

// n의 값으로 들어온 2를 출력하고 줄바꿈합니다

= return 5 + 4 + 3 + 2 + sum(1)

// 2는 if문의 조건에 부합하지 않으므로 그대로 2를 return함과 동시에 2 - 1의 값인 정수 1을 순환형식으로 다시 호출합니다

// n의 값으로 들어온 1을 출력하고 줄바꿈합니다

= return 5 + 4 + 3 + 2 + 1 + sum(0)

// 1은 if문의 조건에 부합하지 않으므로 그대로 1을 return함과 동시에 1 - 1의 값인 정수 0을 순환형식으로 다시 호출합니다

// n의 값으로 들어온 0를 출력하고 줄바꿈합니다

= return 5 + 4 + 3 + 2 + 1 + 1

// 0은 if문의 조건에 부합하므로 1을 return하고 함수를 종료합니다

 

최종 반환값 :16

출력 내용:

5

4

3

2

1

0

 

 

 

3. 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라

#include <stdio.h>

int recursive(int n) {
    printf("%d\n", n);
    if (n < 1) return 2;
    else return (2 * recursive(n - 1) + 1);
}

int main(void)
{
    printf("%d", recursive(5));
    return 0;
}

함수 설명

recursive(5)

// recursive() 함수에 정수 5를 매개변수로 보냅니다

printf(“%d\n”, n);

// n의 값 5를 출력합니다

if(n < 1) return 2;

else return (2 * recursive(n - 1) +1);

= 현재 return 값 : 2 * recursive(4) +1

// 정수 5는 if문의 조건에 부합하지 않으므로 2 * 1 값을 return함과 동시에 5 - 1의 값인 정수 4를 순환 형식으로 다시 호출합니다

// n의 값 4를 출력합니다

= 현재 return 값 : 2 * 2 * recursive(3) +1

// 정수 4는 if문의 조건에 부합하지 않으므로 2 * 2 + 1 값을 return함과 동시에 4 - 1의 값인 정수 3을 순환 형식으로 다시 호출합니다

// n의 값 3을 출력합니다

= 현재 return 값 : 5 * 2 * recursive(2) +1

// 정수 3은 if문의 조건에 부합하지 않으므로 5 * 2 + 1 값을 return함과 동시에 3 - 1의 값인 정수 2를 순환 형식으로 다시 호출합니다

// n의 값 2를 출력합니다

= 현재 return 값 : 11 * 2 * recursive(1) +1

// 정수 2는 if문의 조건에 부합하지 않으므로 11 * 2 + 1 값을 return함과 동시에 2 - 1의 값인 정수 1을 순환 형식으로 다시 호출합니다

// n의 값 1을 출력합니다

= 현재 return 값 : 23 * 2 * recursive(0) +1

// 정수 1은 if문의 조건에 부합하지 않으므로 23 * 2 + 1 값을 return함과 동시에 1 - 1의 값인 정수 0을 순환 형식으로 다시 호출합니다

// n의 값 0을 출력합니다

= 현재 return 값 : 47 * 2 +1

// 정수 0은 if문의 조건에 부합하므로 47 * 2 + 1 값을 return하고 함수를 종료합니다.

 

최종 반환값 : 95

출력내용:

5

4

3

2

1

0

 

 

 

4. 다음 함수를 recursive(10)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라

#include <stdio.h>

int recursive(int n) {
    printf("%d\n", n);
    if (n < 1) return -1;
    else return (recursive(n - 3) + 1);
}

int main(void)
{
    printf("%d", recursive(10));
    return 0;
}

함수 설명

recursive(10)

// recursive() 함수에 정수 10을 매개변수로 보냅니다

printf(“%d\n”, n);

// 정수 10을 출력합니다

if (n < 1) return -1;

else return (recursive(n - 3) +1);

= 현재 return 값 : recursive(7) + 1

// 정수 10은 if문의 조건에 부합하지 않으므로 1을 return함과 동시에 10 - 3의 값인 정수 7을 순환 형식으로 다시 호출합니다

// 정수 7을 출력합니다

= 현재 return 값 : recursive(4) + 1 + 1

// 정수 7은 if문의 조건에 부합하지 않으므로 1 + 1을 return함과 동시에 7 - 3의 값인 정수 4를 순환 형식으로 다시 호출합니다

// 정수 4를 출력합니다

= 현재 return 값 : recursive(1) + 1 + 1 + 1

// 정수 4는 if문의 조건에 부합하지 않으므로 1 + 1 + 1을 return함과 동시에 4 - 3의 값인 정수 1을 순환 형식으로 다시 호출합니다

// 정수 1을 출력합니다

= 현재 return 값 : recursive(-2) + 1 + 1 + 1 + 1

// 정수 1은 if문의 조건에 부합하지 않으므로 1 + 1 + 1 + 1을 return함과 동시에 1 - 3의 값인 정수 -2를 순환 형식으로 다시 호출합니다

// 정수 -2를 출력합니다

= 현재 return 값 : -1 + 1 + 1 + 1 + 1

// 정수 -2는 if문의 조건에 부합하므로 -1 + 1 + 1 + 1 + 1을 return하고 함수를 종료합니다.

 

최종 반환값 : 3

출력 내용

10

7

4

1

-2

 

 

 

5. 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용을 쓰시오

#include <stdio.h>

int recursive(int n) {
    if (n != 1) recursive(n - 1);
    printf("%d\n", n);
}

int main(void)
{
    recursive(5);
    return 0;
}

함수 설명

recursive(5)

// 정수 5를 recursive() 함수에 매개변수로 보냅니다

if(n != 1) recursive(n - 1);

// n의 값 5는 if문의 조건에 부합하므로 5 - 1의 값인 정수 4를 순환형식으로 다시 호출하고 정수 5는 스택에 쌓입니다

// n의 값이 1이 될 때까지 순환하며 4, 3, 2, 1을 차례대로 스택에 올려놓습니다

printf(“%d\n”, n);

// 스택에 쌓인 n의 값들을 다시 꺼내어 마지막 값부터 순차적으로 출력합니다.

 

출력 내용:

1

2

3

4

5

 

 

 

6. 다음 함수에서 asterisk(5)를 호출할 때 출력되는 *의 갯수는?

#include <stdio.h>

void asterisk(int i) {
    if (i > 1) {
        asterisk(i / 2);
        asterisk(i / 2);
    }
    printf("*");
}
int main(void)
{
    asterisk(5);
    return 0;
}

함수 설명

asterisk(5)

// 정수 5를 asterisk() 함수의 매개변수로 보냅니다

If (i >1) {

  asterisk(i / 2);

  asterisk(i / 2);

}

// 최초 asterisk 호출에서 정수 5는 if문의 조건에 부합하므로 5 / 2의 값인 정수 2를 순환 형식으로 각각 두 번 호출합니다

// 1번 asterisk 호출에서 정수 2는 if문의 조건에 부합하므로 2 / 2의 값인 정수 1을 순환 형식으로 각각 두 번 호출합니다

// 1-1번 asterisk 호출에서 정수 1은 if문의 조건에 부합하지 않으므로 조건문을 탈출하고 *을 출력합니다

// 1-2번 asterisk 호출에서 정수 1은 if문의 조건에 부합하지 않으므로 조건문을 탈출하고 *을 출력합니다

// 2번 asterisk 호출에서 정수 2는 if문의 조건에 부합하므로 2 / 2의 값인 정수 1을 순환 형식으로 각각 두 번 호출합니다

// 2-1번 asterisk 호출에서 정수 1은 if문의 조건에 부합하지 않으므로 조건문을 탈출하고 *을 출력합니다

// 2-2번 asterisk 호출에서 정수 1은 if문의 조건에 부합하지 않으므로 조건문을 탈출하고 *을 출력합니다

// 1번 asterisk 호출이 종료되어 *을 출력합니다

// 2번 asterisk 호출이 종료되어 *을 출력합니다

// 최초로 실행했던 asterisk의 호출이 종료되어 *을 출력합니다

 

* 출력 개수 : 7개

 

 

 

7. 다음과 같은 함수를 호출하고 “recursive”문자열을 입력한 다음, 엔터키를 눌렀다면 화면에 출력되는 것은?

#include <stdio.h>

unknown() {
    int ch;
    if ((ch = getchar()) != '\n')
        unknown();
    putchar(ch);
}

int main(void)
{
    unknown();
    return 0;
}

함수 설명

unknown()

// unknown() 함수를 호출합니다

int ch;

if( (ch=getchar()) != ‘\n’)

unknown();

// 정수형 변수 ch를 선언하고 getchar() 를 통해 값을 사용자로부터 입력받습니다

// if 문의 조건 안에 있는 내용을 실행합니다.

// recursive를 입력합니다. getchar()는 char형 1개만 입력받으므로 ch에는 r의 정수값인 114를 할당하고 나머지 ecursive와 Enter키를 통해 입력된 Line Feed값이 버퍼에 담깁니다.

// 입력된 ch가 if문에서 null값이 아닐때 라는 조건에 부합하므로 unknown()을 다시 호출합니다

// ch에는 버퍼에 담겨있던 e의 정수값인 101을 할당합니다. 이와 같은 방식으로 조건에 부합할 때 까지 나머지 c, u, r, s, i, v, e를 순환하며 각각 99, 117, 114, 115, 105, 118, 101을 할당하고 마지막 Line Feed의 값인 10을 할당합니다.

// 이후에는 버퍼에 남아있는 값이 없으므로 조건에 부합하지 않아 조건문을 탈출합니다

 

출력 내용 :

 

evisrucer

 

// putchar(ch)를 통해 마지막 값부터 char형으로 변환하여 첫번째로 \n(줄바꿈)을 출력하고 e, v, i, s, r, u, c, e, r을 차례로 출력합니다