[프로그래밍 랩] 4주차 - 재귀

문제 1. 재귀함수 sum, factorial, fibonacci, gcd, binary

1 ~ n까지의 합인 sum, 1 ~ n까지의 곱인 factorial, 피보나치 수열 fibonacci, 유클리드 호제법을 이용한 최대공약수를 구하는 gcd, 10진수 n을 2진수로 바꿔 출력하는 binary 함수를 재귀함수로 구현하시오.

 

추가) 1 ~ n까지 홀수의 합과 짝수의 합을 반환하는 oddsum, evensum, 10진수 n을 k진수로 바꾸는 jinbub을 구현하시오.

이번 문제는 배워갈게 많은 문제이다.

a진수 숫자인 n을 b진수로 바꾸는 문제는 시험에 간간히 나오는 문제이기 때문에 알아두면 좋다.

또한, 유클리드 호제법을 통해 gcd를 구하는 것은, 알고리즘 문제를 풀면서 최대공약수를 구하는 문제를 풀 때, (시간복잡도 측면에서) 매우 효율적인 알고리즘이므로 알아두면 좋다.

그리고 피보나치 수열을 재귀함수로 구현하는 경우, n이 조금만 커져도 연산 횟수또한 기하급수적으로 증가하게 되는데, 이는 정말 많은 시간을 소모한다는 의미이다. 수업과는 관련이 없지만, 이를 해결할 방법을 고민해보면 좋다. (hint : memoization)

// 1학기 프로그래밍랩 - 4주
// Lab4-1 재귀함수

