递推算法
    在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第N项数或所有的数列元素（如果可以枚举的话），或求前N项元素之和。这种从已知数据入手，寻规则，推导出后面的数的算法，称这递推算法。
    典型的递推算法的例子有整数的阶乘，1，2，6，24，120…，a[n]=a[n-1]*n(a[1]=1)；前面学过的2n，a[n]=a[n-1]*2(a[1]=1)，菲波拉契数列：1，2，3，5，8，13…，a[n]=a[n-1]+a[n-2](a[1]=1,a[2]=2)等等。
    在处理递推问题时，我们有时遇到的递推关系是十分明显的，简单地写出递推关系式，就可以逐项递推，即由第i项推出第i+1项，我们称其为显示递推关系。但有的递推关系，要经过仔细观察，甚至要借助一些技巧，才能看出它们之间的关系，我们称其为隐式的递推关系。
    下面我们来分析一些例题，掌握一些简单的递推关系。
    例如阶梯问题：题目的意思是：有N级阶梯，人可以一步走上一级，也可以一步走两级，求人从阶梯底走到顶端可以有多少种不同的走法。
    这是一个隐式的递推关系，如果编程者不能出这个递推关系，可能就无法做出这题来。我们来分析一下：走上第一级的方法只有一种，走上第二级的方法却有两种（两次走一级或一次走两级），走上第三级的走法，应该是走上第一级的方法和走上第二级的走法之和（因从第一级和第二级，都可以经一步走至第三级），推广到走上第i级，是走上第i-1级的走法与走上第i-2级的走法之和。很明显，这是一个菲波拉契数列。到这里，读者应能很熟练地写出这个程序。在以后的程序习题中，我们可能还会遇到菲波拉契数列变形以后的结果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。
    我们再来分析一下尼科梅彻斯定理。定理内容是：任何一个整数的立方都可以写成一串连续的奇数和，如：43=13+15+17+19=64。
    从键盘输入一个整数n，要求写出其相应的连续奇数。
    我们不妨从简单入手，枚举几个较小的数据：
    13=1
    23=3+5
    33=7+9+11
    43=13+15+17+19
    53=21+23+25+27+29
根据上面的例子，读者不难看出：
（1）输入为n时，输出应有n项。
（2）输入分别为1，2，3…时，则输出恰好为连续奇数，1，3，5，7，9，11…即下一行的首项比上一行的末项大2。
    经上面的分析，原本看不出递推关系的问题，呈现出递推关系。在趣的是，这个例子的递推过程，可以有多种算法。
    算法一：将所有奇数逐项例举出来，然后将其分段，即:
1; 3 5; 7 9 11; 13 15 17 19; 21…
1  2  3    4        5…
算法二、设输入为n时的输出第一项为a[n]，则a[n]=a[n-1]-n+1;
于是我们推出首项后，则输出为a[n]+a[n]+2+…+a[n]+2(n-1)
算法三、进一步总结，不难得出，若输入为n时，首项a[n]=n2-n+1，其余同算法二。下面我们来分析两个与动物有关的趣题。
狡兔三窟
兔子生活在山脚下，围绕山脚有N个洞。一狼经常出没在这些洞口，对免子构成威协。聪明的兔子想出一条计策，与狼谈好了一个条件。兔子说自己呆在某一个洞中不走，要求狼从第一个洞口开始跳过一个洞到第三个洞，然后再跨越两个洞到第六个洞，然后再跨越四个、五个……，直到跨越的洞数为十个时，又从跨越一个洞开始。如果狼在某一洞中遇到
兔子，则兔子心甘情愿做狼的美餐。如果狼在有限的时间里遇不到兔子，以后就不能再侵犯兔子了。
狼想，这个主意不坏，只要你兔子呆着不动，我就总有机会抓到你，比跟狡猾的兔子捉迷藏好，于是欣然同意。聪明的读者，对于给定的洞数N，你能否告诉兔子，是否有安全洞，安全洞号是哪些或哪个？
例如，n=11,则狼的跳跃过程如下：11->32->63->104->45->106->……。上述表示中，大号数字表示狼到过的洞号，下标小号字表示越的洞数。
这个题目中，读者不难理解，如果狼每次都能走入一个以前没有到过的洞中，则无论兔子怎么躲藏，都不能幸免遇狼。若狼跳越若干次后，不仅走到了以前到过的洞中，而且要跳越的洞数又与以前的某次相同，则狼就会循环往复地在同一些洞中跳来跳去，成为小丑而无法跳入以前没有到过的洞中。这些洞恰恰就是兔子的安全洞穴。
基于以上的分析，兔子有安全洞穴的条件有三，一是狼经过若干次跳跃后，回到原来到过的洞中;二是同一洞历史上的某一次跳越的洞数与即将要跳的这一次跨越的洞数也相同；三是到此时为止，狼应有从未到过的洞穴。
基本的算法是：从1号洞开始，按11->32->63->104->45->106->……方式,由前一个状态推导出下一个状态，同时将每一个新状态与前面存贮下来的状态作比较，以便到两个可以作结论的状态。即要么狼已走遍了所有兔子洞，要么狼卷入死循环，而有些洞无法进入。
那么，现在我们怎样来存贮这些状态呢？最简单的办法是计数。
我们对每个洞建立一个数组，用来记载这个洞狼是否到过，在这个洞中跳越洞数，以及狼所经历过的新洞数。程序的关键部分如下，其余部分请读者完善。
program ex02;
var a:,0..10] of 0..1;
  t:integer;
  j:integer;
  s:integer;
