发布时间 : 星期六 文章NOIP初赛复习 - 算法1更新完毕开始阅读
f[0]←1；f[1]←2； {递推边界}
for i：=2 to n do f[i]←f[i-1]+f[i-2]； fib:=f(n)；
2、 数据之间的关系(即数据结构)按递归定义 如树的遍历，图的搜索等。
3、 有些问题本身没有明显的递归结构，但使用递归求解比其它方法更简单 例如【例题三十】合并排序、【例题三十一】导线和开关，等。
对于2、3，可利用堆栈结构将其转换为非递归算法，但结构不如递归算法简洁清晰，可读性较差。限于篇幅，这里不作介绍。
下面，例举三个例题。前两个例题属于计数型，即计算具有某种特性的对象有多少；第三个例题属于枚举型，即把所有具备某种特性的对象完全枚举出来。对这三个试题，我们采用递归方法编写程序，其结构非常简洁而清晰。 【例题三十四】划分问题
设ｓ是一个具有n个元素的集合ｓ＝｛a1，a2，?，an ｝，现将ｓ集合划分成K个满足下列条件的子集合s1，s2，?，sk ： 1． si≠φ 2．si∩sj＝φ
3．s1∪s2∪s3∪?∪sn＝ｓ (1≤i，j≤k i≠j)
则称s1，s2，?，sn是ｓ的一个划分。它相当于把ｓ集合中的n个元素a1?an 放入k个无标号的盒子中，使得没有一个盒子为空。试确定n个元素a1?an 放入k个无标号盒的划分数s(n，k)。
算法分析
例如S＝｛1，2，3，4｝，k＝3。细心的读者稍加分析后，不难得出ｓ有6种不同的划分方案，即划分数为6。其方案为
｛1，2｝∪｛3｝∪｛4｝ ｛1，3｝∪｛2｝∪｛4｝ ｛1，4｝∪｛2｝∪｛3｝ ｛2，3｝∪｛1｝∪｛4｝ ｛2，4｝∪｛1｝∪｛3｝ ｛3，4｝∪｛1｝∪｛2｝
如果对于任意的ｓ集合和k值，就不能凭籍直觉和经验计算划分数和枚举划分方案了。必须总结出一个数学规律：
设n个元素a1 ?an 放入k个无标号盒的划分数为ｓ(n，k)。在配置过程中，有两种互不相容的情况：
1、设｛an｝是k个子集中的一个子集，于是把｛a1?an-1 ｝划分为k－1子集有s (n－1，
k－1)个划分数；
⒉、如果｛an｝不是k个子集中的一个，即an必与其它的元素构成一个子集。首先把
｛a1，?，an-1 ｝划分成k个子集，这共有ｓ(n－1，k)种划分方式。然后再把an加入到k个子集中的一个子集中去，这有k种加入方式。对于每一种加入方式，都使集合划分为k个子集，因此由乘法原理知，划分数共有k*ｓ(n－1，k)。
应用加法原理于上述两种情况，得出｛a1，?，an｝划分为k个子集的划分数：
ｓ(n，k)＝ｓ(n－1，k－1)+k*s(n－1，k) (n>1，k≥1)
下面，我们来确定s(n，k)的边界条件：
1、我们不可能把n个元素不放进任何一个集合中去，即ｓ(n，0)＝0；也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即k＞n时ｓ(n，k)＝0。 2、把n个元素放进一个集合或把n个元素放进n个集合，方式数显然是1。即
s(n，1)=1 s(n，n)=1
显然，通过上述分析可得出划分数ｓ(n，k)的递归关系式： s(n，k)＝s(n－1，k－1)+k*s(n－1，k) (n>k，k≥1)
s(n，k)＝0 (n s(n，k)＝1 (k=1)或(k＝n) 按照划分数ｓ(n，k)的递归定义，可以直接写出它的递归函数S(n，k) function s (n ，k：integer)of word； begin if(k=0)or(k>n)then s←0 else if (k=1)or (k=n) then s←1 else s←s(n－1，k－1)+k*s(n－1，k)； end；{s} 【例题三十五】计算交点数 在平面上有n条直线，且无三线共点。问这些直线能有多少种不同的交点数。 输入： n 输出： 以下若干行列出所有相交方案。其中一行为一个交点数。 算法分析 我们将n条直线排成一个序列。直线2与直线1最多有一个交点；直线3与直线1和直线2最多有2个交点，??，直线n与其它n-1条直线有n-1个交点。由此得出n条直线互不平行且无三线交于一点的最多交点数为1+2+?+（n-1）= n*(n?1)。设 2 g[i]???0?1交点i不存在;交点i存在; （1≤i≤ n*(n?1)） 2 我们来具体分析n=4的情况 ⑴ 四条直线全部平行，无交点，g[0]=1 ⑵ 其中三条直线平行，交点数为(n-1)*1+0=3，g[3]=1 ⑶ 其中二条直线平行。这两条直线与另外两条直线之间的交点数为(n-2)*2=4。而另外 两条直线本身即可能平行亦可能相交，因此交点数据分别为 (n-2)*2+0=4 g[4]=1 (n-2)*2+1=5 g[5]=1 ⑷ 四条直线互不平行。交点数为(n-1)*1+3条直线的相交情况 (n-1)*1+0=3 g[3]=1 (n-1)*1+2=5 g[5]=1 (n-1)*1+3=6 g[6]=1 即n=4时，有0个、3个、4个、5个、6个不同的交点数。 由此得出 m条直线的交点方案=(m-r)条平行线与r条直线交叉的交点数+r条直线本身的交点方案 =(m-r)*r+r条直线本身的交点数 （1≤r≤m） 显然，计算不同交点数的问题是递归的，可以描述成如下递归算法： procedure try (m，j) {值参m为直线数， j为交点数} begin if m>0 {若直线存在，则递归计算所有的交叉情况} then for r：=m downto 1do try(m-r，j+r*(m-r)) else g[j]←1； {否则确定m条直线存在j个交点} end；{try} 有了递归过程try(m，j)后，我们便可以通过下述方式计算和输出n条直线的交点方案； k?n(n?1)； {计算n条直线的最多2交点数} fillchar(g，sizeof (g)，0)； try(n，0)； 方案数total初始化为0； for i：=0 to k do if g[i]=1 then begin total←total+1；输出第total个方案为交点数i；end；{then} 上面两个例题属于计算类型，即计算具有某种特性的对象有多少。递归不仅可用于计数，而且还可用于枚举，即把所有具有各某种特性的对象完全枚举出来。关键是如何从输入参数与输出结果之间的对应关系中归纳出递归式和边界条件。 【例题三十六】移动棋子 n对棋子(n≥4)排成一行 〇〇???〇●●???● n个白棋 n个黑棋 (图5．3—6) 移动规则：每次左移或者右移相邻两个棋子(不能调换位置)至空位，每次移动必须跳过若干个棋子(不能平移)。经若干次跳动后形成黑白相同的一行棋子。 〇●〇●〇●???〇● 2n个棋子 （图5．3—7） 请输出一种跳动方案。 输入： n 输出： 移动方案 算法分析 首先，我们分析n=4时的移动方案： 〇 〇 〇 〇 ● ● ● ● ▁ ▁ （▁ ▁ 为工作场地） 第一步： 〇 〇 〇 ▁ ▁ ● ● ● 〇 ● c4c5?c9c10 第二步： 〇 〇 〇 ● 〇 ● ● ▁ ▁ ● c8c9?c4c5 第三步： 〇 ▁ ▁ ● 〇 ● ● 〇 〇 ● c2c3?c8c9 第四步： 〇 ● 〇 ● 〇 ● ▁ ▁ 〇 ● c7c8?c2c3 第五步： ▁ ▁ 〇 ● 〇 ● 〇 ● 〇 ● c1c2?c7c8 （图5．3—8） 由此看出，第i(1≤i≤5)步移动分两种情况 ⑴i为奇数时 i=5， c1c2移动至工作场地 i≠5， c5-ic6-i移动至工作场地 ⑵i为偶数时 c?i??i?9???10????2??2?c移动至工作场地 接下来分析n≥5时的移动方案。 n=5时 〇 〇 〇 〇 〇 ● ● ● ● ● ▁ ▁ 第一步： 〇 〇 〇 〇 ▁ ▁ ● ● ● ● 〇 ● c5c6?c11c12 第二步： 〇 〇 〇 〇 ● ● ● ● ▁ ▁ 〇 ● c9c10?c5c6 (图5．3—9) 已归结为n=4的情况，即第3步～第7步同n=4时的第1～5步 n=6时 〇 〇 〇 〇 〇 〇 ● ● ● ● ● ● ▁ ▁