当前位置：文档库 › 程序员面试题精选100题

程序员面试题精选100题

…

程序员面试题精选100题

前言

随着高校的持续扩张，每年应届毕业生的数目都在不断增长，伴随而来的是应届毕业生的就业压力也越来越大。

在这样的背景下，就业变成一个买方市场的趋势越来越明显。为了找到一个称心的工作，绝大多数应届毕业生都必须反复经历简历筛选、电话面试、笔试、面试等环节。在这些环节中，面试无疑起到最为重要的作用，因为通过面试公司能够最直观的了解学生的能力。

为了有效地准备面试，面经这个新兴概念应运而生。笔者在当初找工作阶段也从面经中获益匪浅并最终找到满意的工作。为了方便后来者，笔者花费大量时间收集并整理散落在茫茫网络中的面经。不同行业的面经全然不同，笔者从自身专业出发，着重关注程序员面试的面经，并从精选出若干具有代表性的技术类的面试题展开讨论，希望能给读者带来一些启发。

由于笔者水平有限，给各面试题提供的思路和代码难免会有错误，还请读者批评指正。另外，热忱欢迎读者能够提供更多、更好的面试题，本人将感激不尽。

(01)把二元查找树转变成排序的双向链表

)

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

比如将二元查找树

/ \

6 14

/ \ / \

8 12 16

转换成双向链表

4=6=8=10=12=14=16。

分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不例外。下面我们用两种不同的递归思路来分析。

思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。

思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

参考代码：

首先我们定义二元查找树结点的数据结构如下：

struct BSTreeNode print the path

bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);

if(currentSum == expectedSum && isLeaf)

{

std::vector::iterator iter =();

for(; iter != (); ++ iter)

std::cout<<*iter<<'\t';

std::cout<

}

，则输出“student. a am I”。

。

分析：由于编写字符串相关代码能够反映程序员的编程能力和编程习惯，与字符串相关的问题一直是程序员笔试、面试题的热门题目。本题也曾多次受到包括微软在内的大量公司的青睐。

由于本题需要翻转句子，我们先颠倒句子中的所有字符。这时，不但翻转了句子中单词的顺序，而且单词内字符也被翻转了。我们再颠倒每个单词内的字符。由于单词内的字符被翻转两次，因此顺序仍然和输入时的顺序保持一致。

还是以上面的输入为例子。翻转“I am a student.”中所有字符得到“.tneduts a ma I”，再翻转每个单词中字符的顺序得到“students. a am I”，正是符合要求的输出。

参考代码：

.+n

题目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（AB:C）。

分析：这道题没有多少实际意义，因为在软件开发中不会有这么变态的限制。但这道题却能有效地考查发散思维能力，而发散思维能力能反映出对编程相关技术理解的深刻程度。

通常求1+2+…+n除了用公式n(n+1)/2之外，无外乎循环和递归两种思路。由于已经明确限制for和while的使用，循环已经不能再用了。同样，递归函数也需要用if语句或者条件判断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。、

我们仍然围绕循环做文章。循环只是让相同的代码执行n遍而已，我们完全可以不用for 和while达到这个效果。比如定义一个类，我们new一含有n个这种类型元素的数组，那么

该类的构造函数将确定会被调用n次。我们可以将需要执行的代码放到构造函数里。如下代码正是基于这个思路：

class Temp

{

public:

Temp() { ++ N; Sum += N; }

static void Reset() { N = 0; Sum = 0; }

static int GetSum() { return Sum; }

private:

static int N;

static int Sum;

};

int Temp::N = 0;

int Temp::Sum = 0;

int solution1_Sum(int n)

{

Temp::Reset();

Temp *a = new Temp[n];

delete []a;

a = 0;

return Temp::GetSum();

}

我们同样也可以围绕递归做文章。既然不能判断是不是应该终止递归，我们不妨定义两个函数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在两个函数里二选一。从二选一我们很自然的想到布尔变量，比如ture（1）的时候调用第一个函数，false（0）的时候调用第二个函数。那现在的问题是如和把数值变量n转换成布尔值。如果对n连续做两次反运算，即!!n，那么非零的n转换为true，0转换为false。有了上述分析，我们再来看下面的代码：

