双十一节刚过，妈的就开始培训了。

今天晚上全程直播培训过程。

先写一道Java最大公约数的题目热热身。

今晚的主题是递归回溯算法。

 开始讲话了，今天来的人非常的多。

画红线是我上一次参加的成绩。希望这一次能够取得更好的成绩。

能够在省赛拿到一等奖，就比公本的学生强了。

具体的工作：

体力活，4小时写10道题目。

 

学习分为两大阶段： 

1、基础阶段——打字，for循环等简单的基础的方法要做的熟练，基本的问题形成自己的编码的习惯。

2、算法——针对特定的问题，分析出特定的算法。《算法导论》作为最主要的参考书。

 

开始上课了：

回溯法。也是一种穷举法。更加聪明的穷举法， 有一个判断的条件来简化穷举，避免了穷举所有的元素。排除明显不合理的步骤——又称剪枝。

 

例题： 八皇后问题。

 

简化成四皇后问题。

直觉的解法，通过4重for循环。

另一种解决思路。

 在第一行放一个皇后，再在第二行中放一个皇后，看第三行和第四行是否有空间在放皇后，如果没有可能性的时候，就不再放第三行和第四行，改动第二个行的皇后的位置，在看第三行是否有空间放第三个皇后，如果没有，再移动第二行的皇后的位置。。。。。

 

排除明显不合理的步骤

 

回溯法概述

1、状态树——这个状态树不是事先有的，是在解题的过程中逐步生产的。

2、约束函数。不同的问题，产别主要表现在约束函数上

3、节点与解

　　（1）完全节点，完全的满足条件的节点。

　　（2）部分解，部分的满足条件，不知道其是否完全的满足条件，要深入一层继续判断。

　　（3）死节点，不满足条件的节点，没有必要继续。

 

 

 

 

递归问题:

将一个规模是n的问题降低为具体步骤的方法。

以下为四皇后的递归解法

 寻找递归的解决方法的约束函数本身就是一个难题，因此主要使用非递归的方法解决问题。

 外while循环控制规模，内while循环不断尝试处理的元素。check(a, k)是约束函数。

else if(check(a, k ))是部分解（应为没有判断条件n == k）.

k++是深入一层。

 

 

回溯法的应用：

 

 

 

 

 

 回溯代码框架

 

t[]数组用来表示下标

 

 

全排列：

 

 

题型：给出一个排序，求出下一个排序（用字典序列来求解）。

 

一副扑克牌随机抽出5张牌