八皇后问题的递归解决(低效)

#include <iostream>
/**
*@author c0rpse
*@date 2015/9/22 23:14
*@usage A way to resolve the EightQueen Problem.
*/

using namespace std;
unsigned int cnt = 0;
int isSafe(int row, int col, int(*chess)[8]){
int i = 0, j;
//判断列方向有没有危险点
for (i = 0; i<8; ++i){
if (*(*(chess + i) + col) != 0){
//flag+col=1;
//break;
return 0;
}
}
//判断该坐标左上方有没有危险
for (i = row, j = col; i >= 0 && j >= 0; –i, –j){
if (*(*(chess + i) + j) != 0) return 0;
}
//判断该坐标右下方有没有危险
for (i = row, j = col; i<8 && j<8; ++i, ++j){
if (*(*(chess + i) + j) != 0) return 0;
}
//判断该坐标右上方有没有危险
for (i = row, j = col; i >= 0 && j<8; –i, ++j){
if (*(*(chess + i) + j) != 0) return 0;
}
//判断该坐标左下方有没有危险
for (i = row, j = col; i<8 && j >= 0; ++i, –j){
if (*(*(chess + i) + j) != 0) return 0;
}
return 1;
}
void eightQueen(int row, int col, int(*chess)[8]){

int i, j, chess2[8][8];//chess2为新棋盘,其复制了传入的chess棋盘
for (i = 0; i<8; ++i){
for (j = 0; j<8; ++j){
chess2[i][j] = chess[i][j];
}
}
if (row == 8){
//如果已经到达棋盘最后,那么输出棋盘
cout << “第” << cnt + 1 << “种摆法步骤” << endl;
for (i = 0; i<8; ++i){
for (j = 0; j<8; ++j){
cout << *(*(chess2 + i) + j) << ” “;
}
cout << endl;
}
cout << endl;
++cnt;
}
else {
for (j = 0; j<col; ++j){//对该行的每一列进行尝试
if (isSafe(row, j, chess)){
//在尝试前首先重置该行所有坐标为0,因为上次循环可能会改变该行坐标的值
for (i = 0; i<8; ++i){
*(*(chess2 + row) + i) = 0;
}
*(*(chess2 + row) + j) = 1;
eightQueen(row + 1, col, chess2);//递归测试下一行
}
}
}
}
int main()
{
int i, j, chess[8][8];
for (i = 0; i<8; ++i){
for (j = 0; j<8; ++j){
chess[i][j] = 0;
}
}
eightQueen(0, 8, chess);
return 0;
}

汉诺塔的递归解决

一位法国数学家曾编写过一个印度的古老传说:在世界中心贝拿勒斯的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。

不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。

僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

继续阅读“汉诺塔的递归解决”

c++的左值与右值

C++左值与右值的含义与误区

术语 “L-Values” 和 “R-Values” 是很容易被搞混的,因为它们的历史渊源也是混淆。他们最初起源是编译器的设计者,从字面上来理解就是表达式左边的值和表达式右边的值。它们的含义一直在演 化而名字却没变,现在已经“名”不副“实”了。虽然还是称为left-value 和right-value,但是他们的含义已经大大不同了。

C++ 03 标准上是这样写的: “每一个表达式要么是一个 lvalue,要么就是一个 rvalue。”

记住,lvalue和rvalue是针对表达式而言的。

lvalue 是指那些单一表达式结束之后依然存在的持久对象。例如: obj,*ptr, prt[index], ++x 都是 lvalue。

rvalue 是指那些表达式结束时(在分号处)就不复存在了的临时对象。例如:1729 , x + y , std::string(“meow”) , 和 x++ 都是 rvalue。

++x 和 x++ 的区别的语义上的区别: 当写 int i = 10 ; 时, i 是一个 lvalue,它实际代表一个内存里的地址,是持久的。 表达式 ++x 也是一个 lvalue,它修改了 x 的值,但还是代表原来那个持久对象。但是,表达式 i++ 却是一个 rvalue,它只是拷贝一份i的初值,再修改i的值,最后返回那份临时的拷贝,那份拷贝是临时对象。 ++i 和 i++ 都递增i,但 ++i 返回i本身,而 i++ 返回临时拷贝。这就是为什么 ++i 之所以是一个 lvalue,而 i++ 是一个 rvalue。

lvalue 与 rvalue 之分不在于表达式做了什么,而在于表达式代表了什么(持久对象或临时产物)。

判断一个表达式是不是 lvalue 的直接方法就是“能不能对表达式取址?”。如果能够,那就是一个 lvalue;如果不能,那就是一个 rvalue。