class A;

A* Array[2];

class A

{

public:

virtual int Sum (int n) { return 0; }

};

class B: public A

{

public:

virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }

};

int solution2_Sum(int n)

{

A a;

B b;

Array[0] = &a;

Array[1] = &b;

int value = Array[1]->Sum(n);

return value;

}

这种方法是用虚函数来实现函数的选择。当n不为零时，执行函数B::Sum；当n为0时，执行A::Sum。我们也可以直接用函数指针数组，这样可能还更直接一些：

typedef int (*fun)(int);

int solution3_f1(int i)

{

return 0;

}

int solution3_f2(int i)

{

fun f[2]={solution3_f1, solution3_f2};

return i+f[!!i](i-1);

}

另外我们还可以让编译器帮我们来完成类似于递归的运算，比如如下代码：

template struct solution4_Sum

{

enum Value { N = solution4_Sum::N + n};

};

template <> struct solution4_Sum<1>

{

enum Value { N = 1};

};

solution4_Sum<100>::N就是1+2+...+100的结果。当编译器看到solution4_Sum<100>时，就是为模板类solution4_Sum以参数100生成该类型的代码。但以100为参数的类型需要得到以99为参数的类型，因为solution4_Sum<100>::N=solution4_Sum<99>::N+100。这个过程会递归一直到参数为1的类型，由于该类型已经显式定义，编译器无需生成，递归编译到此

结束。由于这个过程是在编译过程中完成的，因此要求输入n必须是在编译期间就能确定，不能动态输入。这是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的，也就是要求n不能太大。

大家还有更多、更巧妙的思路吗欢迎讨论^_^

(09)－查找链表中倒数第k个结点

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的

尾指针。链表结点定义如下：

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

分析：为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是输入的是单向链表，只有从前往后的指针而没有从后往前的指针。因此我们需要打开我们的思路。

既然不能从尾结点开始遍历这个链表，我们还是把思路回到头结点上来。假设整个链表有n 个结点，那么倒数第k个结点是从头结点开始的第n-k-1个结点（从0开始计数）。如果我们能够得到链表中结点的个数n，那我们只要从头结点开始往后走n-k-1步就可以了。如何得到结点数n这个不难，只需要从头开始遍历链表，每经过一个结点，计数器加一就行了。(

这种思路的时间复杂度是O(n)，但需要遍历链表两次。第一次得到链表中结点个数n，第二次得到从头结点开始的第n-k-1个结点即倒数第k个结点。

如果链表的结点数不多，这是一种很好的方法。但如果输入的链表的结点个数很多，有可能不能一次性把整个链表都从硬盘读入物理内存，那么遍历两遍意味着一个结点需要两次从硬盘读入到物理内存。我们知道把数据从硬盘读入到内存是非常耗时间的操作。我们能不能把链表遍历的次数减少到1如果可以，将能有效地提高代码执行的时间效率。

如果我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动；在第k-1步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

这种思路只需要遍历链表一次。对于很长的链表，只需要把每个结点从硬盘导入到内存一次。因此这一方法的时间效率前面的方法要高。

思路一的参考代码：

. n - 1) form a circle. Remove the mth from

Find the last number remaining

. n - 1)

list integers;

for(i = 0; i < n; ++ i)

(i);

list::iterator curinteger = ();

while() > 1)

{

Note that std::list is not a circle

. n - 1) form a circle. Remove the mth from

Find the last number remaining

m-1n-1k-1m-1n-1k-1m-1n-1

2. 如果x m-1≠y n-1，那么当z k-1≠x m-1时Z是X m-1和Y的LCS；

3. 如果x m-1≠y n-1，那么当z k-1≠y n-1时Z是Y n-1和X的LCS；

下面简单证明一下这些性质：

—

