Java通过递归算法解决迷宫与汉诺塔及八皇后问题

目录
  • 1.递归的重要规则
  • 2.递归的三个案例
    • 1.老鼠出迷宫
    • 2.汉诺塔
    • 3.八皇后

1.递归的重要规则

  • 在执行一个方法时,就创建一个新的受保护的独立空间(栈空间)。
  • 方法的局部变量时独立的,不会相互影响。
  • 如果方法中使用的是应用类型变量(比如数组,对象),就会共享该引用类型的数据。
  • 递归必须向退出递归的条件逼近,否则就是无限递归。
  • 当一个方法执行完毕,或者遇到return,就会返回,遵循谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕。

2.递归的三个案例

1.老鼠出迷宫

//一个7列8行的迷宫
//分析
//1.我们用一个二维数组来表示迷宫
//2.定义一个findWay方法来找路径,返回值为布尔类型,
//3.若找到路则返回true,否则返回false。
//4.我们用1来表示障碍物
//5.我们初始化老鼠当前坐标(1,1)
//6.用0表示能走,1表示不能走,2表示走过能走,3表示走过但走不通
//7.当map[6][5]=2时则说明找到了出迷宫的路,否则继续找路
//8.我们定义一个试探走的规则,我们假设 下->右->上->左
public class MiGong{
   public  static void main(String [] args){
   //迷宫初始化
   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
         //然后按照我们的试探规则依次试探下->右->上->左
         if(findWay(map, x+1, y))//递归调用findway函数如果下可以走则返回true
            return  true;
         else if (findWay(map, x, y+1))//否则还继续看右边能不能走
              return true;
         else if(findWay(map, x-1, y))//上
               return true;
         else if(findWay(map, x, y-1))//左
               return true;
         else {
               map[x][y]=3;
               return false;
             }
      }else // map[x][y]=1,2,3
          return false;
  }
 }
}

2.汉诺塔

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

分析:对于这样一个问题,任何人都不可能直接写出移动盘子的每一步,但我们可以利用下面的方法来解决。设移动盘子数为n,为了将这n个盘子从A杆移动到C杆,可以做以下三步:

(1)以C盘为中介,从A杆将1至n-1号盘移至B杆;

(2)将A杆中剩下的第n号盘移至C杆;

(3)以A杆为中介;从B杆将1至n-1号盘移至C杆。

import java.util.Scanner;
public class HanoiTower{
	public static void main(String []args ){
	System.out.println("请输入你要移动的盘数:");
    tower m = new tower();
Scanner input = new Scanner(System.in);
    int num = input.nextInt();
    m.moveWay(num,'A','B','C');
	}
}
class tower{
	//num表示要移动的盘的个数,a,b,c分别表示a塔,b塔,c塔
	public void moveWay(int num,char a,char b,char c){
		if(num == 1){//如果只有一个盘,直接将其从a移动到c
			System.out.println(a + "->" + c);
		}
		else {//如果有多个盘将最后一个盘以上的盘看成一个整体,借助c,移动到b,然后将最后一个盘移到c
			moveWay(num-1, a, c, b);
			System.out.println(a + "->" + c);
			//然后再将b的所有盘,借助a,移动到c
			moveWay(num-1, b, a, c);
		}
	}
}

3.八皇后

问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

public class Queen8{
//第一个皇后先放在第一行第一列
//第二个放在第二行第一列,然后判断是否发生冲突
//如果冲突,则继续放第二列,第三列,依次直到找到不发生冲突的位置
//第三个皇后,还是按照第二个一样依次找直到第八个皇后也能放在一个不发生冲突的地方,就算找到一个可行解。
//当得到一个可行解时,回退到上一个栈开始回溯,既可以得到第一个皇后放在第一列的所有可行解
//然后回头继续第一个皇后放在第二列,重复前面的操作
//用一个一维数组来表示皇后放置的位置
//列如arry[1]=3,表示第二个皇后放在第二行第四列
   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("摆法一共有:"+ count +"种");
 }
