[JAVA]再帰アルゴリズム(2)

23911 ワード


資料構造とともに学習するアルゴリズム入門-Java

ハノイの塔

  • 底部円盤以外のグループ(円盤[1]~円盤[number-1])を始柱から中間柱に移動
    ->move(番号-1,x(始発柱)、6-x-y(中間柱)
  • 底部円盤数が始点柱から目標柱に移動する
  • を出力する.
  • 底部円盤以外のグループ(円盤[1]~円盤[number-1])を中間柱から目標柱へ移動
    ->move(番号-1、中間柱、ターゲット柱)
  • 本の内容に従って、途中で和音を変えた.
    import java.util.Scanner;
    
    public class Main {
    //number = 원반의 개수 x=시작 기둥의 번호 y=목표 기둥 번호 
        public static void move(int number, int x, int y){
        
        //원반이 1개가 되면 그냥 출력 
            if(number == 1){
               System.out.println(x+" "+y+"\n");
               return;
           }
           // 이건 위랑 같음. 바닥 원반 빼고 시작 -> 중간
           move(number-1,x,6-x-y);
           System.out.println(x+" "+y+"\n");
           // 중간 -> 목표 
           move(number-1,6-x-y,y);
        }
        
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
    
            System.out.println("하노이의 탑");
            System.out.print("원반 개수 : ");
            int n = sc.nextInt();
    
            move(n,1,3);
        }
    }
    

    8皇后問題


    例)8個の皇后を8*8チェス盤に置き、互いに攻撃しないようにする
    行方向、列方向、対角線方向に移動できるので、どの対角線で見ても1つの皇后だけを置くように制限する必要があります.
    public class EightQueen {
        static boolean[] flag_a = new boolean[8]; //각 행에 퀸을 배치했는지
        static boolean[] flag_b = new boolean[15]; //대각선 방향으로 퀸을 배치했는지 /
        static boolean[] flag_c = new boolean[15]; //대각선 방향으로 퀸을 배치했는지 \
        static int[] pos = new int[8]; //각 열의 퀸의 위치
    
        static void print()
        {
            for(int i=0;i<8;i++){
                System.out.printf("%2d",pos[i]);
            }
            System.out.println();
        }
        static void set(int i){
            for(int j=0;j<8;j++){
                if(flag_a[i]==false && flag_b[i+j]==false && flag_c[i-j+7]==false){
                    pos[i]=j;
                    if(i==7){
                        print();
                    }else{
                        flag_a[j]=flag_b[i+j]=flag_c[i-j+7]=true;
                        set(i+1); // 재귀가 끝나면 퀸이 j행에서 제거되었기 때문에 false 처리
                        flag_a[j]=flag_b[i+j]=flag_c[i-j+7]=false;
                    }
                }
            }
        }
        public static void main(String[] args){
            set(0);
        }
    }
    

    標準9663 N-Queen


    参照ビデオ:Python学習アルゴリズム基礎:19 n-Queens問題の実施
    import java.util.*;
    
    public class Main { 
        public static int N;
        public static int []map;
        public static StringBuilder sb = new StringBuilder();
        public static int queen_count = 0 ;
    
        public static void chess(int num){
            if(num==N){
                queen_count++;
                return;
            }
    
            for(int i=0;i<N;i++){
                map[num]=i;
                //놓을 수 있는 위치인가 아닌가
                if(promising(num)){
                    chess(num+1);
                }
            }
    
        }
    
        public static boolean promising(int k){
            for(int i=0;i<k;i++){
            //i번째 행에서 퀸이 놓여있는 열
            //col번째 행에서 퀸이 놓여있는 열
            //같은 열에 놓이게 되므로, 유망 XX
                if(map[k]==map[i]){
                    return false;
                    //대각선 체크 -> arr[i]-arr[k] == i - k (절댓값) 
                }else if(Math.abs(i-k)==Math.abs(map[i]-map[k])){
                    return false;
                }
            }
            return true;
        }
    
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            N=sc.nextInt();
            map = new int [N];
    
            chess(0);
            System.out.println(queen_count);
        }
    }