（4） 若“4”第四个输出，与情况（1）相同，总数为f(3); 所以有：f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3); 若设0个数通过栈后的排列总数为：f(0)=1；
上式可变为：f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0); 再进一步推导，不难推出递推式：
f(n)=f(0)*f(n-1)+f(1)*f(n-2)+?+f(n-1)*f(0); 即f(n)=
0?i?n?1?f(i)*f(n?i?1) (n>=1)
初始值：f(0)=1;
有了以上递推式，就很容易用递推法写出程序。
var
a:array[0..18]of longint; n,i,j:integer; begin
readln(n);
fillchar(a,sizeof(a),0); a[0]:=1;
for i:=1 to n do
for j:=0 to i-1 do a[i]:=a[i]+a[j]*a[i-j-1]; writeln(a[n]); end.
递推算法最主要的优点是算法结构简单，程序易于实现，难点是从问题的分析中找出解决问题的递推关系式。对于以上两个例子，如果在比赛中找不出递推关系式，也可以用回溯法求解。
算法在信息学奥赛中的应用 (分治法)
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
分治法解题的一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 例1、 比赛安排(noip1996)
设有2^n(n<=6)个球队进行单循环比赛,计划在2^n-1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在2^n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为:
队 1 2 3 4
比赛 1-2 3-4 第一天
1-3 2-4 第二天 1-4 2-3 第三天
算法分析：此题很难直接给出结果，我们先将问题进行分解，设m=2^n，将规模减半，如果n=3(即m=8),8个球队的比赛，减半后变成4个球队的比赛（m=4），4个球队的比赛的安排方式还不是很明显，再减半到两个球队的比赛(m=2)，两个球队的比赛安排方式很简单，只要让两个球队直接进行一场比赛即可： 1 2 2 1 分析两个球队的比赛的情况不难发现，这是一个对称的方阵，我们把这个方阵分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1（即加m/2）得到，而右上与左下部分、左上与右下部分别相等。因此我们也可以把这个方阵看作是由M=1的方阵所成生的，同理可得M=4的方阵： 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 同理可由M=4方阵生成M=8的方阵： 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 6 7 8 1 2 3 4 5 8 7 2 1 4 3 8 5 6 3 4 1 2 7 6 5 4 3 2 1 这样就构成了整个比赛的安排表。
在算法设计中，用数组a记录2^n个球队的循环比赛表，整个循环比赛表从最初的1*1方阵按上述规则生成2*2的方阵，再生成4*4的方阵，??直到生成出整个循环比赛表为止。变量h表示当前方阵的大小,也就是要生成的下一个方阵的一半。 源程序： var
i,j,h,m,n:integer;
a:array[1..32,1..32]of integer; begin
readln(n);
m:=1;a[1,1]:=1;h:=1; for i:=1 to n do m:=m*2;
repeat
for i:=1 to h do
for j:=1 to h do begin
a[i,j+h]:=a[i,j]+h;{构造右上角方阵} a[i+h,j]:=a[i,j+h];{构造左下角方阵} a[i+h,j+h]:=a[i,j];{构造右下角方阵} end; h:=h*2; until h=m;
for i:=1 to m do begin
for j:=1 to m do write(a[i,j]:4); writeln; end; end.
在分治算法中，若将原问题分解成两个较小的子问题，我们称之为二分法，由于二分法划分简单，所以使用非常广泛。使用二分法与使用枚举法求解问题相比较，时间复杂度由O（N）降到O（log2N），在很多实际问题中，我们可以通过使用二分法，达到提高算法效率的目的，如下面的例子。
例2 一元三次方程求解（noip2001tg）
题目大意：给出一个一元三次方程f(x)=ax3+bx2+cx+d=0 ,求它的三个根。所有的根都在区间[-100，100]中，并保证方程有三个实根，且它们之间的差不小于1。
算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。
由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100≤x≤100),设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若： ⑴f(x1)=0，则确定x1为f(x)的根；
⑵f(x1)*f(x2)<0，则确定根x在区间[x1，x2]内。
⑶f(x1)*f(x2)>0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间；
若确定根x在区间[x1，x2]内，采用二分法，将区间[x1，x2]分成左右两个子区间：左子区间[x1，x]和右子区间[x，x2]（其中x=（x1+x2）/2）。如果f(x1)*f(x)≤0，则确定根在左区间[x1，x]内，将x设为该区间的右界值（x2=x），继续对左区间进行对分；否则确定根在右区间[x，x2]内，将x设为该区间的左界值（x1=x），继续对右区间进行对分；
上述对分过程一直进行到区间的间距满足精度要求为止（即x2-x1<0.005）。此时确定x1为f(x)的根。
源程序： {$N+}
var
x:integer;
a,b,c,d,x1,x2,xx:extended;
function f(x:extended):extended; begin
f:=((a*x+b)*x+c)*x+d; end; begin
read(a,b,c,d);
for x:=-100 to 100 do begin
x1:=x;x2:=x+1;
if f(x1)=0 then write(x1:0:2,' ') else if f(x1)*f(x2)<0 then begin
while x2-x1>=0.005 do begin
xx:=(x1+x2)/2;
if f(x1)*f(xx)<=0 then x2:=xx else x1:=xx; end;{while}
write(x1:0:2,' '); end; {then} end;{for} end.
信息学奥赛中的基本算法(贪心法)
在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。
从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。
我们看看下面的例子
例1 均分纸牌（NOIP2002tg）
[问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6 移动3次可达到目的：
从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。 [输 入]：键盘输入文件名。
文件格式：N（N 堆纸牌，1 <= N <= 100）
A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输 出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in：
4
9 8 17 6 屏慕显示：3
算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。
我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 （1） 若a[i]>v，则将a[i]-v张纸牌从第I堆移动到第I+1堆； （2） 若a[i] 为了设计的方便，我们把这两种情况统一看作是将a[I]-v张牌从第I堆移动到第I+1堆；移动后有：a[I]:=v；a[I+1]:=a[I+1]+a[I]-v； 在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(a[i+1]+a[i]-v<0 )的情况。 如n=3，三堆纸牌数为（1，2，27）这时v=10，为了使第一堆数为10，要从第二堆移9张纸牌到第一堆，而第二堆只有2张纸牌可移，这是不是意味着刚才使用的贪心法是错误的呢？ 我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张纸牌，第二堆剩下-7张纸牌，再从第三堆移动17张到第二堆，刚好三堆纸牌数都是10，最后结果是对的，从第二堆移出的牌都可以从第三堆得到。我们在移动过程中，只是改变了移动的顺序，而移动的次数不变，因此此题使用贪心法是可行的。