1. 如果z k-1≠x m-1，那么我们可以把x m-1（y n-1）加到Z中得到Z’，这样就得到X和Y的一个长度为k+1的公共子串Z’。这就与长度为k的Z是X和Y的LCS相矛盾了。因此一定有z k-1=x m-1=y n-1。

既然z k-1=x m-1=y n-1，那如果我们删除z k-1（x m-1、y n-1）得到的Z k-1，X m-1和Y n-1，显然Z k-1是X m-1和Y n-1的一个公共子串，现在我们证明Z k-1是X m-1和Y n-1的LCS。用反证法不难证明。假设有X m-1和Y n-1有一个长度超过k-1的公共子串W，那么我们把加到W中得到W’，那W’就是X 和Y的公共子串，并且长度超过k，这就和已知条件相矛盾了。

2. 还是用反证法证明。假设Z不是X m-1和Y的LCS，则存在一个长度超过k的W是X m-1和Y的LCS，那W肯定也X和Y的公共子串，而已知条件中X和Y的公共子串的最大长度为k。矛盾。

3. 证明同2。

有了上面的性质，我们可以得出如下的思路：求两字符串X m={x0, x1,…x m-1}和Y n={y0,y1,…,y n-1}的LCS，如果x m-1=y n-1，那么只需求得X m-1和Y n-1的LCS，并在其后添加x m-1（y n-1）即可；如果x m-1≠y n-1，我们分别求得X m-1和Y的LCS和Y n-1和X的LCS，并且这两个LCS中较长的一个为X和Y的LCS。

如果我们记字符串X i和Y j的LCS的长度为c[i,j]，我们可以递归地求c[i,j]：

/ 0 if i<0 or j<0

c[i,j]= c[i-1,j-1]+1 if i,j>=0 and x i=x j

\ max(c[i,j-1],c[i-1,j] if i,j>=0 and x i≠x j

上面的公式用递归函数不难求得。但从前面求Fibonacci第n项(本面试题系列第16题）的分析中我们知道直接递归会有很多重复计算，我们用从底向上循环求解的思路效率更高。…

为了能够采用循环求解的思路，我们用一个矩阵（参考代码中的LCS_length）保存下来当前已经计算好了的c[i,j]，当后面的计算需要这些数据时就可以直接从矩阵读取。另外，求取c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到，相当于在矩阵LCS_length中是从c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j]，因此在矩阵中有三种不同的移动方向：向左、向上和向左上方，其中只有向左上方移动时才表明找到LCS中的一个字符。于是我们需要用另外一个矩阵（参考代码中的LCS_direction）保存移动的方向。

参考代码如下：

#include""

It's

if(firstDigit > 1)

numFirstDigit = PowerBase10(length - 1);

It's

else if(firstDigit == 1)

numFirstDigit = atoi(strN + 1) + 1;

return numFirstDigit + numOtherDigits + numRecursive;

}

尾到头输出一个字符串；

2.定义一个函数求字符串的长度，要求该函数体内不能声明任何变量。

(32)-不能被继承的类

题目：用C++设计一个不能被继承的类。

分析：这是Adobe公司2007年校园招聘的最新笔试题。这道题除了考察应聘者的C++基本功底外，还能考察反应能力，是一道很好的题目。

在Java中定义了关键字final，被final修饰的类不能被继承。但在C++中没有final这个关键字，要实现这个要求还是需要花费一些精力。

首先想到的是在C++ 中，子类的构造函数会自动调用父类的构造函数。同样，子类的析构函数也会自动调用父类的析构函数。要想一个类不能被继承，我们只要把它的构造函数和析构函数都定义为私有函数。那么当一个类试图从它那继承的时候，必然会由于试图调用构造函数、析构函数而导致编译错误。

可是这个类的构造函数和析构函数都是私有函数了，我们怎样才能得到该类的实例呢这难不倒我们，我们可以通过定义静态来创建和释放类的实例。基于这个思路，我们可以写出如下的代码：

If there is no common

和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。

分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，因为写程序操作字符串能很好的反映我们的编程基本功。

要编程完成这道题要求的功能可能并不难。毕竟，这道题的基本思路就是在第一个字符串中

