`
airpeng
  • 浏览: 14403 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

递归调用(为什么会StackOverflowError)——八皇后算法

阅读更多
为什么我的这个算法有时会StackOverflowError,代码如下
package algorithm;

public class EightQueen {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		EightQueen self = new EightQueen();
		for(int i=12;i<13;i++){
			self.queen(i);
		}
	}
	
	public void queen(int n){
		System.out.println("======== "+n+" ========");
		int[][] grid = new int[n][n];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				grid[i][j] = 0;
			}
		}
		init(grid,0,0,false,n);

		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(grid[i][j]==1){
					System.out.print(" + ");
				}else{
					System.out.print(" - ");
				}
			}
			System.out.println();
		}
	}
	
	public void init(int[][] grid,int horizontal,int vertical,boolean isBack,int size){
		if(isBack){
			if(horizontal==28&&vertical==16){
				System.out.println();
			}
			grid[horizontal][vertical] = 0;
			vertical++;
		}
		if(vertical>=size){
			horizontal--;
			if(horizontal<0){
				System.out.println("No result!");
				return ;
			}
			for(int i=0;i<size;i++){
				if(grid[horizontal][i]==1){
					init(grid,horizontal,i,true,size);
					return ;
				}
			}
		}
		for(int i=0;i<horizontal;i++){
			for(int j=0;j<size;j++){
				if(grid[i][j]==1&&!isFree(horizontal,vertical,i,j)){
					init(grid,horizontal,vertical,true,size);
					return ;
				}
			}
		}
		grid[horizontal][vertical] = 1;
		System.out.println(horizontal+":"+vertical);
		if(++horizontal>=size){
			return ;
		}
		init(grid,horizontal,0,false,size);
		return ;
	}
	
	private boolean isFree(int x,int y,int holdX,int holdY){
		if(x==holdX||y==holdY){//同一横排或竖排
			return false;
		}
		int slant1 = (x-holdX)-(y-holdY);
		int slant2 = (x-holdX)+(y-holdY);
		if(slant1==0||slant2==0){//两条斜线
			return false;
		}
		return true;
	}

}
分享到:
评论
1 楼 airpeng 2011-11-17  
下面这个确MS很好用
package algorithm;

public class Queen_Java {

	int QUEEN_COUNT = 20; // 是多少皇后
	static final int EMPTY = 0;
	int[][] count = new int[QUEEN_COUNT][QUEEN_COUNT];
	int[] QueenIndex = new int[QUEEN_COUNT];
	int resultCount = 0;
	long time = System.currentTimeMillis();

	public void putQueenIndex(int row) {
		for (int col = 0; col < QUEEN_COUNT; col++) {
			if (count[row][col] == EMPTY) {
				for (int iRow = row + 1; iRow < QUEEN_COUNT; iRow++) {
					count[iRow][col]++;
					if ((col - iRow + row) >= 0) {
						count[iRow][col - iRow + row]++;
					}
					if ((col + iRow - row) < QUEEN_COUNT) {
						count[iRow][col + iRow - row]++;
					}
				}
				QueenIndex[row] = col;
				if (row == QUEEN_COUNT - 1) {
					print(++resultCount);
				} else {
					putQueenIndex(row + 1);
				}
				for (int iRow = row + 1; iRow < QUEEN_COUNT; iRow++) {
					count[iRow][col]--;
					if ((col - iRow + row) >= 0) {
						count[iRow][col - iRow + row]--;
					}
					if ((col + iRow - row) < QUEEN_COUNT) {
						count[iRow][col + iRow - row]--;
					}
				}
			}
		}
		if (row == 0) {
			System.out.println(QUEEN_COUNT + "皇后共有 " + resultCount + " 个解\n"
					+ (System.currentTimeMillis() - time) + "毫秒");
		}
	}

	public void print(int n) {
		System.out.println(QUEEN_COUNT + "皇后的第 " + n + " 个解:");
		for (int i = 0; i < QUEEN_COUNT; i++) {
			for (int j = 0; j < QUEEN_COUNT; j++) {
				System.out.print(QueenIndex[i] == j ? " * " : " - ");
			}
			System.out.println();
		}
		System.out.println();
	}

	public static void main(String[] args) {
		new Queen_Java().putQueenIndex(0);
	}
}

相关推荐

    递归算法举例——八皇后问题详解

    递 归 算 法 举 例——八皇后问题详解,和大家分享~

    数据结构课程设计——八皇后问题

    数据结构课程设计——八皇后问题是一项经典的编程任务,旨在锻炼学生的算法设计能力、程序调试技巧以及对数据结构的理解。八皇后问题源于19世纪数学家高斯提出的一个挑战,目标是在8x8的棋盘上放置8个皇后,使得任何...

    如何解决java.lang.StackOverflowError

    在Java编程中,`java.lang.StackOverflowError` 是一个常见的运行时异常,它通常发生在程序执行过程中,当Java虚拟机(JVM)的调用栈溢出时。调用栈是每个线程用来存储方法调用信息的数据结构,当递归调用过深或者...

    系统稳定性——StackOverFlowError常见原因及解决方法1

    【系统稳定性——StackOverFlowError常见原因及解决方法】 在Java编程中,系统稳定性是至关重要的,而StackOverflowError是一个常见的运行时错误,通常由于内存管理问题导致。本篇文章将详细探讨StackOverflowError...

    八皇后问题 递归算法 可以输入皇后的值

    八皇后问题 递归算法 可以输入皇后的值 输出排列的结果

    八皇后递归算法C代码实现

    八皇后递归算法C代码实现 输出格式如下: |Q| | | | | | | | | | | | |Q| | | | | | | | | | | |Q| | | | | | |Q| | | | | |Q| | | | | | | | | | | | |Q| | | |Q| | | | | | | | | | |Q| | | | | linux终端输出...

    8皇后算法的非递归算法

    用非递归解决八皇后的问题,是经典的非递归算法,学习数据结构中很有用

    算法进阶 01 递归调用 打表

    在编程领域,算法是解决问题的关键,而递归调用是算法设计中的一种重要技术。递归调用是指函数或方法在执行过程中调用自身的过程,它通常用于解决那些可以通过简化问题规模来解决的问题。本节将深入探讨递归调用的...

    八皇后问题——递归解决

    用递归解决八皇后问题的一段代码,专门写了较为详细的注释,本人原创,如有雷同,纯属巧合。

    八皇后问题实验报告递归非递归javaC语言+分析可用.pdf

    八皇后问题有多种解决方案,包括递归算法和非递归算法。递归算法使用递归函数来尝试不同的皇后摆放方式,而非递归算法则使用循环来实现皇后摆放。 3.递归算法的实现 递归算法的实现需要使用递归函数来尝试不同的皇后...

    java八皇后递归算法

    不是很好的一个java八皇后算法!! 不过觉对是真的哦

    一个简单的递归调用的实例

    这就是递归的核心——函数在内部调用自身,每次调用处理规模更小的问题(即更深层的子目录)。 递归调用在处理树形结构时非常有用,例如文件系统、组织结构或者HTML DOM等。然而,需要注意的是,递归可能会导致大量...

    八皇后的非递归

    八皇后的非递归代码:全部代码分享,方便各位java初学者学习

    递归算法解决八皇后问题

    用递归解决八皇后 蛮简单的 用递归解决八皇后 蛮简单的用递归解决八皇后 蛮简单的用递归解决八皇后 蛮简单的用递归解决八皇后 蛮简单的用递归解决八皇后 蛮简单的

    斐波那契递归时间和非递归时间的比较(csdn)————程序.pdf

    递归算法是通过调用自身来解决问题的。在斐波那契数列的递归版本中,第 `n` 项 `Fib(n)` 被定义为前两项 `Fib(n-1)` 和 `Fib(n-2)` 的和。这种方法在计算较小的斐波那契数时工作良好,但由于重复计算了大量的子问题...

    .net 递归算法 .net 递归算法.net 递归算法

    - **回溯法**:在解决组合优化问题,如八皇后问题、N皇后问题、迷宫问题时,递归结合回溯可以找出所有可能的解决方案。 递归算法在使用时需要注意几个关键点: - **效率**:递归可能导致大量的函数调用,增加内存...

    经典算法八皇后问题的详解以及回溯(递归)代码示例

    对经典算法八皇后问题的说明,以及代码示例,代码中有详尽的注释,有助于读者充分理解其递归调用的逻辑!

    八皇后算法C语言实现

    在实现过程中,可能会遇到效率问题,因为八皇后问题有92种解,如果算法设计不当,可能需要较长的时间才能找出所有解。题目中提到花了两天时间写出的实现可能是因为算法效率较低或者存在冗余计算。 优化策略包括使用...

    递归调用详解,分析递归调用的详细过程

    递归调用详解,代码详细讲解了如递归调用以及调用中应该注意的一些问题

    八皇后算法

    八皇后算法,使用递归算法,delphi面向对象实现

Global site tag (gtag.js) - Google Analytics