#12. 4주차 과제 2 [Chap05_5-2 ~ 5-6]

5-2. (EuclidGCD) _ 유클리드 호제법을 이용한 최대공약수 구하기

package practice;
 
import java.util.Scanner;
/*
 * 유클리드 호제법
 * 
 * 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나.
 * 
 * 호제법이란 말은
 * 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘.
 * 
 * 2개의 자연수(또는 정식) a, b에 대해서
 * a를 b로 나눈 나머지를 c라 하면(단, a>b),
 * a와 b의 최대공약수는 b와 c의 최대공약수와 같다.
 * 
 * 이 성질에 따라,
 * b를 c로 나눈 나머지 c’를 구하고,
 * 다시 c을 c’로 나눈 나머지를 구하는 과정을 반복하여
 * 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라는 것.
 * 
 */
 
public class EuclidGCD_5_2 {
    //정수 x,y 의 최대공약수를 구하여 반환합니다.
    
    static int gcd(int x, int y) {
        if(y==0) return x;
        else return gcd(y, x%y);
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        System.out.println("두 정수의 최대공약수를 구합니다.");
        System.out.print("정수를 입력하세요: ");
        int x = stdIn.nextInt();
        System.out.print("정수를 입력하세요: ");
        int y = stdIn.nextInt();
        
        System.out.println("최대공약수는 "+gcd(x,y)+"입니다.");
    }
}
 

---

5-3(+4). (Recur) _ 재귀 알고리즘 분석

package practice;
 
import java.util.Scanner;
 
public class Recur_5_3 {
    
    
    static void recur(int n) {
        
        if(n>0) {
            recur(n-1);
            System.out.println(n);
            recur(n-2);
        }
    }
    
//-------------------5-4영역-------------------------------    
    //꼬리 재귀를 제거
    //비재귀적 표현으로 바꾼다. 실행결과는 재귀함수와 같다.
    static void recur2(int n) {
        while(n>0) {
            recur2(n-1);
            System.out.println(n);
            n=n-2;
        }
    }
//--------------------------------------------------------
    
    public static void main(String[] args) {
        
        Scanner stdIn = new Scanner(System.in);
        
        System.out.print("정수를 입력하세요.");
        int x = stdIn.nextInt();
        
        recur(x);
        System.out.println("-------------");
        recur2(x);
    }
}
 

---

5-5. (RecurX2) _ 완전 비재귀표현

package practice;
 
import java.util.Scanner;
 
public class RecurX2_5_5 {
    
    //chapter4 에서 만들었던 스택을 이용해
    //모든 재귀호출을 완전 비재귀적 표현으로 바꿨다.
    static void recur(int n) {
        IntStack_4_1 s = new IntStack_4_1(n);
        
        while(true) {
            if (n>0) {
                s.push(n);
                n=n-1;
                continue;
            }
            if(s.isEmpty() !=true) {
                n=s.pop();
                System.out.println(n);
                n=n-2;
                continue;
            }
            break;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        recur(n);
        
    }
}
 

---

5-6. (Hanoi) _ 하노이의 탑

 : cnt는 연산횟수 보려고 개인적으로 추가했습니다.

package practice;
 
import java.util.Scanner;
 
public class Hanoi_5_6 {
    
    static int cnt = 0;
    
    static void move(int no, int x, int y) {
        cnt++;
        if (no>1)    move(no-1, x, 6-x-y);
        
        System.out.println("원반["+no+"]을 "+x+"기둥에서 "+y+"기둥으로 옮김");
        
        if (no>1)    move(no-1, 6-x-y, y);
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        System.out.println("하노이의 탑");
        System.out.print("원반 개수: ");
        int n = stdIn.nextInt();
        
        //1번기둥의 n개의 원반을 3번기둥으로 옮긴다.
        move(n,1,3);
        System.out.println("\n총 "+cnt+"번 연산했다!");
        
    }
 
}
 

 

---

재귀호출 너무 어렵다 ㅠㅠ.... 하나도 모르겠어 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