// 依次放入皇后,并判断是否冲突
public void locate(int n){
	if(n == max){
		display();
		return;
	}
	for(int i = 0; i < max; i++){
	//先把皇后n放到第一列
     arry[n] = i;
     if(judge(n)){//不冲突则继续放置第n+1个皇后
     	locate(n+1);
     }
     //如果冲突则继续往后一列放置
	}
}
 public boolean judge(int n){
	for(int i = 0; i < n; i++){
		//arry[i]==arry[n]表示在同一列
		//Math.abs(i-n)==Matn.abs(arry[i]-arry[n])表示在同一斜线
		if(arry[i] == arry[n] || Math.abs(i - n) == Math.abs(arry[i] - arry[n])){
			return false;
		}
	}
	return true;
 }
 public void display(){
 	count++;
 	for(int i = 0; i < arry.length; i++){
    System.out.print(arry[i]+" ");
 	}
 	System.out.println();
 }
}

到此这篇关于Java通过递归算法解决迷宫与汉诺塔及八皇后问题的文章就介绍到这了,更多相关Java递归算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java使用递归回溯完美解决八皇后的问题

    八皇后问题 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 解决思路 ①第一个皇后先放第一行第一列. ②第二个皇后放在第二行第一列.然后判断是否OK,如果不0K, 继续放在第二列.第三列.依次把所有列都放完,找到一个合适. ③继续第三个皇后, 还是第一列.第二列-直到第8个皇后也能放在一个不冲突的位置,算是找

  • java递归实现汉诺塔步骤介绍

    汉诺塔的规则是:一共三根柱子,一根柱子从上到下套着有小到大的若干个圆盘,要将所有圆盘按照这个排放顺序移动到第三根柱子上,并且每次只能移动一个圆盘. 可以将整个过程分为三个步骤来看: 第一步:将除最大圆盘外的n-1个圆盘移动辅助柱子上 第二步:将最大的圆盘移动到目标柱子 第三步:将n-1个圆盘从辅助柱子移动到目标柱子 其中第一步又可以拆成一模一样的三步,可以看成一个n-1层的塔要移动到目标柱子,只不过目标柱子换了一个: 第三步也可以拆分成一模一样的三步: 多拆几次就会发现规律:第一步和第三步无论如

  • Java递归实现迷宫游戏

    目录 1.问题由来 2.问题的描述 3.思路分析 4.代码实现 5.结果输出 1.问题由来 迷宫实验是取自心理学的一个古典实验.在该实验中,把一只老鼠从一个无顶大盒子的门放入,在盒中设置了许多墙,对行进方向形成了多处阻挡.盒子仅有一个出口,在出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口.对同一只老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步.老鼠经多次试验终于得到它学习走迷宫的路线. 2.问题的描述 有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍.墙壁.边界)

  • Java递归来实现汉诺塔游戏,注释详细

    我们很容易能想到,可以用递归来实现汉诺塔游戏.因为要将n(n>1)个盘子从"源"柱子移到"目标"柱子,我们要先把n-1个盘子从"源"柱子移到"辅助"柱子上,然后把最底下那一个盘子移到目标柱子上,最后把"辅助柱"上的n-1个盘子移动到目标柱子上.n==1时直接移到目标柱上,也是递归的出口. 有了以上思路的铺垫,就可以开始实现代码了. public class HanoiDemo { public sta

  • java递归算法的实例详解

    递归三要素: 1.明确递归终止条件: 2.给出递归终止时的处理办法: 3.提取重复的逻辑,缩小问题规模. 1.1+2+3+-+n import java.util.Scanner; public class Recursion { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(sum(n)); } publ

  • Java基于循环递归回溯实现八皇后问题算法示例

    本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public

  • Java的递归算法详解

    目录 一.介绍 1.介绍 2.案例 二.迷宫问题 三.八皇后问题 四.汉诺塔问题 1.问题 2.思想 3.代码 总结 一.介绍 1.介绍 递归:递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁. 迭代和递归区别:迭代使用的是循环结构,递归使用的选择结构.使用递归能使程序的结构更清晰.更简洁.更容易让人理解,从而减少读懂代码的时间.其时间复杂度就是递归的次数. 但大量的递归调用会建立函数的副本,会消耗大量的时间和内存,而迭代则不需要此种付出

  • Java通过递归算法解决迷宫与汉诺塔及八皇后问题

    目录 1.递归的重要规则 2.递归的三个案例 1.老鼠出迷宫 2.汉诺塔 3.八皇后 1.递归的重要规则 在执行一个方法时,就创建一个新的受保护的独立空间(栈空间). 方法的局部变量时独立的,不会相互影响. 如果方法中使用的是应用类型变量(比如数组,对象),就会共享该引用类型的数据. 递归必须向退出递归的条件逼近,否则就是无限递归. 当一个方法执行完毕,或者遇到return,就会返回,遵循谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕. 2.递归的三个案例 1.老鼠出

  • Java编程用栈来求解汉诺塔问题的代码实例(非递归)

    [题目] 汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间.求当塔有N层的时候,打印最优移动过程和最优移动总步数. [解答] 上一篇用的是递归的方法解决这个问题,这里我们用栈来模拟汉诺塔的三个塔,也就是不用递归的方法 原理是这样的:修改后的汉诺塔问题不能让任何塔从左直接移动到右,也不能从右直接移动到左,而是要经过中间,也就是说,实际上能做的动作,只有四个:左->中,中->左,中->右,右->中 用栈

  • Java手把手必会的实例汉诺塔讲解练习

    最适合菜鸟的汉诺塔讲解 问题引入 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘. 让我们先从小事入手. 标记汉诺塔的三根柱子分别为 a ,b ,c 标记汉诺塔上的圆盘分别为:1 ,2,3,4 -n a 柱上面只有一个圆盘时 只有这一种走法 a柱上有两个圆盘时

  • Java 细致图解带你分析汉诺塔

    目录 一.汉诺塔问题来源 二.问题分析 从简单问题开始 三.解决问题 整体思路 四.婆罗门能否完成大梵天的任务 移动 64 个盘子需要多长时间 计算机移动64个盘子需要多长时间 ? 一.汉诺塔问题来源 汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只

  • Java数据结构及算法实例:汉诺塔问题 Hanoi

    /** * 汉诺塔大学的时候就学过,但是根本没搞明白,唯一知道的就是要用递归的方法来求解. * 问题描述: * 有三根杆子A,B,C.A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小. * 要求按下列规则将所有圆盘移至C杆: * 1.每次只能移动一个圆盘: * 2.大盘不能叠在小盘上面. * 提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆, * 但都必须尊循上述两条规则. * 问:如何移?最少要移动多少次? * 解决方法: * 假设只有2个盘子,柱子分别是A, B, C柱

  • java数据结构和算法学习之汉诺塔示例

    复制代码 代码如下: package com.tiantian.algorithms;/** *    _|_1              |                | *   __|__2             |                | *  ___|___3            |                |            (1).把A上的4个木块移动到C上. * ____|____4           |                | *    

  • Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

    本文实例讲述了Java基于栈方式解决汉诺塔问题.分享给大家供大家参考,具体如下: /** * 栈方式非递归汉诺塔 * @author zy * */ public class StackHanoi { /** * @param args */ public static void main(String[] args) { System.out.println("我们测试结果:"); System.out.println("递归方式:"); hanoiNormal(

  • C++基于递归算法解决汉诺塔问题与树的遍历功能示例

    本文实例讲述了C++基于递归算法解决汉诺塔问题与树的遍历功能.分享给大家供大家参考,具体如下: 递归是把问题转化为规模缩小的同类问题,然后迭代调用函数(或过程)求得问题的解.递归函数就是直接或间接调用自身的函数. 递归两要素:递归关系和递归边界(终止条件),递归关系确定了迭代的层次结构,需要深入了解并分解问题:终止条件保证了程序的有穷性. 递归的应用有很多,常见的包括:阶乘运算.斐波那契数列.汉诺塔.数的遍历,还有大名鼎鼎的快排等等.理论上,递归问题都可以由多层循环来实现.递归的每次调用都会消耗

  • java基于递归算法实现汉诺塔问题实例

    本文实例讲述了java基于递归算法实现汉诺塔问题.分享给大家供大家参考,具体如下: package test; import java.util.List; import java.util.ArrayList; import java.util.Scanner; import sun.net.www.content.audio.x_aiff; /** * @author 年浩 * */ public class test { public static void move(char x,cha

  • Java用递归方法解决汉诺塔问题详解

    目录 前言 一.问题描述 二.问题分析 三.解决方案 四.示例 前言 博主之前有写过关于递归问题的思维模式: 递归的思路 下面将用这种思维模式来求解经典汉诺塔问题. 一.问题描述 汉诺塔(又称河内塔)问题是源于印度一个古老传说.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘. 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上. 并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘. 问应该如何操作? 玩法如下: 1.有三

随机推荐