재귀 연습2

3N + 1 수열 만들기

문제

• 자연수 N에서 시작하여 N이 짝수면 2로 나누고, N이 홀수면 3을 곱하고 1을 더하는 것을 N이 1이 되기 전까지 계속 반복할때, 총 몇 번을 반복해야 1이 되는지를 계산. 단, 재귀함수 이용.

풀이

• 점화식을 생각하자
• f(n)의 정의
  • n에서 시작해서 1이 되기 위해 필요한 횟수
• f(1) = 0
• n이 짝수면, f(n) = f(n / 2) + 1
• n이 홀수면, f(n) = f(n * 3 + 1) + 1

import java.util.Scanner;
 
public class Main {    
    // a가 3n + 1 수열을 총 몇번 반복해야 1이 되는지 반환합니다.
    public static int countNumber(int a) {
        if(a == 1)
            return 0;
    
        if(a % 2 == 0)
            return countNumber(a / 2) + 1;
        else
            return countNumber(3 * a + 1) + 1;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 변수 선언 및 입력:
        int n = sc.nextInt();
 
        System.out.print(countNumber(n));
    }
}
 

풀이2

• 재귀 답지 못한 재귀랄까?

import java.util.*;
import java.io.*;
public class Main {
    static int n,cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
 
        recur(n);
 
        System.out.print(cnt);
    }
 
    static void recur(int num){
        if(num == 1) return;
        if(num%2==0) {
            num /= 2;
            cnt++;
        }
        else{
            num = num * 3 + 1;
            cnt++;
        }
 
        recur(num);
 
    }
}

---

100으로 나눈 나머지의 수열

문제

• 첫 번째는 2, 두 번째는 4, 세 번째부터는 앞의 두 수의 곱을 100으로 나눈 나머지로 이루어진 수열이 있을때, 100 이하의 정수 N을 입력받아 재귀함수를 이용하여 N번째 값을 구하여 출력 코멘트
• 재귀 감 잡기 좋았다 풀이
• 문제를 쪼개서 위임하기

import java.util.*;
import java.io.*;
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
 
        System.out.println(recur(n));
    }
 
    static int recur(int cnt){
        if(cnt==2) return 4;
        if(cnt==1) return 2;
 
        return (recur(cnt-1) * recur(cnt-2)) % 100;
    }
}

---

자연수 배열의 최소공배수

문제

• n개의 수가 주어졌을때 이 수들의 최소공배수는? 풀이
• 틀렸던 이유 int lcm = 0; 으로 초기화 하면, n이 1로 입력될때, 0을 출력하게됨. 원소 개수 1개이므로 첫번째 원소로 초기화 해야 함.

import java.util.*;
import java.io.*;
 
public class Main {
    static int n, arr[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int lcm = arr[0];
        for(int i = 1; i < n ; i++){
            lcm = arr[i-1] * arr[i] / gcd(arr[i-1],arr[i]);
            arr[i] = lcm;
        }
 
        System.out.print(lcm);
 
    }
 
    static int gcd(int a, int b){
        if(b==0) return a;
        return gcd(b,a%b);
    }
}