Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to solve the maze and the Tower of Hanoi and the eight Queens by Java recursive algorithm". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. Important rules of recursion

When a method is executed, a new protected independent space (stack space) is created.

The local variables of the method are independent and do not affect each other.

If application type variables (such as arrays, objects) are used in the method, the data of that reference type is shared.

Recursion must approach the condition of exit recursion, otherwise it is infinite recursion.

When a method completes execution, or encounters a return, it returns, and returns the result to whoever calls it, and when the method finishes or returns, the method finishes execution.

two。 Three recursive cases 1. The mouse comes out of the maze

/ / A maze with 7 columns and 8 rows / / Analysis / / 1. We use a two-dimensional array to represent the maze / / 2. Define a findWay method to find the path, and the return value is Boolean, / / 3. Returns true if the way is found, false otherwise. / / 4. We use 1 to denote obstacles / / 5. We initialize the mouse's current coordinates (1pm 1) / / 6. 0 means you can walk, 1 means you can't walk, 2 means you can walk, and 3 means you can walk but can't get through / / 7. When map [6] [5] = 2, it means that the way out of the maze has been found, otherwise continue to find the way / / 8. We define a trial rule, we assume bottom-> right-> top-> left public class MiGong {public static void main (String [] args) {/ / Maze initialization int [] [] map = new int [8] [7]; for (int I = 0; I)

< 7; i++){ map[0][i] = 1; map[7][i] = 1; } for(int j = 0 ; j < 8; j++){ map[j][0] = 1; map[j][6] = 1; } map[3][1]= 1; map[3][2]= 1; for (int k = 0; k < map.length; k++) { for(int m = 0; m < map[k].length; m++){ System.out.print(map[k][m] + " "); } System.out.println(); } t way = new t(); way.findWay(map, 1, 1); System.out.println("=====找到路径后的地图====="); for (int k = 0 ;k < map.length; k++) { for(int m = 0;m < map[k].length; m++){ System.out.print(map[k][m] + " "); } System.out.println(); }}}class t{ public boolean findWay(int [][] map ,int x , int y){ if(map[6][5]==2){//递归出口若终点处的值为2则表明能找到一条路 return true; }else{ if(map[x][y]==0){//首先若当前位置为0，则表明可以走 map[x][y]=2;//我们假设选这条路可以走通，将当前位置赋为2 //然后按照我们的试探规则依次试探下->

Right-> top-> left if (findWay (map, XML1, y)) / / Recursive call to findway function returns true return true; else if (findWay (map, x, y)) / / otherwise continue to see if the right side can go return true; else if (findWay (map, Xmurl, y)) / / on the return true Else if (findWay (map, x, ymur1)) / / left return true; else {map [x] [y] = 3; return false;}} else / / map [x] [y] = 1 return false; 2. Hanoi Tower

Legend has it that in ancient Indian temples, there was a game called Hanoi. The game is on a copper plate device, with three poles (numbered A, B, C), and n gold plates are placed on the A pole from bottom to top, from big to small. The goal of the game: move all the gold plates on the A pole to the C pole and still fold them in the original order. Rules of operation: only one plate can be moved at a time, and in the process of moving, the big plate is always kept on the bottom of the three poles, and the small plate is on the top. During the operation, the plate can be placed on any pole A, B or C.

Analysis: for such a problem, it is impossible for anyone to write down every step of moving the plate directly, but we can use the following methods to solve it. Set the number of plates to n. In order to move the n plates from pole A to pole C, you can do the following three steps:

(1) using disk C as the intermediary, move disk 1 to n-1 from pole A to pole B.

(2) move the remaining plate n in pole A to pole C.

(3) take the A pole as the intermediary; move the plate 1 to n-1 from the B pole to the C pole.

Import java.util.Scanner;public class HanoiTower {public static void main (String [] args) {System.out.println ("Please enter the number of disks you want to move:"); tower m = new tower (); Scanner input = new Scanner (System.in); int num = input.nextInt (); m.moveWay (num,'A','B','C') }} class tower {/ / num denotes the number of disks to be moved. A System.out.println, b tower, c tower public void moveWay (int num,char a dagger, b tower, c tower) {if (num = = 1) {/ / if there is only one disk, move it directly from a to c System.out.println (a + "- >" + c). } else {/ / if there is more than one disk as a whole, move to b with the help of c, and then move the last disk to c moveWay (num-1, a, c, b); System.out.println (a + "- >" + c) / / then move all the disks of b to c moveWay (num-1, b, a, c);} 3. Eight queens

The problem is: put eight queens on an 8 × 8 chess game so that they can't attack each other, that is, no two queens can be in the same row, the same column or the same slash.

Public class Queen8 {/ / the first queen is placed in the first row, the first column / / the second column is placed in the first column of the second row, and then determine whether there is a conflict / / if there is a conflict, continue to put the second column, the third column, until you find the location where there is no conflict / / the third queen, or follow the second until the eighth queen can also be placed in a conflict-free place, even if you find a feasible solution. / / when you get a feasible solution, go back to the previous stack and start backtracking, you can get all the feasible solutions that the first queen put in the first column / / then go back and continue the first queen in the second column, repeat the previous operation / / use an one-dimensional array to represent the position placed by the queen / / column such as arry [1] = 3, indicating that the second queen is placed in the second row and the fourth column int max = 8 Int [] arry = new int [max]; static int count = 0; public static void main (String [] args) {Queen8 queen8 = new Queen8 (); queen8.locate (0); System.out.print ("pendulum: + count +" species ");} / / put it into the queen in turn and judge whether there is a conflict with public void locate (int n) {if (n = = max) {display () Return;} for (int I = 0; I < max; iTunes +) {/ / first put the queen n in the first column arry [n] = I; if (judge (n)) {/ / if there is no conflict, continue to place the n + 1 queen locate (nasty 1). } / / in case of conflict, continue to place}} public boolean judge (int n) {for (int I = 0; I < n) in the next column. If +) {/ / arry [I] = = arry [n] means in the same column / / Math.abs (iMain) = = Matn.abs (arry [I]-arry [n]) indicates that it is in the same slash if (arry [I] = = arry [n] | | Math.abs (iripn) = = Math.abs (arry [I]-arry [n])) {return false }} return true;} public void display () {count++; for (int I = 0; I < arry.length; iTunes +) {System.out.print (Arry [I] + ");} System.out.println ();}}" how to solve the maze and the Tower of Hanoi and the eight Queens problem by recursive algorithm "ends here. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.