21-05-17

1. 순환(recursion)

함수는 자기 자신을 호출할 수도 있다.

1) 팩토리얼 구하기

long factorial(int n)
{
	if (n<=1) return 1;
    else return n * factorial(n-1)
}

 

2) 2진수 구하기

#include <stdio.h>

void print_binary(int x)
{
	if (x > 0)
	{
		print_binary(x / 2);
		printf("%d", x % 2);
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	print_binary(n);
	return 0;
}

 

3) 최대공약수 구하기

#include <stdio.h>

int gcd(int x, int y)
{
	if (y == 0)
		return x;
	else
		return gcd(y, x % y);
}

int main()
{
	int x, y;
	scanf("%d %d", &x, &y);
	printf("%d\n", gcd(x, y));
}

수학적 알고리즘에 대한 지식(유클리드 호제법)이 필요한 코드이다.

 

---

Lab. 하노이의 탑

#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
	{
		hanoi_tower(n - 1, from, to, tmp);
		printf("원판 %d을 %c에서 %c(으)로 옮긴다.\n", n, from, to);
		hanoi_tower(n - 1, tmp, from, to);
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	hanoi_tower(n, 'A', 'B', 'C');
	return 0;
}

n개의 원판을 A에서 C로 옮기는 알고리즘의 경우,
step 1. n-1개의 원판을 from에서 temp로 옮긴다.
step 2. n번째 원판을 from에서 to로 옮긴다.
step 3. n-1개의 원판을 temp에서 to로 옮긴다.

 

예컨대, 4개의 원판을 옮기는 경우 다음과 같이 나타낼 수 있다.(색깔순)

---

2. 배열

#include <stdio.h>

int main()
{
	int i;
	int score[5];

	for (i = 0; i < 5; i++)
	{
		score[i] = i * 10 + 10;
		printf("score[%d]=%d\n", i, score[i]);
	}
	return 0;
}

0부터 인덱스된다는 사실에 유의

 

---

3. 최댓값과 최솟값

	int i;
	int arr[5];

	int M = arr[0];
	for (i = 1; i < 5; i++)
		if (M < arr[i]) M = arr[i];

	int m = arr[0];
	for (i = 1; i < 5; i++)
		if (m > arr[i]) m = arr[i];

빈출 알고리즘