========================================
1、1,2,3...n入栈，问有多少种出栈的可能性，递归式和解析式。
原理：
有：h(0)=1, h(1)=1, h(2)=2, h(3)=5, 14, ...
- 递推关系的解为： h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
- 递推关系的另类解为： h(n)=c(2n,n)-c(2n,n+1)(n=1,2,3,...)
应用：
关键是把原问题分解成不相交的子问题的并集。
举例：
- n个数的入栈问题——假如数k为第一个出栈的数，那么k把1~n分成了两组，1~k-1和k+1~n，而k可取1~n中的任意数，故：f(n) = f(0)*f(n-1) + f(1)*f(n-2) + f(2)*f(n-3) + ... + f(n-1)*f(0), 令f(0)=f(1)=1;我们有f(n) = h(n).
- 矩阵乘法的括号化问题——每次用两个括号，把a1~an分成两份，a1~ak，ak+1~an，k=1,2,3...n-1，而这两段又组成了两个独立的子问题。于是：f(n) = f(1)*f(n-1) + f(2)*f(n-2) + ... f(n-1)*f(1),令f(1)=1. 我们有f(n) = h(n-1).
- n个节点构造二叉树问题——此处应该是认为每个节点都一样。取出根节点，设左子树有k个节点k=0,1,2,...n-1，则右子树有n-k-1个节点，故：f(n) = f(0)*f(n-1) + f(1)*f(n-2) +... + f(n-1)*f(0),令f(0)=1；我们有f(n) = h(n).
- 常见的例子还有：买票找零问题，凸多边形三角划分问题，不越过对角线的上班路线问题。
========================================
2、八皇后问题——递归解和非递归解
下面两个程序分别来自于：
程序注释比较详细，不再赘述，直接上代码吧。
递归解
// 回溯法解八皇后问题。
/* Code by Slyar */
#include <stdio.h>
#include <stdlib.h>
#define max 8
int queen [max], sum=0; /*
max 为棋盘最大坐标，queen[i]标识第i行的皇后放置在第queen[i]列 */
max 为棋盘最大坐标，queen[i]标识第i行的皇后放置在第queen[i]列 */
void show () /* 输出所有皇后的坐标 */
{
int i ;
for(i =
0; i < max; i ++)
0; i < max; i ++)
{
printf("(%d,%d)
" , i, queen[i ]);
" , i, queen[i ]);
}
printf("\n" );
sum++;
}
int check (int n) /* 检查当前列能否放置皇后 */
{
int i ;
for(i =
0; i < n; i ++) /* 检查横排和对角线上是否可以放置皇后 */
0; i < n; i ++) /* 检查横排和对角线上是否可以放置皇后 */
{
if(queen [i]
== queen[n ]
|| abs( queen[i ]
- queen[ n])
== (n - i))
== queen[n ]
|| abs( queen[i ]
- queen[ n])
== (n - i))
{
return 1;
}
}
return 0;
}
void put (int n) /* 回溯尝试皇后位置 ,n为横坐标*/
{
int i ;
for(i =
0; i < max; i ++)
0; i < max; i ++)
{
queen[n ]
= i; /* 将皇后摆到当前循环到的位置 */
= i; /* 将皇后摆到当前循环到的位置 */
if(!check (n))
{
if(n == max -
1)
1)
{
show(); /* 如果全部摆好，则输出所有皇后的坐标 */
}
else
{
put(n +
1); /* 否则继续摆放下一个皇后 */
1); /* 否则继续摆放下一个皇后 */
}
}
}
}
int main ()
{
put(0); /* 从横坐标为开始依次尝试 */
printf("%d" , sum);
system("pause" );
return 0;
}
非递归解:
/**
* 回溯法解N 皇后问题
* 使用一个一维数组表示皇后的位置
* 其中数组的下标表示皇后所在的行
* 数组元素的值表示皇后所在的列
* 这样设计的棋盘，所有皇后必定不在同一行，于是行冲突就不存在了
* date : 2011-08-03
* author: liuzhiwei
**/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define QUEEN 8 //皇后的数目
#define INITIAL -10000 //棋盘的初始值
int a [QUEEN]; //一维数组表示棋盘
void init () //对棋盘进行初始化
{
int *p ;
for (p = a; p < a + QUEEN;
++ p)
++ p)
{
* p = INITIAL ;
}
}
int valid (int row, int col) //判断第row 行第col列是否可以放置皇后
{
int i ;
for (i =
0; i < QUEEN;
++i ) //对棋盘进行扫描
0; i < QUEEN;
++i ) //对棋盘进行扫描
{
if (a [i]
== col || abs (i - row)
== abs (a[ i]
- col )) //判断列冲突与斜线上的冲突
== col || abs (i - row)
== abs (a[ i]
- col )) //判断列冲突与斜线上的冲突
return 0;
}
return 1;
}
void print () //打印输出 N皇后的一组解
{
int i , j;
for (i =
0; i < QUEEN;
++i )
0; i < QUEEN;
++i )
{
for (j =
0; j < QUEEN;
++j )
0; j < QUEEN;
++j )
{
if (a [i]
!= j) //a[i] 为初始值
!= j) //a[i] 为初始值