[알고리즘 공부 6일차]

1.팩토리얼

for문이 아닌 재귀를 통해 팩토리얼을 구현한다

int factorial(int a)
{
	if (a == 0)
		return (1);
	return a * factorial(a-1);
}

재귀를 통해 간단하게 구현하였다.

2.피보나치수 5

int fibonacci(int a)
{
	if (a <= 0)
		return (0);
	if (a == 1)
		return (1);
	return fibonacci(a-1) + fibonacci(a-2);
}

재귀를 통해 피보나치를 구현한다 fibonacci(a) 는 fibonacci(a-1) + fibonacci(a-2) 이기 때문에 간단하게 재귀로 구현할수있다 탈출조건은 0보다 작을때 0 1일때는 1로 해주면된다

3.별찍기 10

분할 정복을 통해 해결한다

void star(int i, int j, int num)
{
    if ((i / num) % 3 == 1 && (j / num) % 3 == 1) {
        cout << ' ';
    }
    else
    {
        if (num / 3 == 0)
            cout << '*';
        else
            star(i, j, num / 3);
    }
}

빈칸의 규칙을 찾아 재귀를 통해 구성하면된다

4.하노이 탑 이동 순서

void print_hanoi(int a,int from,int to)
{
    int middle = 6 - from - to;
    if (a == 1)
    {
        printf("%d %d\n", from, to);
        return;
    }
    if (a >= 2)
    {
        print_hanoi(a - 1, from, middle);
        print_hanoi(1, from, to);
        print_hanoi(a - 1, middle, to);
        return;
    }
}
...

a는 원판의 크기이다 원판의 크기가 1일땐 바로 원하는곳으로 이동한다 아니라면 위에있는 작은판부터 가운데로 옮겨준 후에 첫번째칸에있는판을 원하는곳에 옮겨준다