程序员面试题精选100题

2024年3月29日发(作者：罗大力)

是事先无法确定究竟需要进行多少步；还有著名的8数码问题（文曲星上的那个9x9方格中

移数字的游戏），那个问题也是预先不知道需要移动多少步才能达到目标。不过这并不影响

回溯法的使用，只要该问题有解，一定可以将解用有限的变元来表示，我们可以假设n就是

问题的一个解的变元的个数，这样就可以继续利用上面的搜索树模型了。事实上，这棵搜索

树并非预先生成的，而是在搜索的过程中逐步生成的，所以不知道树的深度n并不影响在树

中搜索叶子节点。但是有一点很重要，如果问题根本不存在有限的解，或者问题的状态空间

无穷大，那么沿着某条道路从根出发搜索叶节点，可能永远无法达到叶结点，因为搜索树会

不断地扩展，然而叶结点也许是确实存在的，只要换一条道路就可以找到，只不过一开始就

走错了路，而这条错路是永远无法终止的。为了避免这种情况我们一般都规定状态空间是有

限的，这样即使搜索整个状态空间的每个状态也可以在有限时间内完成，否则的话回溯法很

可能不适用。

搜索树的每一个节点表示一个状态，节点i要生成节点j必须满足约束集D中的约束条件，

我们也可以将这个约束条件称为“状态转移规则”或者“产生规则”（意指从节点i产生节点j

的规则，这是从“产生式系统”理论的角度来解释回溯法）。因此回溯法的实质是在一个状态

空间中，从起始状态（搜索树的根）搜索到一条到达目标状态（搜索树的叶结点）的路径（就

和走迷宫差不多，这是从图论的角度来解释回溯法）。一般来说，为了防止搜索的过程中出

现回路，必须记录已经走过的节点（状态），在同一条路径中不能重复走过的节点（状态），

这样只要状态空间是有限的，回溯法总是可以终止的。

======================================================================

=====================

下面我们就根据回溯法来解决这个喝酒问题

（1）状态的表示

一个状态用一个7元组表示 X=（x1,x2,x3,x4,x5,x6,x7)；，其中x1~x3分别表示a,b,c三个酒

瓶中的酒，x4~x7分别表示A,B,C，D四个人已经喝的酒；

（2）约束条件

1。每个人喝的酒不能超过4两；

2。每个瓶中容纳的酒不能超过该瓶的容量；

为了方便设第k个人喝的酒不超过C[k], 第i个酒瓶的容量为C

，

则

C[1]=C[2]=8, C[3]=3, C[4]=C[5]=C[6]=C[7]=4;

约束条件为

0<= X <= C;

（

3

）状态的转移规则（状态产生规则）

从某个状态

X

转移到另一个状态

Y

有以下几种情况：

1

。

i

瓶中的酒倒入

j

瓶中，并将

j

瓶装满

: Y = X - (C[j]-X[j]) , Y[j] = C[j], i,j

∈

[1,3]

2

。

i

瓶中的酒倒入

j

瓶中，并将

i

瓶倒空

: Y = 0 , Y[j] = X[j] + X , i,j

∈

[1,3]

3

。某个人

j

喝光了

i

瓶中的酒

: Y = 0; Y[j] = X[j] + X, i

∈

[1,3], j

∈

[4,7]

当然状态

Y

必须满足（

2

）中的约束条件；

100

（

4

）初始状态

a,b

两个瓶中装满酒，

c

空：

X0[1]=C[1], X0[2]=C[2], X0[3]=C[3], X0[4]=X0[5]=X0[6]=X0[7]=0

；

中为

（

5

）目标状态

所有的瓶中的酒为空，每个人都喝饱了

酒：

Xn[1]=Xn[2]=Xn[3]=0 , Xn[4]=C[4]

，

Xn[5]=C[5]

，

Xn[6]=C[6]

，

Xn[7]=C[7];

下面给出一个通用的回溯法伪代码：

void DFS_TRY( s )

{

if (

状态

s

是目标状态

) {

打印结果；

退出；

//

如果要求输出所有的解，这里退出函数，如果只要求输出一组解，这里退出

整个程序

}

for

从状态

s

根据产生规则产生的每个状态

t

if (t

不在堆栈中

) {

状态

t

压入堆栈；

DFS_TRY(t);

状态

t

弹出堆栈；

}

}

主程序为：

初始状态

s0

压入堆栈；

DFS_TRY(s0);

然而，对于这个问题，如果单纯地用上面的回溯法解决效率非常的低，几乎无法忍受。所以

要改进一下。我们注意到每个状态是一个

7

元组，而且根据约束条件，所有的合法的状态的

个数是

8*8*3*4*4*4*4 =49152

个，完全可以将所有的状态记录下来，即使穷举所有的状态

也是可以忍受的。所以在上面的

DFS_TRY

中，我们不是在堆栈中寻找已经搜索过的状态，

而是在一个状态表中找已经搜索过的状态，如果某个状态在状态表中的标志表明该状态已经

搜索过了，就没有必要再搜索一遍。比如，单纯的回溯法搜索出来的搜索树如下所示：

a

/

/

b c

/

101

/

d

/

/

从

a

出发，搜索

a - b - d - ...

然后回溯到

a,

又搜索到

a - c - d - ...,

因为

