例子
1. 设计一个算法求解4排列问题，即输出4个数 字 1 2 3 4 所有的排列； 2
回溯法



回溯法也称为试探法，该方法首先暂时放弃关于规模的大小的 限制，并将问题的候选解按某种顺序逐一枚举和检验，当发现 当前候选解不可能是解时，就选择下一个候选解，倘若当前的 候选解除了还不满足问题的规模的要求外，还满足其他所有要 求，则继续扩大当前候选解的规模，并继续试探。如果当前候 选解满足包括问题规模在内的所有要求的时候，该候选解就是 问题的一个解。 在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为 回溯。 扩大当前候选解的规模称为试探。 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜 索，以达到目标。但当探索到某一步时，发现原先选择并不优 或达不到目标，就退回一步重新选择，这种走不通就退回再走 的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯 点”。


自动门刚安装好的时候，我们可以认为它是关上的，所以关闭状态是自动门 的初始状态。 在理想情况下，自动门会一直运行，所以它没有接受状态，接受状态集F是空 集。
例子

密码锁：以四位密码校验作为状态机的例子，连续输入 2479就可以通过密码测试



统计一篇英文文章里的单词个数。 有多种方法可以解这道题，这里我们选择用有穷状态机来解，做法如下： 先把这篇英文文章读入到一个缓冲区里，让一个指针从缓冲区的头部一直移到缓冲区的尾部，指针 会处于两种状态：“单词内”或“单词外”，加上后面提到的初始状态和接受状态，就是有穷状态 机的状态集。缓冲区中的字符集合就是有穷状态机的字母表。 如果当前状态为“单词内”，移到指针时，指针指向的字符是非单词字符(如标点和空格)，那状态 会从“单词内”转换到“单词外”。如果当前状态为“单 词外”， 移到指针时，指针指向的字符 是单词字符(如字母)，那状态会从“单词外”转换到“单词内是初始状态。 指针指向缓冲区的尾部时是接受状态。 每次当状态从“单词内”转换到“单词外”时，单词计数增加一。 这个有穷状态机的图形表示如下：
Hash table 简介
哈希查找 基本思想：在记录的存储地址和它的关键字 之间建立一个确定的对应关系；这样，不经 过比较，一次存取就能得到所查元素的查找 方法
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被 更快地定位。 实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有： · 计算哈希函数所需时间 · 关键字的长度 · 哈希表的大小 · 关键字的分布情况 · 记录的查找频率 1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。 即H(key)=key或H(key) = a· + b，其中a和b为常数（这种散列函数叫做自身函数）。若其 key 中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。 2. 数 字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几 位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表 示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会 明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较 低的散列地址。 3. 平方取中法：取关键字平方后的中间几位作为散列地址。 4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分 的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移 位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分 割界来回折叠，然后对齐相加。 5. 随机数法：选择一随机函数，取关键字的随机值作 为散列地址，通常用于关键字长度不同的场合。 6. 除留余数法：取关键字被某个不大 于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可 以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取 素数或m，若p选的不好，容易产生同义词。


例子:斐波那契序列; 以兔子繁殖为例 用月份n作为参数,表示计算第几个月后兔子 的总数,i循环变量,迭代条件为:3<=I<=n 程序中迭代变量为fib fib1.fib2
由递归引出的分治
一、求解大规模问题的复杂性 二、化整为零、分而治之
分解 分治 合并
p1 n1
s0 s1
P n
p2 n2
例子

假定有n个物体和一个背包，物体i 有质量wi，价值为pi，而背包的载荷能力为M。若将物体i 的一部分xi（1<=i<=n,0<=xi<=1)装入背包中，则有价值pi*xi。在约束条件 （w1*x1+w2*x2+…………+wn*xn)<=M下使目标(p1*x1+p2*x2+……+pn*xn)达到极大，此处 0<=xi<=1,pi>0,1<=i<=n.这个问题称为背包问（Knapsack problem）。
Void trial(int I,int n) {


If(i>n) 输出当前布局； Else for(j=1;j<=n;++j){
在第i行第j列放置一个棋子； If(当前布局合法) trial(i+1,n); 移走第i行第j列的棋子；


}

}
贪心算法



所谓贪心算法是指，在对问题求解时，总是做 出在当前看来是最好的选择。也就是说，不从 整体最优上加以考虑，他所做出的仅是在某种 意义上的局部最优解。 贪心算法没有固定的算法框架，算法设计 的关键是贪心策略的选择。必须注意的是，贪 心算法不是对所有问题都能得到整体最优解， 选择的贪心策略必须具备无后效性，即某个状 态以后的过程不会影响以前的状态，只与当前 状态有关。 所以对所采用的贪心策略一定要仔细分析其 是否满足无后效性。
什么是迭代

