[Algorithm] 재귀 함수 기초 2

6. 2진수 변환, 진법 변환

14를 2진법으로 고칠 때 어떤 과정을 거칠까?

14 / 2 = 7 … 0

7 / 2 = 3 … 1

3 / 2 = 1 …. 1

따라서 1110이 된다.

십진법 수 n을 2진법으로 나타내는 함수는 f(n, 2)로 정의할 수 있다.

그럼, 십진법 수 n이 2보다 작은 경우 n을 출력, 2보다 크거나 같은 경우 점화식을 f(n/k, k), printf(“%d”, n % k);로 정리할 수 있다.

2진법 외 다른 진법으로 변환하고자 하는 경우 f(n, 2) 부분을 f(n, k)로 바꾸기만 하면 된다.

11진법-16진법으로 변환하고자 하는 경우 알파벳을 출력하는 부분을 만들어야 하므로 아래와 같이 서식 문자를 바꾼다. 

(서식문자만 바꾸면 됨 -> %X[대문자], %x[소문자]) 

아래 예시 코드는 16진법까지 변환할 수 있다.

20진법까지 바꾸고자 하는 경우, char letter[21] =“0123456789ABCDEFGHIJ";  변수를 만들어 변수 내 값을 꺼낸다. 이 부분은 한번 생각해보길 바란다.

7. 우박수(3n+1) Basic

1. 어떤 자연수 n 이 입력되면,  

2. n이 홀수이면 3n + 1을 하고,  

3. n이 짝수이면 n/2 를 한다.  

4. 이 n이 1이 될때까지 2, 3 과정을 반복한다.  

예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.  

이 처럼 어떤 자연수 n이 입력되면 위 알고리즘에 의해 1이 되는 과정을 모두 출력한다.

솔직히 이 문제는 문제에서 해결 전략을 다 줬다... 종료 조건만 생각하면 된다.

8. 우박수(3n+1) reverse

1. 어떤 자연수 n 이 입력되면,  

2. n이 홀수이면 3n + 1을 하고,  

3. n이 짝수이면 n/2 를 한다.  

4. 이 n이 1이 될때까지 2, 3 과정을 반복한다.  

예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.  

이 처럼 어떤 자연수 n이 입력되면 위 알고리즘에 의해 1이 되는 과정을 모두 출력한다.

근데, 이 순서의 역순을 출력하고자 한다.

즉, 1, 2, 4, 8, 16, 5가 출력되어야 한다.

반대로 한다 (...) 

조건은 같으나 n == 1인 경우 printf("1\n"); 해주고 더 이상 함수를 호출하지 않도록 한다.

9. 삼각형 출력하기 (반대로)

5가 입력되면

*****

****

***

**

*

을 출력한다.

이 문제는 * 출력과, \n 출력할 부분을 구별해 주면 된다.

10. 피보나치 수열 (Large)

자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.  

단, N이 커질 수 있으므로 출력값에 10,009를 나눈 나머지를 출력한다.

이 문제는 Large 문제이므로 이전에 계산한 값을 메모리에 저장함으로써 

동일한 계산의 반복 수행을 제거하는 메모이제이션 기법으로 프로그램을 작성한다.