d

在搜索的路径上并没

有重复，所以在堆栈中是发现不了

d

节点被重复搜索的，这样就重复搜索了

d

和它的子树；

如果用一个表格纪录每个节点是否被搜索过了，这样搜索

a - b - d - ...

回溯到

a,

又搜索

到

a - c - d

，这时候查表发现

d

已经搜索过了，就可以不用再搜索

d

和它的子树了。

这种用一个表格来记录状态的搜索策略叫做

“

备忘录法

”

，是动态规划的一种变形，关于动

态规划和备忘录法，请参见

:

/algorithm/technique/dynamic_programming/

备忘录法的伪代码：

bool Memoire_TRY( s )

{

if (

状态

s

是目标状态

) {

记录状态

s

；

return true; //

这里假设只要求输出一组解

}

for

从状态

s

根据产生规则产生的每个状态

t

if (

状态

t

没有被搜索过

) { //

注意这里的改变

标记状态

t

被访问过；

if (DFS_TRY(t)) {

记录状态

s

；

return true;

}

}

return fal;

}

主程序为：

初始化设置状态表中的所有状态未被访问过

初始状态设为

s0

；

if (Memoire_TRY(s0))

打印记录下来的解

;

这样就不需要自己设置堆栈了，但是需要维护一个状态访问表。

下面是按照这种思路写的程序，注意，求出来的不是最优解，但是很容易修改该程序求出最

102

优解。

#include

#include

const int CUP_COUNT = 3; //

酒杯的数目

const int STATE_COUNT = 7; //

状态变量的维数

typedef int State[STATE_COUNT]; //

记录状态的类型

const State CONSTR = {8, 8, 3, 4, 4, 4, 4}; //

约束条件

const State START = {8, 8, 0, 0, 0, 0, 0}; //

初始状态

const State GOAL = {0, 0, 0, 4, 4, 4, 4}; //

目标状态

const int MAX_STATE_COUNT = 10*10*10*10*10*10*10; //

态空间的状态数目

const MAX_STEP = 50; //

假设最多需要

50

步就可以找到目标

const State key = {3, 5, 3, 3, 2, 0, 0};

bool visited[MAX_STATE_COUNT]; //

用来标记访问过的状态

State result[MAX_STEP]; //

记录结果；

int step_count = 0; //

达到目标所用的步数

//

计算状态

s

在状态表中的位置

int pos(const State &s)

{

int p = 0;

for (int i=0; i

p = p*10 + s;

}

return p;

}

//

判断状态

a,b

是否相等

bool equal(const State &a, const State &b) {

for (int i=0; i

if (a!=b) return fal;

return true;

}

void printState(const State &s) {

for (int i=0; i

cout << s << " ";

cout << endl;

}

103

//

备忘录法搜索

bool Memoire_TRY(const State &s, int step)

{

if (memcmp(s,GOAL,sizeof(s))==0) { //

如果是目标状态

step_count = step;

memcpy(result[step-1],s, sizeof(s)); //

记录状态

s

return true;

}

int i, j;

//

第一种规则，第

i

个人喝光杯子

j

中的酒

for (i=CUP_COUNT; i

if (s < CONSTR) //

如果第

i

个人还可以喝

for (j=0; j

if (s[j]>0 && s + s[j] <= CONSTR) { //

如果第

i

个人可以喝光第

j

杯中的酒

State t;

memcpy(t, s, sizeof(s));

t += t[j]; //

第

i

个人喝光第

j

杯的酒

t[j] = 0;

int tmp = pos(t);

if (!visited[pos(t)]) { //

如果状态

t

没有访问过

visited[pos(t)] =true; //

标记状态

t

访问过了

if (Memoire_TRY(t, step+1)) { //

从状态

t

出发搜索

memcpy(result[step-1],s, sizeof(s)); //

记录状态

s

return true;

} // end of if (Memoire_TRY(t, step+1))

} // end of if (!visited[pos(t)])

} // end of if (s + s[j] <= CONSTR)

//

第二种规则，将杯子

i

中的酒倒入到杯子

j

中去

for (i=0; i

for (j=0; j

if (i != j) {

int k = (CONSTR[j] - s[j] < s ? CONSTR[j] - s[j] : s ); //

计算出可以从

i

中倒入

j

中的酒的数

量

if (k > 0) { //

如果可以倒

State t; //

生成新的状态

t

memcpy(t, s, sizeof(s));

t -= k;

t[j] += k;

int tmp = pos(t);

if (!visited[pos(t)]) { //

如果状态

t

没有访问过

104

visited[pos(t)] =true; //

标记状态

t

访问过了

if (Memoire_TRY(t, step+1)) { //

从状态

t

出发搜索

memcpy(result[step-1],s, sizeof(s)); //

记录状态

s

return true;

} // end of if (Memoire_TRY(t, step+1))

} // end of if (!visited[pos(t)])

} // end of if (k > 0)

} // end of if (i != j)

return fal;

} // end of Memoire_TRY

void main()

{

memt(visited, fal, sizeof(visited));

if (Memoire_TRY(START,1)) {

cout << "find a solution: " << endl;

for (int i=0; i

for (int j=0; j

cout << result[j] << " ";

cout << endl;

}

} el

cout << "no solution." << endl;

}

鹰蛋

105