迭代法是一种常用的算法设计方法,迭代是 一个不断用新值取代变量的旧值,或由旧值 递推出变量的新值的过程.





当一个问题的求解过程能够由一个初值使用一个 迭代表达式进行反复迭代的时候,便可以用效率极 高的重复程序描述 迭代也是用循环结构实现的. 只不过重复的操作是不断的从一个变量的旧值出 发计算它的新值. 其基本格式如下; 迭代变量赋予初值; 循环语句 { 计算迭代式; 新值取代旧值 }
关键字 集合 hash 存储地址 集合


哈希表——应用哈希函数，由记录的关键字确定记录在 表中的地址，并将记录放入此地址，这样构成的表叫 ~ 哈希查找——又叫散列查找，利用哈希函数进行查找的 过程叫~

7.4 哈希查找


基本思想：在记录的存储地址和它的关键字之间 建立一个确定的对应关系；这样，不经过比较， 一次存取就能得到所查元素的查找方法 定义

哈希函数——在记录的关键字与记录的存储地址之间建 立的一种对应关系叫~


哈希函数是一种映象，是从关键字空间到存储地址空间的一 种映象 哈希函数可写成：addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字
其他

动态规划 随机化思想 概率分析 摊销分析 竞争分析……还有很多愿意深入了解的同学 可以看一些算法方面的书籍。
但是需要注意，常用的算法了解即可，先把编程语言和高级编程等基 础学好，算法暂时不可深入钻研。

有穷状态机（有限状态机）



有穷状态机很简单，在生活中可以找出很多这样的 例子。但是教科书里讲得太复杂了，一会儿证明确 定性有穷状态机和非确定性有穷状态机的等价性， 一会儿 证明正则表达式的 这些理论的证明于编程没有太大用处，不过状态机 本身却是文本处理利器，由于程序员在很多场合下 都是在与文本数据 打交道，所以状态机是程序员必 备的工具之一。 含义。但 是大部分人 第一次看到它时，反复的读上几遍，仍 然不知道它在说什么。幸好通过一些实例，我们可 以很容易明白有穷状态机的原理。



八皇后问题，是一个古老而著名的问题， 是回溯算法的典型例题。该问题是十九世 纪著名的数学家高斯1850年提出：在8X8 格的国际象棋上摆放八个皇后，使其不能 互相攻击，即任意两个皇后都不能处于同 一行、同一列或同一斜线上，问有多少种 摆法。 可以简化为四皇后问题
伪代码的实现

《数据结构》一书
递归与迭代的区别
关于递归的回顾



一般定义 程序调用自身的编程思想称为递归（ recursion）。 一个过程或函数在其定义或说明中有直接或间接调用自 身的一种方法，它通常把一个大型复杂的问题层层转化 为一个与原问题相似的规模较小的问题来求解，递归策 略只需少量的程序就可描述出解题过程所需要的多次重 复计算，大大地减少了程序的代码量。递归的能力在于 用有限的语句来定义对象的无限集合。一般来说，递归 需要有边界条件、递归前进段和递归返回段。当边界条 件不满足时，递归前进；当边界条件满足时，递归返回。 注意： (1) 递归就是在过程或函数里调用自身； (2) 在使用递归策略时，必须有一个明确的递归结束条 件，称为递归出口。
S
pk nk
sk
递归与分治紧密相连
第二个例子
简单介绍算法
穷举法





穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种 简单而直接地解决问题的方法。其基本思想是逐一列举问题所 涉及的所有情形，并根据问题提出的条件检验哪些是问题的解， 哪些应予排除。 通常程序设计入门都是从穷举设计开始的。今天，计算机的运 算速度非常快，应用穷举设计程序可快捷地解决一般数量的许 多实际应用问题。 穷举法的特点是算法设计比较简单，解的可能为有限种，一一 列举问题所涉及的所有情形。 穷举法常用于解决“是否存在”或“有多少种可能”等问题。 其中许多实际应用问题靠人工推算求解是不可想象的，而应用 计算机来求解，充分发挥计算机运算速度快、擅长重复操作的 特点，穷举判断，快速简便。 应用穷举时应注意对问题所涉及的有限种情形须一一列举，既 不能重复，又不能遗漏。重复列举直接引发增解，影响解的准 确性；而列举的遗漏可能导致问题解的遗漏。