[JAVA]再帰アルゴリズム(2)
23911 ワード
資料構造とともに学習するアルゴリズム入門-Java
ハノイの塔
->move(番号-1,x(始発柱)、6-x-y(中間柱)
->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);
}
}
Reference
この問題について([JAVA]再帰アルゴリズム(2)), 我々は、より多くの情報をここで見つけました https://velog.io/@suzu11/JAVA-재귀-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol