递推法在解题方法和解题思维上的使用 东风七中叶飞

1、递推法在解题方法和解题思维上的使用东风七中叶飞对于信息学奥林匹克联赛的题目来说有人讲简单，有人讲难。为什么会有如此大的差别呢？我觉得如何选择正确的思维方式是能否顺利解决问题的关键。递推法是常用的解题方法之一，我认为它也是最好用的方法。首先我们来看一下第一题。题目是这样的：丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后去发觉原来在简单的规则下想要赢得这个游戏并不那末容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为个部分，各部分内的数字相加，相加所得的m个结果对10去模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或最小。例如，对于下面这

2、圈数字(n=4,m=2)当要求最小值时，(2-1) mod 10)×(4+3) mod 10)=1×7=7，要求最大值时，为(2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均取非负值。丁丁请你编写程序帮他赢得这个游戏。对于这题给人的第一感觉就是用穷举法，把每个情况都探到即可解题。但你要仔细看一下题目要求就会发现问题所在。题目要求n（1n50）和m（1m9）粗略估计一下所可能出现的情况应为429即是4.06×1014次。这样是无法在规定的时间里完成。那么如何解决呢？答案就

3、是用递推法。如何递推呢？我们假设有n个数分成m个部分，也可以看成切m个口。第一个切口切完后，我们就可以看成一个有n个数组成的长链。那末这第一刀就有n个切法，如下图所示。我们就先对第一种切法进行研究，也就是把从1到n个数切m-1刀分成m个部分。首先我们想象第一部分可分为1个数字、2个数字、3个数字（n-m）个数字。我们把其求和取模的结果分别存入数组的（n-m）个单元中。接着我们可以把第一、二部分合并考虑了，我们可以认为只有（n-m+1）个数字分成两个部分和（n-m）个数字分成两个部分和2个数字分成两个部分的（n-m）种情况。见下图所示，两个部分寻找最大值过程。我们再把每种情况中的最大值和最小值找

4、出，分别存入d和x两个数组中。再接着我们可以把第一、二、三部分合并考虑了，我们可以认为只有（n-m+2）个数字分成三个部分和（n-m+1）个数字分成三个部分和3个数字分成三个部分的（n-m）种情况。我们再把每种情况中的第三部分，分别于两个部分的最大值和最小值相乘就可以找到三个部分的最大值和最小值。如下图所示，三个部分寻找最大值过程。如此进行下去，我们就可以把从1到n个数切m-1刀分成m个部分的最大值和最小值求出来。如此往复，我们就可以解出这道题了。下面就是我所编的参考程序：Var a,b:Array1.100Of integer; d,x:Array1.50Of longint; m,n,l,

5、i,j:Integer; mk,sk:longint;Procedure Work; Var i,j,s,k,k1:Integer; da,xiao:longint; Begin for i:=1 to l do begin s:=0; for j:=1 to l-i+1 do begin s:=s+bm+j+i-2; end; di:=s mod 10; if di<0 then di:=di+10; end; x:=d; for i:=m-1 downto 1 do begin for j:=1 to l do begin da:=0;xiao:=90000000; for k:=j

6、 to l do begin s:=0; for k1:=j to k do s:=s+bi+k1-1; s:=s mod 10; if s<0 then s:=s+10; if da<s*dk then da:=s*dk; if xiao>s*xk then xiao:=s*xk; end; dj:=da;xj:=xiao; end; end; end;begin readln(n,m); mk:=0;sk:=90000000;l:=n-m+1; for i:=1 to n do readln(ai); for i:=1 to n-1 do ai+n:=ai; for i:

7、=1 to n do begin for j:=1 to n do bj:=ai+j-1; Work; if mk<d1 then mk:=d1; if sk>x1 then sk:=x1; end; writeln(sk);writeln(mk);end.接下来我们来看一下第二题。题目是这样的：栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给

8、出答案，所以需要你的帮忙。宁宁考虑的是这样一个问题：一个操作数序列，1，2，一直到n（图示为1到3的情况），栈A的深度大于n。现在可以进行两种操作，1、将一个数，从操作数数列的头端移到栈的头端（对应数据结构栈的push操作）2、将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由123生成序列231的过程。（原始状态如上图所示）你的程序将对给定的n，计算并输出由操作数序列1，2，3，n经过操作可能得到的输出序列的总数。这题最大的难点是如何排出任何数的所有输出序列。如果硬排的话，很可能会出现漏排或重排的现象。

9、要用递推法就比较容易得出正确结论的，请看递推过程。如果操作数只有1个，那么输出序列的总数也只有1种。如果操作数有2个，那么输出序列的总数就有2种。即：如果操作数有3个，那么输出序列的总数就有5种。即：如果操作数有4个，那么输出序列的总数就有14种。即：如果操作数有5个，那么输出序列的总数就有42种。即：由此我们不难发现递推的规律，即n种计算方法为：n参考程序如下：var a:array0.50of longint; n,j,i,m:longint;begin readln(n); a1:=1; for i:=2 to n do begin m:=ai-1*2; for j:=1 to i-2

10、do m:=m+aj*ai-j-1; ai:=m; end; writeln(an);end.最后我们来看一下第三题，题目是这样的：形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数。2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P3021377,它有909526位。麦森数有许多重要应用，它与完全数密切相关。任务：数如P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）这体看起来比较简单，用log2来计算位数；用一个500单元的数组不停地乘2就可。但是如果P3100000的

11、话，那么就要计算1.55×109次，这样在10秒钟以内是无论如何也无法完成的。那么如何提高速度呢？答案还是用递推法。其具体方法如下：学过编程的人都知道要把一个二进制的数变成十进制的方法是：不断地乘1 2 3 4 5 6 7二、加一。例把1011010变成十进制就是从首位的第二位开始。首先把2×2，接着看第二位是0还是1，如果是1就加二，否则就不加。这样就完成了首位的第二位计算。摘下来就可以按照此法对第三位进行计算，如此往复就可以把一个二进制的数变成十进制了。即(2×2+0)×2+1)×2+1)×2+0)×2+1)×

12、2+0=90。这样就可以由首位递推完成。同样2P也可以先把P变成二进制，再由首位递推变成十进制即可。只是乘二的地方变成平方（2n×2=2n×2n）；加一的地方变成乘二（2n+1=2n×2）。这样就可以大大减少计算量，当P=3100000时大约为2.63×106次。参考程序如下：var a,b,c:array1.501of integer; j1,j,i,w,y,k,l:integer; n,m:longint; d:array1.50of integer;begin readln(n);m:=n;l:=0; while m>0 do begin l

13、:=l+1;dl:=m mod 2;m:=m div 2; end; FillChar(c,SizeOf(c),0); a1:=2;b1:=2; for j1:=l -1downto 1 do begin c501:=0; for j:=1 to 500 do begin for i:=1 to 501-j do begin ci+j-1:=ci+j-1+ai*bj; ci+j:=ci+j+(ci+j-1 div 10); ci+j-1:=ci+j-1 mod 10; end; end; b:=c;a:=c; FillChar(c,SizeOf(c),0); if dj1>0 then begin k:=0; for i:=1 to 500 do begin m:=ai*2+k;ai:=m mod 10;k:=m div 10