begin
  fillchar(a,sizeof(a),0);
t:=1;
j:=1;
a[t,j]:=1;
s:=1;
  repeat
    t:=t+j+1;
if t>n then t:=t mod n;
if a[t,j]=1 then break;
j:=j+1;
if j>10 then j=1;
if a[t,0]=0 then inc(s);
  until (s=n)
  if s=n then write(0) else
  for k:=1 to n do
    if a[k,0]=0 then write(k:4);
end;
a[k,0]=1或0，代表狼是否到过第k洞。
a[k,j]=1或0,代表在第k洞中，狼是否跳越过j个洞。
目前狼跳入的洞号
目前狼要跳越的洞数
狼已进入个的洞数
养成赋初值的好习惯
开始狼在第一洞中
开始狼跳越的洞数
第一洞跨越个一洞
狼到过了一洞
循环递推
递推下一个洞号
回到前面的小号洞，形成环形。
狼已进入死循环，但程序不能“死”
跳越洞数累加
该洞没来过，则到过的洞数加一
所有洞狼都到过了
输出从未到过的洞号
另一个趣题是猴子吃桃问题：山中住有五只猴。一天，老大看见一堆桃子，想把桃子据为已有，却担心让老二老三知道了说自己太贪心。于是将桃分成相等的两份，却发现剩余一个，于是，老大吃掉这一个以后，再带走这堆桃的二分之一。第二天，老二也看到了这堆桃，其想法和做法与老大一样，老三老四老五也和他们的兄长想到一块去了。结果等老五吃完一个，带走一半以后，这堆桃还剩余11个。请编程计算当初这堆桃共有多少个。
这个下题目明眼人一看便知，我们如果按兄弟吃桃搬桃的相反顺序倒推过去，就能知道当初桃子的总数。其递推的公式是a[n-1]=a[n]*2+1。递推的初始值是a[5]=11（又称边界条件），待求a[0]的值。相信阅读本书到了此处的读者，很容易就能写出正确的程序。作者在这里不过是想明确一下，递推算法不仅可以顺着推、也可逆着推的道理。
挖地雷
●
●
●
●
●
●
2
2
2
2
3
2
2
1
windows操作系统自带有一个挖地雷游戏，本题将其简化为仅一行地雷。如右图所示，表中第一行有黑点的位置表示一颗地雷。而第二行每格中的数字表示与其相邻的三格中地雷的总数。
输入数据给定一行的格子数n(n<=10000)和第二行的各个数字，编程求第一行的地雷分布。右图所示的输入输出样例为：
输入：          输出：
8              1 1 0 1 1 1 1 0 1
2 2 2 2 3 2 2 1
如果设输入数据为a[1]…a[n]，输出结果为b[1]…b[n]，则根据题意，我们应该不难得出下面的结论：
1) a[k]:=b[k-1]+b[k]+b[k+1];
2) a[1]和a[n]都会小于3；
        0        b[1]=0  b[2]=0
3) a[1]=  1  则  b[1]=1  b[2]=0或b[1]=0 b[2]:=1
        2        b[1]=1  b[2]=1
有了上述三个结论后，程序算法便跃然纸上。我们先根据a[1]得到b[1]和b[2]的值，然后递推出b[3]到b[n]。
在递推过程中，若递推出某个值b[k]>1或b[k]<0，如果a[1]=1，则交换b[1]和b[2]的值，然后再重新递推，若a[1]=0,2或已交换b[1],b[2],则问题无解。
procedure bomp;
const maxn=10000;
var a,b:axn+1] of byte;
i,j,n,:integer;
f:boolean;
function calcul:boolean;
  begin
    for i:=2 to n do begin
      b[i+1]:=a[i]-b[i-1]-b[i];
      if (b[i+1]<0) or (b[i+1]>1) or (b[n+1]<>0) then
        begin calcul:=false;exit;
      end else calcul:=true;
    end;
  end;
begin
  assign(input,'bomp.in');reset(input);
  readln(n);
  for i:=1 to n do read(a[i]);
  a[0]:=0;a[n+1]:=0;
  close(input);
  if a[1]=0 then begin
    b[1]:=0;b[2]:=0;
  end else if a[1]=2 then begin
    b[1]:=1;b[2]:=1;
  end else begin
    b[1]:=0;b[2]:=1;
  end;
  f:=calcul;
  if (a[1]=1) and not f then begin
    b[1]:=1;b[2]:=0;f:calcul
  end;
  if f then for I:=1 to n do write(b[I]:2);
  else write('No answer');
end.
输入输出数据。
递推过程；
递推式;编程递归函数
b[n+1]必须为0.
唯一情况
两值情形；
唯一情形。
递推算法是一个高效的算法，其时间复杂度是O(n)的。不仅如此，它同时也是后面要学习的其它算法的基础，读者应该好好地把握它，多做这方面的习题积累经验。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。