satan

看到这样的一个题：
从1到100000中任意拿掉两个数字，把剩下99998个数的顺序打乱并且放到数组中，要求只扫描一遍，把这个两个数找出来，可以使用最多不超过5个局部变量，不能使用数组变量并且不能改变数组的值。

刚看到这个题， 瞬间想到， 我们遍历1-100000,不就能把这两个数找出来了么，再看看不对呀，是把剩下的99998 个数乱序放在数组中的， 还不能修改数组的值。这可麻烦了。

那既然是乱序的，那就不能从单个数上考虑了， 也许可以从整体上考虑吧。
只是缺了两个数， 用原数组的和减去新的数组的和不就是这两个数的和了。
a+b=Q (1)

哈哈， 一个二元一次方程， 还差一个方程。
跟上面的思路一样， 用原数组的乘积除于新的数组的乘积就是这两个数的乘积
a * b = P (2)
这可麻烦了， 阶乘是多大的数呀， 程序那不溢出了，那拆成子项试试
i/arr[i] * (i+1) /arr[i+1] * …
实验了一下， 从1开始的话， 这个数就变0 了，
从999998 开始， 这个数就无穷大了。

这个头大了， 进行不下去了。

n 个小时后……

还是得会到加号上来， 我可以先平方嘛。哈哈， 对， 先平方后一减， 可得
a^2 + b^2 = P (3)

（1）(3)方程联合， 立马可以解得了。

问题是这样的：
有三个瓶子， 分别可以装 12L, 8L和5L 的酒， 现在12 L 的瓶子装满了酒，他们都没有刻度， 现在要用这几个瓶子倒出两个6L 的酒来。

用人来做的话还是不难的， 用机器来做就要把这个问题抽象一下了。先上代码吧， 至于思路有放假回来再慢慢整。

#include 
using namespace std;

//三个瓶子以0，1，2标识

/*int V[3]={12,8,5};//三个瓶子的容积*/
int V[3]={8,5,3};//三个瓶子的容积
int objnum = 3;

//可能的倒酒方式有6种，从src[i]到dest[i]
int src[6] ={0,0,1,1,2,2};
int dest[6]={1,2,0,2,0,1};

int record[100][3];//record[i][0~2]记录三个瓶子盛酒的状态
int rec_index=0;//已知的状态数

//从a瓶倒酒到b瓶
void Pour(int state[],int a,int b)
{
	// 还剩这么多可以倒过来
    int r=V[b]-state[b];
	// 可以倒得比还剩的少， 把被倒杯的都倒过来
    if(state[a]
													

在一个8 × 8 的国际象棋棋盘上， 放8 个皇后， 让她们彼此不能吃到对方（皇后的走法是可以吃到直线包括横线上的棋子），下面是一个合法的例子:

5 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 5
0 0 0 0 0 5 0 0
0 0 5 0 0 0 0 0
0 0 0 0 0 0 5 0
0 5 0 0 0 0 0 0
0 0 0 5 0 0 0 0

这个问题的解法还是比较简单的， 逐行放置合法的棋子， 直到8个合法的棋子都放完。
基于这个， 很容易就想到一个递归的解法，在当前已有的选择中找一个合法的位置。
当然递归的都可以化为非递归的， 当然要自己模拟栈的情况了。

递归算法
递归算法有几个重要的点：进入递归的条件， 递归退出的条件，退栈的时候要处理什么
这里是这个问题相对应的：
进入递归的条件：找到了一个合法的位置 valid(tmp)
递归退出的条件： 找到了一组合法的组合或者当前路径无法找到合法的组合 rec_index == 8
退栈的时候要处理什么： 把找到的合法个数减一 rec_index–;

#include 
using namespace std;

// 保存结果
int record[8][2];
// 保存已经选中了的元素的个数
int rec_index = 0;

// 验证当前行是否合法
bool valid(int a[]) {
	for (int i = 0; i < rec_index; i++) {
		int p0 = a[0] - record[i][0];
		int p1 = a[1] - record[i][1];
		// 不能在一条线上， 横竖
		if((p0 == 0) || (p1==0) ||  (p0 == p1) || (p0 == -p1)) {
			return false;
		}
	}
	return true;
}

void CopyArr(int ori[], int dest[], int length) {
	for ( int i = 0; i < length; i++) {
		dest[i] = ori[i];
	}
}

// 记录选择元素
void Record(int a[]) {
	CopyArr(a, record[rec_index], 2);
}

void Output()
{
    for(int i=0;i
非递归版本

非递归要自己处理退栈 popstack(i, q)， 在找到了一组合法的组合或者当前路径无法找到合法的组合的时候
#include 
using namespace std;

// 保存结果
int record[8][2];
// 保存已经选中了的元素的个数
int rec_index = 0;

// 验证当前行是否合法
bool valid(int a[]) {
	for (int i = 0; i < rec_index; i++) {
		int p0 = a[0] - record[i][0];
		int p1 = a[1] - record[i][1];
		// 不能在一条线上， 横竖
		if((p0 == 0) || (p1==0) ||  (p0 == p1) || (p0 == -p1)) {
			return false;
		}
	}
	return true;
}

void CopyArr(int ori[], int dest[], int length) {
	for ( int i = 0; i < length; i++) {
		dest[i] = ori[i];
	}
}

// 记录选择元素
void Record(int a[]) {
	CopyArr(a, record[rec_index], 2);
}

void Output()
{
    for(int i=0;i=0) {
		bool found =  false;
		for (int j = q; j < 8; j++) {
			// 记录当前状态
			int tmp[] = {i,j};
			// 检查当前元素是否是合法的
			if(valid(tmp)) {
				// 当前元素合法， 记录它
				Record(tmp);
				i++;
				found = true;
				// 这一行找到了， 到下一行的开始去找
				q = 0;
				rec_index++;
				break;
			}
		}
		// 退栈操作
		if(!found) {
			popstack(i, q);
		}
		// 找到一组答案
		if(found && (rec_index == 8)) {
			Output();

			// 只找一个结果
			if(!all) {
				break;
			} else {
				// 找出所有的结果
				popstack(i, q);
			}
		}
	}

	return false;
}

int main() {
	Solve(true);
	return 0;
}