程序員面試題精選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