f(-----)=false
显然,对于任意一个棋局,我们生成其所有的多放一个皇后之后的棋局.如果这些新生成的棋局中有任何一个可以放到n个皇后,那么,该棋局可以放到n个皇后.而新生成的棋局可不可以放到n个皇后可以用我们假装出来的解决方案(函数f)来解决.如果f对某个棋局返回true,我们说这个棋局是可行的.否则说它是不可行的.再给出边界条件:对存在n个互不攻击的皇后的棋局返回true,对存在可以互相攻击的皇后的棋局返回false.所以,这个问题的递归代码为:bool f(棋局) {
判断边界条件, 如果满足, 返回true或者false;
for_each (棋局中所有的空位) {
在空位上放上皇后, 生成新的棋局;
if ( f(新的棋局) )
return true;
}
return false;
}
当然,为了实现这个算法,我们还有一些问题,第一个问题就是棋局的表示.当然,我们可以用一个n*n的数组来保存整个棋局.不过,如果注意到对于任意合法的方案,每一行中有且只有一个皇后,那么,我们只要一个大小为n的int数组保存每一行中那个皇后所在的位置就可以了.另外,在函数中的for循环上,我们也不用枚举所有的空位,而只要在现在棋局的某一个空行中找一个空位就可以了.
还可以进一步的优化:只要找到行号最小的空行,并枚举其中的空位就可以了.这是因为在在一个解中,每行必然存在一个皇后.所以,如果某个棋局最后是可行的,在其行号最小的空行的空行中必然能够找到一个位置放下皇后,使得新的棋局最后是可行的.也就是说,一个棋局是可行的,等价于在其行号最小的空行中的所有位置放下皇后得到的新棋局中,至少有一个是可行的.
经过了优化之后,我们的代码变成了:bool f( int* 每行皇后所在位置,未放皇后的做特殊标记(棋局的一种表示方式) ) {
判断边界条件, 如果满足, 返回true或者false;
int row = 棋局中最小空行的行号
for_each (第row行的空位) {
在空位上放上皇后, 生成新的棋局;
if ( f(新的棋局) )
return true;
}
return false;
}
如果把f的int*参数叫做board,那么,即bool f( int* board ) {
判断边界条件, 如果满足, 返回true或者false;
int row = 棋局中最小空行的行号
for_each (第row行的空位) {
在空位上放上皇后, 生成新的棋局 new_board;
if ( f(new_board) )
return true;
}
return false;
}
你会发现,如果在第三行中求出的row是x的话,那么,对于第6行中的f,它求出来的row肯定是x+1,我们也不要为难它,让它再算一次了.我们告诉它好了.而且这样的话,就有人帮我自己算了.与人为善确实是有好处的.bool f( int* board, int row ) {
判断边界条件, 如果满足, 返回true或者false;
for_each (第row行的空位) {
在空位上放上皇后, 生成新的棋局 new_board;
if ( f(new_board, row+1) )
return true;
}
return false;
}
注意,如果这个时候再考虑f的话,f的含义已经改变了.f现在的意义是,对于一个从第0行到第row-1行都已经放上一个皇后的棋局board,我来判定它是不是可行的.这相当于在第row行放上新的皇后,产生新的棋局,如果新的棋局中有一个是可行的,那么我现在的board就是可行的.要不然就是不可行的.
另一个技巧是不用显式地生成new_board,只要修改board,最后再把它恢复就好了.bool f( int* board, int row ) {
判断边界条件, 如果满足, 返回true或者false;
for_each (第row行的空位pos) {
board[row] = pos;
if ( f(board, row+1) )
return true;
board[row] = EMPTY;
}
return false;
}
这样的话,其实每个f的board都是一样的,我们可以把它弄成全局变量.我说的只是=可以=哦.intboard[n];bool f(int row ) {
判断边界条件, 如果满足, 返回true或者false;
for_each (第row行的空位pos) {
board[row] = pos;
if ( f(row+1) )
return true;
board[row] = EMPTY;
}
return false;
}
这一次,虽然f的参数表变了,不过它的含义没有变,因为我们只是把一个函数变成了隐含的.
我就不继续写了,如果你继续优化,最后会得到书上那个解法哦^_^.
最后是三个小小的,有些生硬的练习:1.N皇后问题,即给出可行的方案数,而不仅仅是是否存在可行方案.
2.用递归实现后缀表达式的求值后缀表达式的形式为算符后缀表达式_1后缀表达式_2.一个后缀表达式的值为,将后缀表达式_1的值和后缀表达式_2的值进行算符所指的操作.
在这个练习里,递归的方式是直截了当的.但是,有一个小小的问题:我们不知道后缀表达式_1和后缀表达式_2在哪里分隔开来.努力一下吧^_^要是老想不出也不要慌张....我也许出错题了_
3.在我们上面的讨论中,没有考虑那里才是合适的边界.事实上,确定边界也是非常重要的,合适的边界可以使解决问题变得更简单,也更容易保证递归的可终止性.考虑一下上面几个例子和你的练习中,是不是所有的边界都是必要的,有没有可能用新的边界代替旧的.并给出上面这些递归方案一定会终止的证明.
最后补充一下:TheLittleScheme确实是一本好书!
wdswds (wds2006sdo) 在 ta 的帖子中提到：RT |
