这个到底是怎么回事,php 8皇后问题代码引起的疑问。

泡不烂的凉粉 发布于 2012/04/04 20:09
阅读 254
收藏 0
PHP

<?php

$q = 8;
$l = array();
$c = 0;

f(0);

echo $c;


function f($n) {
	global $q, $l, $c;

	if($n < $q) {
		for($l[$n] = 0; $l[$n] < $q; $l[$n]++) {
			if(c($n)) {
				f($n + 1);			/* 正确的代码 */
				// f(++$n);			/* 这一行我特别郁闷, 难道 ($n+1)和(++$n) 不能互换?*/
			}
		}
	}
	else {
		$c++;
	}
}

function c($n) {
	global $q, $l, $c;
	for($i = 0; $i < $n; $i++) {
		if(($l[$i] == $l[$n] || $l[$i] - $l[$n] == $i - $n || $l[$i] - $l[$n] == $n - $i )) return false;
	}
	return true;
}

?>

尝试用php代码解决8皇后 问题。

写完后仔细审核逻辑,没发现有什么遗漏。

结果就是运行不成功 。 无奈,上网找点范例参考。

按照范例稍微修改,结果还是不行。

最后 被一个 语法给坑了。实在是不明白, 难道是 BUG ? 还是我php版本有问题。

百思不得其解 ,只好把代码放出来求大家分析一下, 错误重现代码。 原版。没有修改以及深入分析。求大家帮忙分析产生的原因。。

 问题产生在 18,19行。 f($n + 1) 和 f(++$n) 的区别。 我真的晕了。 求分析。

加载中
0
deleted
deleted
++n改变了n本身, n+1不变
0
泡不烂的凉粉
泡不烂的凉粉
 一语点醒梦中人。 
0
泡不烂的凉粉
泡不烂的凉粉

这个效率高不少。

有兴趣的可以自己运行做一下比较。 12皇后感觉就很明显了。

<?php

$q = 8;
$l = array();
$c = 0;

f(0);



echo $c;


function f($n) {
	global $q, $l, $c;

	if($n < $q) {
		for($l[$n] = 0; $l[$n] < $q; $l[$n]++) {
			for($i = 0; $i < $n; $i ++) {
				if(($l[$i] == $l[$n] || $l[$i] - $l[$n] == $i - $n || $l[$i] - $l[$n] == $n - $i )) continue 2;
			}
			f($n+1) ;
		}
	}
	else {
		$c++;
	}
}

?>

0
泡不烂的凉粉
泡不烂的凉粉
<?php
function f($q) {
	static $c = 0; /* 计数器, 解个数 */
	static $l = array(); /* 当前皇后存在的列, 键名记录行 */
	static $n = 0; /* 当前皇后,从0计数,表示第一个 */ 

	/* 尝试放入皇后 */
	for($l[$n] = 0; $l[$n] < $q; $l[$n]++) {
		/* 验证皇后是否可以放入*/
		for($i = 0; $i < $n;$i++) {
			/* 验证是否可放入,冲突直接跳出本次筛选 */
			if(($l[$i] == $l[$n] || $l[$i] - $l[$n] == $i - $n || $l[$i] - $l[$n] == $n - $i )) continue 2;
		}
		/* 验证通过,可以放置本次 */

		/* 如果没有达到最后一个 */
		if($n < ($q - 1)) {
			$n++; /* 下一个皇后 */
			f($q);
			$n--; /* 本层还有其他位置要验证, 还原后继续验证本层 */
		}
		/* 达到最后一个, 计数器+1 */
		else {
			$c++;
		}
	}
	return $c;
}

加注释改进版, 放弃用 全局变量, 自己控制堆, 方便移植,  效率无提高。
0
泡不烂的凉粉
泡不烂的凉粉

构造成函数的代码存在一个BUG  , 没有正确初始化变量。
 被本站会员 @曹林剑 发现,现修正代码如下:

<?php
function f($q, $f = false) { /* $f 是标记,如果为 false 将重新初始化 */
	static $c = 0; /* 计数器, 解个数 */
	static $l = array(); /* 当前皇后存在的列, 键名记录行 */
	static $n = 0; /* 当前皇后,从0计数,表示第一个 */ 

	/* BUG FIX 增设初始化内容,感谢 @曹林剑  发现此BUG */
	if(!$f) {
		$c = 0;
		$l = array();
		$n=0;
	}

	/* 尝试放入皇后 */
	for($l[$n] = 0; $l[$n] < $q; $l[$n]++) {
		/* 验证皇后是否可以放入*/
		for($i = 0; $i < $n;$i++) {
			/* 验证是否可放入,冲突直接跳出本次筛选 */
			if(($l[$i] == $l[$n] || $l[$i] - $l[$n] == $i - $n || $l[$i] - $l[$n] == $n - $i )) continue 2;
		}
		/* 验证通过,可以放置本次 */

		/* 如果没有达到最后一个 */
		if($n < ($q - 1)) {
			$n++; /* 下一个皇后 */
			f($q, true); /* 第2个参数表示不会破坏内部存放数值*/
			$n--; /* 本层还有其他位置要验证, 还原后继续验证本层 */
		}
		/* 达到最后一个, 计数器+1 */
		else {
			$c++;
		}
	}
	return $c;
}

/* f(8); 可以返回 8 皇后解个数, 要想知道所有解, 可 在  "达到最后一个,计算器+1" 部分获取解详情。 */

返回顶部
顶部