拿到一个字符，在第二个字符串中查找一下，看它是不是在第二个字符串中。如果在的话，就从第一个字符串中删除。但如何能够把效率优化到让人满意的程度，却也不是一件容易的事情。也就是说，如何在第一个字符串中删除一个字符，以及如何在第二字符串中查找一个字符，都是需要一些小技巧的。

首先我们考虑如何在字符串中删除一个字符。由于字符串的内存分配方式是连续分配的。我们从字符串当中删除一个字符，需要把后面所有的字符往前移动一个字节的位置。但如果每次删除都需要移动字符串后面的字符的话，对于一个长度为n 的字符串而言，删除一个字符的时间复杂度为O(n) 。而对于本题而言，有可能要删除的字符的个数是n ，因此该方法就删除而言的时间复杂度为O(n2) 。

事实上，我们并不需要在每次删除一个字符的时候都去移动后面所有的字符。我们可以设想，当一个字符需要被删除的时候，我们把它所占的位置让它后面的字符来填补，也就相当于这个字符被删除了。在具体实现中，我们可以定义两个指针(pFast 和pSlow) ，初始的时候都指向第一字符的起始位置。当pFast 指向的字符是需要删除的字符，则pFast 直接跳过，指向下一个字符。如果pFast 指向的字符是不需要删除的字符，那么把pFast 指向的字符赋值给pSlow 指向的字符，并且pFast 和pStart 同时向后移动指向下一个字符。这样，前面被pFast 跳过的字符相当于被删除了。用这种方法，整个删除在O(n) 时间内就可以完成。

接下来我们考虑如何在一个字符串中查找一个字符。当然，最简单的办法就是从头到尾扫描整个字符串。显然，这种方法需要一个循环，对于一个长度为n 的字符串，时间复杂度是O(n) 。

由于字符的总数是有限的。对于八位的char 型字符而言，总共只有28=256 个字符。我们可以新建一个大小为256 的数组，把所有元素都初始化为0 。然后对于字符串中每一个字符，把它的ASCII 码映射成索引，把数组中该索引对应的元素设为１。这个时候，要查找一个字符就变得很快了：根据这个字符的ASCII 码，在数组中对应的下标找到该元素，如果为0 ，表示字符串中没有该字符，否则字符串中包含该字符。此时，查找一个字符的时间复杂度是O(1) 。其实，这个数组就是一个hash 表。这种思路的详细说明，详见本面试题系列的第13 题。

基于上述分析，我们可以写出如下代码：

const unsigned int nTableSize = 256;

int hashTable[nTableSize];

memset(hashTable, 0, sizeof(hashTable));

const char* pTemp = pStrDelete;

}

while ('\0' != *pTemp)

{

hashTable[*pTemp] = 1;

++ pTemp;

}

char* pSlow = pStrSource;

char* pFast = pStrSource;

while ('\0' != *pFast)

{

Maind:\n", ++iCount);

for(int i=0; i < ROWS; i++)

for(int j=0; j < COLS; j++)

printf("%d%c", Grid[i][j], (j+1) % COLS ' ' : '\n');

iFound = 1; LenALenALenA456789”2005年5月29日2005年11月15日123”-0123”45”123.45”2005年11月23日56”4g,n}，给定关于n元组中的分量的一个约束集D，要求E中满足D的全部约束的所有n元组。其中Si 是分量xi的定义域且|Si|有限，i=1,2,...n。我们称E中满足D的全部约束条件的任一n 元组为问题P的一个解。

对于n元组(x1,x2,……，xn)中分量的约束，一般分为两类，一类是显约束，它给出对于n 元组中分量的显式限制，比如当i≠j时xi≠xj；另一类是隐约束，它给出对于n元组中分量的隐式限制，比如：f(x1,x2,……，xn)≠0，其中f是隐函数。不过隐式显式并不绝对，两者可以相互转换。

