分治算法的应用

分治算法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成

回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点

public class FullPermutation { public static void main(String[] args) { String s ="ABC"; char[] arr = s.toCharArray(); HashSet set = new HashSet<>(); permutation(set,arr,0,arr.length - 1); System.out.println(set); } private static void permutation(HashSet set, char[] arr, int from, int to) { if(from == to){ set.add(String.valueOf(arr)); }else{ for(int i = from; i <= to; i++){ swap(arr,i,from); permutation(set,arr,from + 1,to); swap(arr,i,from); } } } private static void swap(char[] arr, int i, int j) { char c = arr[i]; arr[i] = arr[j]; arr[j] = c; }}

public class ChessBoardCoverage { private static int BOARD_SIZE = 8; private static int[][] board = new int[BOARD_SIZE][BOARD_SIZE]; private static int title = 0; public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println(">>>"); int dr = input.nextInt(); int dc = input.nextInt(); chessBoard(0,0,dr,dc,BOARD_SIZE); printBoard(); } private static void printBoard() { for (int i = 0; i < BOARD_SIZE; i++) { for (int j = 0; j < BOARD_SIZE; j++) { System.out.print(board[i][j] + "t"); } System.out.println(); } } private static void chessBoard(int tr, int tc, int dr, int dc, int size) { if(size == 1){ return; } int num = ++title; int s = size / 2; if(dr < tr + s && dc < tc + s){ chessBoard(tr,tc,dr,dc,s); }else{ board[tr + s - 1][tc + s - 1] = num; chessBoard(tr,tc,tr + s - 1,tc + s - 1,s); } if(dr < tr + s && dc >= tc + s){ chessBoard(tr,tc + s,dr,dc,s); }else{ board[tr + s - 1][tc + s] = num; chessBoard(tr,tc+s,tr + s - 1,tc + s,s); } if(dr >= tr + s && dc < tc + s){ chessBoard(tr+s,tc,dr,dc,s); }else{ board[tr + s][tc + s - 1] = num; chessBoard(tr + s,tc,tr + s,tc + s - 1,s); } if(dr >= tr + s && dc >= tc + s){ chessBoard(tr + s,tc + s,dr,dc,s); }else{ board[tr + s][tc + s] = num; chessBoard(tr + s,tc + s,tr + s,tc + s,s); } }}

public class Hanoi { public static void main(String[] args) { String x = "X"; String y = "Y"; String z = "Z"; hanoi(3,x,y,z); } private static void hanoi(int n, String begin, String mid, String end){ if (n == 1) { System.out.println(begin + "->" + end); } else { hanoi(n - 1, begin, end, mid); System.out.println(begin + "->" + end); hanoi(n - 1, mid, begin, end); } }}