#include <stdio.h>
int sum(int n)
{
    if (n <= 1)
        return n;
    else
        return n + sum(n - 1);

}
int oddsum(int n) // 홀수의 합
{
    if (n == 1)
        return n;

    else if (n % 2 == 0) n--; // 짝수 -> 홀수
        
    return n + oddsum(n - 2);
}
int evensum(int n) // 짝수의 합
{
    if (n == 2)
        return n;

    else if (n % 2 == 1) n--; // 홀수 -> 짝수

    return n + evensum(n - 2);
}
int factorial(int n)
{
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

int fibo(int n) // recursive 방식
{
    if (n <= 1)
        return n;
    else
        return fibo(n - 1) + fibo(n - 2);

}

int gcd(a, b) // 최대 공약수
{
    if (b == 0) return a;
    else return gcd(b, a % b);
}
void binary(int n)
{
    if (n < 2)
        printf("%d", n);
    else {
        binary(n / 2);
        printf("%d", n % 2);
    }
}
void jinbub(int n, int k) // 10진수 n을 k진법으로 출력
{
    if (k <= 10) {
        if (n < k)
            printf("%d", n);
        else {
            jinbub(n / k, k);
            printf("%d", n % k);
        }
    }
    else {
        if (n < k)
            printf("%d", n);
        else {
            jinbub(n / k, k);
            int tmp = n % k;
            // printf("%d", tmp < 10 ? tmp : );
            if (tmp < 10)
                printf("%d", tmp);
            else
                printf("%c", tmp - 10 + 65); // +65 : 영어 대문자 아스키코드, -10 : 나머지가 10이상일때
        }
    }
}
void main()
{
    int i, k, n = 10;
    printf("sum(%d) = %d\n", n, sum(n));
    n = 10;
    printf("oddsum(%d) = %d\n", n, oddsum(n));
    // n = 11;
    printf("evensum(%d) = %d\n", n, evensum(n));
    printf("factorial(%d) = %d\n", n, factorial(n));
    printf("fibonacci = ");
    for (i=0;i<=10;i++)
        printf("%d ", fibo(i));
        //printf("%d:%d ", i, fibo(i));
    printf("\n");
    n = 12345;
    printf("binary(%d) = ", n);
    binary(n);
    printf("\n");

    n = 0x12abcdef; // 313249263
    
    printf("n=%d\n", n);
    for (k = 2; k <= 10; k++) {
        printf("%d진법 : ", k);
        jinbub(n, k); // 2: 10010101010111100110111101111
        printf("\n");
    }
    k = 16;
    printf("%d진법 : ", k);
    jinbub(n, k);
    printf("\n");
}

 

문제 2. Hanoi Tower

하노이 탑에 관한 문제. 재귀함수의 문제라면 빠지지 않는 문제이다.

#include <stdio.h>

void hanoi_tower(int n, char from, char tmp, char to)
{
    if (n == 1)
        printf("원판 1을 %c 에서 %c으로 옮긴다.\n", from, to);
    else {
        // 1 ~ n-1 을 임시 장소에 이동
        hanoi_tower(n - 1, from, to, tmp);
        // 제일 밑에 있는 원판을 이동
        printf("원판 %d을 %c에서 %c으로 옮긴다.\n", n, from, to);
        // 1 ~ n-1 을 임시 장소에서 목적지로 이동
        hanoi_tower(n - 1, tmp, from, to);
    }
}
void main()
{
    hanoi_tower(4, 'A', 'B', 'C');
}

 

문제 3. Hanoi Tower 변형

하노이 탑을 시각화해서 출력한다.

//  1학기 프로그래밍랩 
// Lab 4-3 Hanoi tower 중간과정 출력
#include <stdio.h>

// 탑에 저장된 원판의 수와 어떤 원판이 있는지 보관하는 변수
// 초기 조건 
// A 에 4,3,2,1 이 있다면
// 탑에 몇개의 원판이 있는지 저장 : nplates[0] = 4 ---> nplates = {4, 0, 0}
// 탑의 현재 상태 tower[0][0 ~ 3] => 4, 3, 2, 1
// 1 이 B 로 움직였다면
// nplates[0] = 3, nplates[1] = 1 -> nplates = {3,1,0}
// tower[0][0 ~ 2] = 4, 3, 2
// tower[1][0] = 1

int nplates[3]; // 탑에 몇개의 원판이 있는지
int tower[3][100]; // 어떤 원판들이 있는지 보관

// 탑의 현재 상태를 표시한다.
void print_tower()
{
    int i; // tower 번호
    int j; 
    // tower[][] 내용을 보여준다
    for (i = 0; i < 3; i++) {
        j = 0;
        printf("%c : ", i + 65);
        while (tower[i][j] != 0) {
            printf("%d ", tower[i][j++]);
        }
        printf("\n");
    }
    printf("\n");
    printf("다음 Enter : ");
    getchar(); // getchar() 로 잠시 대기한다.
}

// 하나의 원판을 이동할 때 마다 전체 탑의 현재 상태를 변경한다.
void move_one(int n, char from, char to)
{
    int tmp;
    printf("\n원판 %d을 %c에서 %c로 옮긴다.\n", n, from, to);
    // nplates[] 와 tower[][] 내용을 수정한다
    // from 에서는 제일 위의 원판을 빼고
    // to 에는 제일 끝에 원판을 추가하고
    tower[to - 'A'][nplates[to - 'A']] = tower[from - 'A'][nplates[from - 'A'] - 1];
    tower[from - 'A'][nplates[from - 'A'] - 1] = 0;
    // nplates[] 값을 감소/증가 한다.
    nplates[from - 'A']--;
    nplates[to - 'A']++;
    // 이동이 발생할 때 마다 print_tower() 호출
    print_tower();

}

// 타워내용을 초기화 한다.
void init_tower(int n, char start)
{
    int i, tower_no;
    //탑의 번호 A, B, C -> 0, 1, 2
    tower_no = start - 'A';
    // tower[][] 내용과 nplates[]를 초기화 한다.
    // tower[0][0]~[0][3] = 4, 3, 2, 1 식으로
    for (i = 0; i < n; i++) {
        tower[tower_no][i] = n - i;
    }
    // nplates[] 에 원판의 수를 기억시킨다..
    nplates[tower_no] = n;

}

void hanoi_tower(int n, char from, char tmp, char to)
{
    if( n==1 ) 
        move_one(1, from, to); // 제일 위에 있는 1번 원판을 이동

    else {
        hanoi_tower(n-1, from, to, tmp); // 1 ~ n-1 을 임시 장소에 이동
        move_one(n, from, to); // 제일 밑에 있는 원판을 이동
        hanoi_tower(n-1, tmp, from, to); // 1 ~ n-1 을 임시 장소에서 목적지로 이동
    }
}

void main()
{
    init_tower(4, 'A'); // 초기 조건, 1~4 원판이 A 에 있다.
    printf("초기 상태\n");
    print_tower();
    hanoi_tower(4, 'A', 'B', 'C');
}

 

문제 4. 구조체 연습

이번 문제는 재귀와는 상관없지만, 아무튼 문제로 나왔으니 풀자.

복소수를 구조체를 통해 구현하고, 두 복소수의 합과 차를 return하는 add함수와 sub함수를 구현하자.

#include <stdio.h>

typedef struct complex {
    int real;
    int img;
} COMPLEX;

#define ABS(x) ((x>0) ? (x) : (-x))

void print_complex(COMPLEX *x)
{
    if (x->real != 0)
        printf("(%d", x->real);

    if (x->img > 0)
        printf(" + %di)", x->img);
    else if (x->img < 0)
        printf(" - %di)", ABS(x->img));
}

COMPLEX add(COMPLEX x, COMPLEX y)
{
    COMPLEX result = { x.real + y.real, x.img + y.img };
    return result;
}

COMPLEX sub(COMPLEX x, COMPLEX y)
{
    COMPLEX result = { x.real - y.real, x.img - y.img };
    return result;
}

void main()
{
    COMPLEX x, y, z;

    scanf("%d %d", &x.real, &x.img);
    scanf("%d %d", &y.real, &y.img);
    z = add(x, y);
    print_complex(&x); printf(" + "); print_complex(&y);
    printf(" = ");print_complex(&z);
    printf("\n");
    
    z = sub(x, y);
    print_complex(&x); printf(" - ");print_complex(&y);
    printf(" = ");print_complex(&z);
    printf("\n");
}

 

문제 5. 백준 9009번

https://codejin.tistory.com/76

백준 9009번 C언어 풀이