2022年递推与递归应用 .pdf

Jsoi2010 春季函授讲义（B3）1/16递推与递归应用一、递推思想递推关系 是一种简洁高效的常见数学模型，比如我们熟悉的Fibonacci数列问题，F（1）=0，F（2）=1，在 n2 时有：F（n）=F（n-1）+F（n-2）。在这种类型的问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联，这种关联一般是通过一个 递推关系式 来表示的。求解问题时我们就从初始的一个或若干数据项出发，通过递推关系式逐步推进，从而得到最终结果。这种求解问题的方法叫“递推法”。其中，初始的若干数据项称为“边界”。解决递推类型问题有三个重点：一是如何建立正确的递推关系式，二是递推关系有何性质，三是递推关系式如何求解。其中第一点是基础，也最重要。例 1、过河卒 问题描述 棋盘上 A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图中的C 点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如下图中的C点和 P1，P2，,，P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B 点(n,m)(n,m为不超过20 的整数),同样马的位置坐标是需要给出的，C A且 C B。现在从键盘输入n，m，要你计算出卒从A点能够到达 B点的路径的条数。问题分析 跳马是一道很老的题目，一些比赛中也经常出现过这一问题的变形（如NOIP1997初中组第三题）。有些同学一看到这种类型的题目就去盲目搜索，但事实证明：当 n,m=15 就会超时。其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（我们称之为左点）或是从上面过来（我们称之为上点），所以根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0 即可。假设用 Fi,j表示到达点(i,j)的路径数目，用 gi,j表示点(i,j)是否是对方马的控名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 16 页 -Jsoi2010 春季函授讲义（B3）2/16制点，gi,j=0表示不是对方马的控制点，gi,j=1表示是对方马的控制点。则，我们可以得到如下的递推关系式：Fi,j=0 gi,j=1 Fi,0=Fi-1,0 i 0,gi,j=0 F0,j=F0,j-1 j 0,gi,j=0 Fi,j=Fi-1,j+Fi,j-1 i0,j0,gi,j=0 上述递推关系式的边界为：F0,0=1。考虑到最大情况下：n=20,m=20，路径条数可能会超出长整数范围,所以要使用int64类型计数或高精度运算。参考程序 program ex1(input,output);const dx:array1.8 of Shortint=(-2,-1,1,2,2,1,-1,-2);dy:array1.8 of Shortint=(1,2,2,1,-1,-2,-2,-1);var n,m,x,y,i,j:Byte;g:array0.20,0.20 of Byte;f:array0.20,0.20 of Comp;begin Readln(n,m,x,y);Fillchar(g,Sizeof(g),0);gx,y:=1;for i:=1 to 8 do if(x+dxi=0)and(x+dxi=0)and(y+dyi=1000;disk:=1000;置始点至终点的距离值 d1:=1000-disk-1;求贮油点k 处至始点的距离 oilk:=d1*(2*k+1)+oilk-1;求始点藏油量 writeln(No.Distance oil);for i:=0 to k do 输出第 i 个贮油点的距离为1000-disk-i，藏油量为oilk-i；writeln(i:4,1000-disk-i:10:2,oilk-i:12:2);readln;end.例 3骨牌问题（gupai.pas）问题描述 已知 32n 个棋盘格子，试求用火柴棒覆盖所有格子的方法（一根火柴棒可覆盖2个格子）。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 16 页 -Jsoi2010 春季函授讲义（B3）5/16如 n=1 时，有如下3 种覆盖方法：输入：n，n1000。输出：用火柴棒覆盖所有32n 格子的方案数。输入样例：1 输出样例：3 提示：找出一个递推的公式。要采用高精度计算 问题分析 F(1)=3 F(2)=11 F(3)=3*f(2)+2*f(1)+2,f(n)=3f(n-1)+2f(n-2)+2f(n-3)+2f(n-4)+2f(n-5)+.+2f(1)+2 f(n)=3f(n-1)-f(n-2)+(3f(n-2)+2f(n-3)+2f(n-4)+2f(n-5)+.+2f(1)+2)f(n)=3f(n-1)-f(n-2)+f(n-1)f(n)=4f(n-1)-f(n-2)参考程序 const max=1000;var n,i,g,s,j:integer;a,b,c,d:array0.max of integer;begin assign(input,gupai.in);assign(output,gupai.out);reset(input);rewrite(output);readln(n);amax:=3;bmax:=1;bmax-1:=1;for i:=3 to n do begin fillchar(c,sizeof(c),0);g:=0;for j:=max downto 1 do begin s:=bj*4+g;cj:=s mod 10;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 16 页 -Jsoi2010 春季函授讲义（B3）6/16g:=s div 10 end;for j:=max downto 1 do if cjk，k0)。下面，我们来确定S(n，k)的边界条件,首先不能把n 个元素不放进任何一个集合中去，即 k=0 时，S(n，k)0；也不可能在不允许空盒的情况下把n 个元素放进多于n 的 k 个集合中去，即 kn 时,S(n，k)0；再者，把 n 个元素放进一个集合或把n 个元素放进n 个集合，方案数显然都是1，即 k=1 或 k=n 时，S(n,k)=1。因此，我们可以得出划分数S(n，k)的递归关系式为：S(n，k)S(n1，k1)+k*S(n1，k)(nk，k0)S(n，k)0 (nk)或(k 0)S(n，k)1 (k=1)或(k n)参考程序 program ex3(input,output);var n,k:integer;function s(n,k:integer):int64;数据还有可能越界，请用高精度计算 begin if(n0 若直线存在，则递归计算所有的交叉情况 then for r：=m downto 1do try(m-r，j+r*(m-r)else gj1；否则确定m条直线存在j 个交点 end；有了上述递归过程后，我们便可以通过下述方式计算和输出n 条直线的交点方案：1、计算 max：max=2)1(nn；计算 n 条直线的最多交点数 2、初始化：fillchar(g，sizeof(g)，0)；3、递归求 gi：try(n，0)；4、统计方案数并输出：total：=0；for i：=0 to max do if gi=1 then begin total:=total+1；输出第 total个方案为交点数i；end；三、递推与递归应用例 6、Hanoi 塔问题 问题描述 3个柱子的 Hanoi 塔问题，问n 个盘子移动过去，至少要移多少次？问题分析 当 a 柱上有 n(n=2)个盘子时，总是先借助c 柱把上面的n-1 个盘子移动到b 柱上，然后把 a 柱最下面的盘子移动到c 柱上；再借助 a 柱把 b 柱上的 n-1 个盘子移动到c 柱上；所以总共移动：hn-1+1+hn-1次。即：hn=2hn-1+1，边界条件为：h1=1。闭公式：hn =2hn-1+1=4hn-2+3=8hn-3+7=,=2n-1 h1+2n-1-1=2n-1次名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 16 页 -Jsoi2010 春季函授讲义（B3）10/16本质是什么？除了最下面的那个盘子移动了一次，其它n-1 个盘子都至少移动两次。例 7、平面分割问题 问题描述 设有 n 条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数？问题分析 设 an为 n 条封闭曲线把平面分割成的区域个数。由上图可以看出：a1=2 a2=4 a3=8 a4=14（比较困难了？）a5=22（很困难？）猜想、探究、分析，发现：a2-a1=2 a3-a2=4 a4-a3=6 a5-a4=8 从这些式子中可以看出:an-an-1=2(n-1)，即递归公式为an=an-1+2(n-1)，a1=2。证明：当平面上已有n-1 条曲线将平面分割成an-1个区域后，第n 条曲线每与曲线相交一次，就会增加2 个区域，因为平面上已有了n-1 条封闭曲线，且第 n 条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。得到：递推关系是an=an-1+2(n-1)，边界条件是a1=2。闭公式为什么呢？方法如下：an =an-1+2(n-1)an-1 =an-2+2(n-2)an-2 =an-3+2(n-3)名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 16 页 -Jsoi2010 春季函授讲义（B3）11/16,a2 =a1 +2*1 左边和右边分别累加，得：an=a1+2(1+2+,+（n-1）)=n2-n+2。例 8、自然数的拆分问题 问题描述 自然数的拆分是指把一个自然数拆成若干个自然数之和。如4 的拆分如下：4=4 4=3l 4=22 4=211 4=l 11l 现在，请你编程求出自然数n（n100）的全部拆分总数。例如输入：8 输出拆分的总数为：22 问题分析 设函数f(n,k)表示把n 分成k 个自然数的方案数，显然n 的全部拆分总数为nkknf1),(。现在的问题就是怎样求f(n,k)。首先来看f(8,3)的各种拆法：8=1+1+6 8=1+2+5 8=1+3+4 8=2+2+4 8=2+3+3 不难看出，这些拆法可以分为两类：包含 1 的拆法和不包含1 的拆法。上例中前3 个拆法属于第一类，后2 个拆法就属于第2 类。对于前三个拆法，我们把等号右边的第一个1 去掉，就形成了f(7,2)的拆法:7=1+6 7=2+5 7=3+4 对于后两个拆法，我们把等号等号右边的每个自然数都减1，就形成了 f(8-3,3)既 f(5,3)的拆法：5=1+1+3 5=1+2+2 至此，f(n,k)的求法就很明了了，即：若 1kn，则：f(n,k)=f(n-1,k-1)+f(n-k,k)否则：若k=0 且 n=0，则：f(n,k)=1 否则：若（k=0 且 n0）或（k0 且 n=0）或（kn）名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 16 页 -Jsoi2010 春季函授讲义（B3）12/16则：f(n,k)=0 程序清单 program ex7(input,output);const maxn=100;var f:array0.100,0.100 of longint;i,k,total,n:longint;begin write(Input n:);readln(n);fillchar(f,sizeof(f),0);f0,0:=1;for i:=1 to n do for k:=1 to i do fi,k:=fi-1,k-1+fi-k,k;total:=0;for k:=1 to n do total:=total+fn,k;writeln(Total=,total);end.例 9、Ackermann 函数 问题描述 已知 Ackermann 函数定义如下：1、手工计算Ack(3,2)和 Ack(3,6)。解答：29 和 509 2、写出计算Ack(m，n)的递归算法程序。program ackermann1;var m,n:longint;function ack(m,n:longint):longint;begin if m=0 then ack:=n+1 else if n=0 then ack:=ack(m-1,1)else ack:=ack(m-1,ack(m,n-1)end;begin write(Input m,n:);readln(m,n);writeln(ack(m,n)名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 16 页 -Jsoi2010 春季函授讲义（B3）13/16end.3、写出计算Ack(m，n)的非递归算法程序。program ackermann2;type stack=array 1.8000,1.2 of longint;var m,n,top:longint;s:stack;begin write(Input m,n:);readln(m,n);s1,1:=m;s1,2:=n;top:=1;while top0 do begin m:=stop,1;n:=stop,2;top:=top-1;if(top=0)and(m=0)then begin writeln(n+1);exit end;if m=0 then stop,2:=n+1 else if n=0 then begin top:=top+1;stop,1:=m-1;stop,2:=1 end else begin top:=top+1;stop,1:=m-1;top:=top+1;stop,1:=m;stop,2:=n-1 end end end.四、作业（只要交源程序）1 实数数列（realsn）源程序名realsn.?(pas,c,cpp)输入文件名realsn.in 输出文件名 realsn.out 时间限制 1秒【问题描述】一个实数数列共有n 项，已知ai=(ai-1-ai+1)/2+d，(1in)(n 60)【输入文件】输入第一行为n，m，d。第二行为，a1,an 两个整数。【输出文件】输出 am，结果保留6 位小数。【样例输入】3 2 2 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 16 页 -Jsoi2010 春季函授讲义（B3）14/161 3【样例输出】4.000000 2 金坷垃（buc）源程序名buc.?(pas,c,cpp)输入文件名buc.in 输出文件名 buc.out 时间限制 1秒金坷垃，金坷垃，小麦亩产一千八。金坷垃，金坷垃，一袋能当两袋撒。某牛看准了金坷垃的光明前途，已经储存了整整一满仓的金坷垃，这个仓库能放下N 的金坷垃。日本资源太缺乏，非洲农业不发达，日本和非洲纷纷要求购入。为了避免被偷被抢，作为奸商的某牛，又另外租了两个容量分别为Q 和 P 的仓库。他每次可以把一个仓库中的金坷垃不停地运到另一个仓库，直到目标仓库满了，或者当前仓库空了。他如此这番折腾了很多次。至于多少次，某牛自己也忘了。终于，某牛只知道，容量为Q 的仓库终于是空了。那么现在,最初容量为N 的那个仓库，可能会有多少金坷垃咧？(显然某些金坷垃已经直接或者间接地运到了容量为P 的仓库)Input Format 输入三个数Q，P，N。分别表示新租的两个仓库的容量和原来的仓库容量。Output Format 输出一行，从小到大输出最初的仓库可能的金坷垃数量。（本题的金坷垃单位，全部为Kg）Sample Input 8 9 10 Sample Output 1 2 8 9 10 Data Limit 30%:Q,P,N=10 60%:Q,P,N=100 100%:Q,P,N=1000 3.字母组合源程序名charcom.?(pas,c,cpp)输入文件名charcom.in 输出文件名 charcom.out 时间限制 1秒问题描述：字母 A，B，C的所有可能的组合（按字典顺序排序）是：A，AB，ABC，AC，B，BC，C 每个组合都对应一个字典顺序的序号，如下所示：1 A 2 AB 3 ABC 4 AC 5 B 名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 16 页 -Jsoi2010 春季函授讲义（B3）15/166 BC 7 C 找出某个字母组合的字典序号。例如，上例中AC的字典序号是4。注:假设某个字母组合为X1X2X3,XK,保证 X1X2X3,XK。输入：输入包括 2 行：第一行：N，表示字母组合由字母表中前N（N=26）个字母组成；第二行：某一个字母组合,都是大写字母；输出：该字母组合的序号；输入样例：3 AB 输出样例：2 4、拔河比赛源程序名tug.?(pas,c,cpp)输入文件名tug.in 输出文件名 tug.out 时间限制 2秒问题描述：一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体重加起来尽可能地接近。输入：数据的第 1 行是一个n，表示参加拔河比赛的总人数，n=100，接下来的n 行表示第1到第 n 个人的体重，每个人的体重都是整数（1=weight=450）。输出：包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。输入样例：3 100 90 200 输出样例：190 200 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 16 页 -Jsoi2010 春季函授讲义（B3）16/16备注：6 月 10 日前提交作业名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 16 页 -