解问题P的最朴素的方法是穷举法，即对E中的所有n元组，逐一地检测其是否满足D的全部约束。全部满足，才是问题p的解;只要有一个不满足，就不是问题P的解。显然，如果记m(i)=|S(i+1)|,i=0,1,...n-1，那么，穷举法需要对m=m(0)*m(1)*...*m(n-1)个n元组一个不漏地加以检测。可想而知，其计算量是非常之大的。

我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组(x1,x2,……，xi)满足D中仅涉及到x1,x2,……，xi的所有约束意味着j(j

这个发现告诉我们，对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1,x2,……,xj)违反D中仅涉及x1,x2,……,xj的一个约束，就可以肯定，以(x1,x2,……,xj)为前缀的任何n元组(x1,x2,……,xj,……,xn)都不会是问题的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比穷举法效率高得多的算法。

回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树。它可这样构造：设Si中的元素可排成x(i,1),x(i,2),……,x(i,m(i-1)),i=1,2,……,n。从根开始，让T的第i层的每一个结点都有m(i)个儿子。这m(i)个儿子到它们的共同父亲的边，按从左到右的次序分别带权x(i+1,1),x(i+1,2),……,x(i+1,m(i)),i=0,1,2,……,n-1。照这种构造方式，E中的一个n元组(x1,x2,……，xn)对应于T中的一个叶结点，T的根到这个叶结点的路上依次的n条边分别以x1,x2,……，xn为其权，反之亦然。另外，对于任意的0≤i≤n-1，E中n元组(x1,x2,……，xn)的一个前缀i元组(x1,x2,……，xi)对应于T中的一个非叶结点，T的根到这个非叶结点的路上依次的i条边分别以了x1,x2,……，xi为其权，反之亦然。特别，E中的任意一个n元组的空前缀()，对应于T的根。

因而，在E中寻找问题P的一个解等价于在T中搜索一个叶结点，要求从T的根到该叶结点的路上依次的n条边相应带的n个权x1,x2,……，xn满足约束集D的全部约束。在T中搜索所要求的叶结点，很自然的一种方式是从根出发逐步深入，让路逐步延伸，即依次搜索满足约柬条件的前缀1元组(xl)，前缀2元组(xl,x2)，前缀i元组(x1,x2,……，xi)，……，直到i=n为止。注意，在这里，我们把(x1,x2,……，xi)应该满足的D中仅涉及x1,x2,……，xi的所有约束当做判断(x1,x2,……，xi)是问题p的解的必要条件，只有当这个必要条件加上条件i=n才是充要条件。为了区别，我们称使积累的判别条件成为充要条件的那个条件(如条件i=n)为终结条件。

在回溯法中，上面引入的树T被称为问题P的状态空间树;树T上的任意一个结点被称为问题p的状态结点;树T上的任意一个叶结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约柬的任意一个叶结点被称为问题P的一个回答状态结点，简称为回答结点或回答状态，它对应于问题P的一个解。

例如8皇后问题，就是要确定一个8元组（x1,x2,..,x8)，xi表示第i行的皇后所在的列，这样的问题很容易应用上面的搜索树模型；然而，有些问题的解无法表示成一个n元组，因为事先无法确定这个n是多少，比如这个喝酒问题，问题的解就是一系列的倒酒喝酒策略，但是事先无法确定究竟需要进行多少步；还有著名的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）中的约束条件；

（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是目标状态) {

打印结果；

退出；. 然后回溯到a, 又搜索到 a - c - d - ..., 因为d在搜索的路径上并没有重复，所以在堆栈中是发现不了d节点被重复搜索的，这样就重复搜索了d和它的子树；如果用一个表格纪录每个节点是否被搜索过了，这样搜索 a - b - d - ...回溯到a, 又搜索到 a - c - d ，这时候查表发现d已经搜索过了，就可以不用再搜索d和它的子树了。

这种用一个表格来记录状态的搜索策略叫做“备忘录法”，是动态规划的一种变形，关于动态规划和备忘录法，请参见:

备忘录法的伪代码：

bool Memoire_TRY( s )

{

if (状态s是目标状态) {

记录状态s；

return true; << endl;

}

鹰蛋