编者按：最近被算法虐的不要不要的，还是那句话拒绝算法就是拒绝成为一流，而想要有好的算法能力在我看来一定是勤加练习加长时间的积累与训练，现在我就十分后悔没有在前两年扎实我的算法能力，如今到了升级打怪的时候才发现内力不够。。。从今以后重新做人。
第七届省赛Ｂ组第一题 煤球数目 煤球问题
有一堆煤球，堆成三角棱锥形。 具体： 第一层放1个， 第二层3个（排列成三角形）， 第三层6个（排列成三角形）， 第四层10个（排列成三角形）， …. 如果一共有100层，共有多少个煤球？
请填表示煤球总数目的数字
递归
递归方法基本步骤
案例提出：
- （1） 根据实际构建递归关系
- （2）确定递归边界
- （3）编写递归函数
- （4）设计主函数调用递归函数
排队购票
一场球赛开始前，售票工作正在紧张进行中。 每张球票为50元，有m+n个人排队等待狗牌，其中有m个人手持50元的钞票，另外n个人手持100元的钞票。
求出m+n个人排队购票，使售票处不至于出现找不开钱的局面的不同排队种数。 （约定：开始售票时售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）
递归设计要点
令f(m,n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的排队总数。 分以下3种情况来讨论。
- (1) n=0 n=0意味着排队购票的所有人手中拿的 都是50元的钱币，注意到拿同样面值钞 票的人对换位置为同一种排队，那么这 m个人的排队总数为1，即f(m,0)=1。
- (2）m<n 当m<n时, 即购票的人中持50元的人数 小于持100元的钞票，即使把m张50元 的钞票都找出去，仍会出现找不开钱的 局面，这时排队总数为0，即f(m,n)=0。
- (3）其它情况 ① 第m+n个人手持100元的钞票，则在他之前的 m+n-1个人中有m个人手持50元的钞票，有n-1个人 手持100元的钞票，此种情况共有f(m,n-1)。 ② 第m+n个人手持50元的钞票，则在他之前的 m+n-1个人中有m-1个人手持50元的钞票，有n个人 手持100元的钞票，此种情况共有f(m-1,n)。 由加法原理得到f(m,n)的递归关系： f(m,n)=f(m,n-1)+f(m-1,n) 初始条件： 当m<n时，f(m,n)=0 当n=0时，f(m,n)=1
皇后问题的回溯举例
回溯剖析与描述
（1） 回溯求解的问题P对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)|xi∈si,i=1,2,…,n}，给定关于 n元组中的约束集D，要求E中满足D的全部约束条件的所有n元组。 对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的 一个约束，就可以肯定，以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P 的解，因而就不必去搜索它们，省略了对部分元素(xj+1,…,xn)的操作与测试。
（2） 回溯描述对于一般含参量m,n的搜索问题,输入正整数n,m,(n≥m) i=1;a[i]=<元素初值>;
while (1)
{for(g=1,k=i-1;k>=1;k--)
if( <约束条件1> ) g=0; // 检测约束条件,不满足则返回
if(g && <约束条件2>) printf(a[1：m]); // 输出解
if(i<n && g) {i++;a[i]=<取值点>;continue;}
while(a[i]=<回溯点> && i>1) i--; // 向前回溯
if(a[i]==n && i==1) break; // 退出循环，结束
else a[i]=a[i]+1;
}
i=1;a[i]=1;
while (1)
{ g=1;for(k=i-1;k>=1;k--)
if(a[i]=a[k] || abs(a[i]-a[k])=i-k) g=0; // 检测约束条件,不满足则返回
if(g && i==4) printf(a[1：4]); // 输出一个解
if(i<4 && g) {i++;a[i]=1;continue;}
while(a[i]==4 && i>1) i--; // 向前回溯
if(a[i]==4 && i==1) break; //退出循环结束探索
else a[i]=a[i]+1;
}