NOIP基本算法之递推

递推算法递推是计算机数值计算中的一个重要算法。思想是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机善长于重复处理的特点。例：切煎饼王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切100刀最多能分成多少块？”找规律，如下图：令qn为切n刀能分成的块数，从图中可见：q1=11=2q2=112=4q3=1123=7q4=11234=11在切法上让每两条线都有交点，则有qn=qn-1nq0=1有了递推方程，程序就很简单。解决递推问题的一般步骤

建立递推关系式确定边界条件递推求解递推的形式顺推法和倒推法问题1、杨辉三角形（YHTriangle）【问题描述】杨辉三角是一个由数字排列成的三角形数表，一般形式如下：111121133114641151010511615201561172135352171【输入数据】一个正整数n，表示三角形的行数【输出数据】n行杨辉三角形

问题分析：观察杨辉三角形不难看出，数字是有规律的，从第3行开始，每行第1个和最后一个值为1，其他值为上方和左上方数字和。设二维数组c存储行坐标为i、列坐标为j位置上元素值，则c=ci-1,j-1ci-1,j每个元素值由其左上方和上方元素求和得到，因此，可以一行地求得元素值。算法描述：存放杨辉三角形的值；2．赋初值：c:=1;3．用二重循环控制二维数组下标的变化，从上到下，从左到右求元素值；4．输出杨辉三角形。程序设计：YHtriangle;const n=20;//输出行数var c:arrayoflongint; i,j,m:longint;beginc:=1;c:=1; fori:=3tondo//从第3~n行 begin c:=1; forj:=2toi-1do//从第2~i-1列 c;//求二维数组元素值 c:=1;

end; fori:=1tondo forj:=1toido ifj=ithenwritelnc,'';//输出杨辉三角形end问题2、数字三角形（NT）【问题描述】给定一个具有N层的数学三角形如下图，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。2621841568【输入数据】 第1行，一个正整数n，表示三角形的行数 第2至n1行，照描述输入三角形【输出数据】 最小路径得分，行末有换行【样例输入】42621841568【样例输出】10【注意】测试数据规模：保证100%的数据n<=1000。问题分析：求最小路径得分，比较容易想到的是：1．如果知道从第1行走到第n行各数字上的最小得分，那么，从中取最小值即可；2．第n行是从n-1行走下来的，如果知道第n-1层各数字位置上的最小得分值，那么根据规则每步只能沿左斜线向下或沿右斜线向下，要使第n层的各数字位上得到最小得分值，只能从左上和右上两个得分值中取小的一个与当前位的数字相加；3．同理，第n-1层各数位上的最小得分可以从第n-2层推出；4．考虑第I层与第I-1层的关系，可以推出如下关系：设D表示第I层，第J列位置上的数字，则：D）A，那么问题的解为D（1≤J≤n）中最小数。进一步分析：在上述分析中，思考问题的角度按照题意给出从第1层到第n层，如果换个角度从第n层到第1层，每次按规则从可选的相邻两数中选择小的数向上传递，可以发现效果是一样，且当走到第1层时，即为最小分值和。这样就不必再在最后一行中求最小数。算法描述：1、定义二维数组a存放数据；2、读入原始数据；3、控制循环变量i从n-1行到第1行，每行重复下列操作：求每列的元素值为当前元素值与a两元素中最小值之和；4．输出a。程序设计：Nt;VarN:longint;A:arrayoflongint;I,j:longint;BeginReadlnn;Fori:=1tondoBeginForj:=1toidoreada;Readln;End;Fori:=n-1downto1do//控制第n-1行至第1行Forj:=1toido//每个元素值为下方和右下方两数中小的数加自身数Ifatheninca,a;//输出最小分值和End问题:3：守望者的逃离（NOI/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒s为单位。且每次活动的持续时间为整数秒。距离的单位为米m。

【输入文件】仅一行，包括空格隔开的三个非负整数M，S，T。【输出文件】包含两行:

第1行为字符串"Yes"或"No"区分大小写，即守望者是否能逃离荒岛。第2行包含一个整数，第一行为"Yes"区分大小写时表示守望着逃离荒岛的最短时间。第一行为"No"区分大小写时表示守望者能走的最远距离。【输入输出样例1】

392004No197

【输入输出样例2】

3625510Yes

6

【限制】

30%的数据满足:1<=T<=10，1<=S<=100

50%的数据满足:1<=T<=1000，1<=S<=10000

100%的数据满足:1<=T<=300000，0<=M<=10001<=S<=10^8

【简述】已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。即：要在最短时间走最多的路程，每秒有三种方法：休息（魔法恢复4）；跑步（移动17m）；闪烁法术（花费10魔法，移动60m）。【分析】从题意中，我们可以得到如下信息：1．休息和闪烁法术是有关联的（要不然还不如不休息）；2．有魔法的情况下，尽量用闪烁法术（因为闪烁法术移动最远）；3．在魔法不够的情况下，对休息（等待魔法恢复使用闪烁法术）还是跑步进行选择。

为了理清信息，不妨将跑步和使用闪烁法术分开处理。设想：1．如果“守望者”不会跑步，记第i秒的能到达最大距离为f60当m（魔法）≥10时，同时m=m-10（魔法足够使用魔法）f当m＜10时，同时m=m4（休息恢复魔法值）通过这样一个预处理，解决了闪烁法术的使用。2．把跑步的情况加入，则：f17}（注意：令f=0）此时在跑步与跑之间做选择如此，得到了解决问题的递推式。当f值，否则，输出“Yes”及f值刚好离岛时i值。算法描述：1．读入数据；2．计算只使用闪烁法术时的每秒最大距离；3．计算加入跑步选择时的每秒最大距离，如果在某时刻刚好离岛，则输出离岛时间，结束；4．如果不能离岛，输出最远距离，结束。readlnm,s,t;//读入数据Fori:=1totdo//计算只使用闪烁法术时的每秒最大距离 begin ifm>9then//如果魔法值足够就使用瞬移begin f60; decm,10; end elsebegin//如果魔法值不够休息 f; incm,4; end; end;Fori:=1totdo//计算加入跑步选择时的每秒最大距离 begin iff:=f>=sthenbegin//刚好离岛，输出 writeln'Yes'; writelni; halt; end;end;writeln'No';//不能离岛，输出writelnf;end本题有多种解决问题的方法，然而，在上述分析中很巧妙地运用了分而治之的思想，把原来跑步、魔法、休息交错在一起的问题条件分离开，考虑在只有魔法情况下每秒最远距离，此时，很容易用上问题的贪心条件，能用魔法尽量用上魔法，求只有魔法情况下每秒最远距离的递推式写起来也很简单。接着，考虑跑步的情况，当前秒的跑步距离由上一秒加17递推得到，每秒最远距离为跑步距离和魔法距离中的最大值。这是一道很好的题，建议大家用不同方法解决之，然后，从中体会分解问题的方法和技巧。问题4奇因数（fsum）【问题描述】 我们定义f为最大的奇数因数。比如F18=9 输入n，输出f1f2…fn【输入文件】一个整数，n。【输出文件】输出连加的和。【样例输入】5【样例输出】11【数据规范】30%:n<=100060%:n<=1000000100%:n<=1000000000问题分析：根据题意，对于所有奇数f=，对于一个偶数f=f/2，那么，很容易用On时间求得问题的解。然而，观察数据规模n<=1000000000，有否更快的解决问题的算法呢？设s=f1f2…f，进一步推得：1．对于一个s，如果是奇数，那么由于f=，则s=s-1，转化为偶数和加；2．如果是偶数，那么我们可以把f1到f的求和分为s奇数和s偶数；得到：1s奇数=135-1=*/42s偶数=f2f4f6f=f1f2f3f/2=s/23为偶数时s=*/4s/2综上所述当为奇数时，s=s-1=s-1/2-1*-1/4=s-1/21*1/4

根据这个递推式看出，一个n规模的值可以由n/2规模的值推出，即运算时间复杂度为Olog2n。s是一个递推式也是否个累加式，程序实现时，采用倒推思想实现更为方便，不断让n=ndiv2，累加对应n的累加项值。算法描述：设所求最大的奇数因数和为ans；读入n值；当n>0时，重复下列操作：当n为奇数时，ans=ansn1*n1/4;当n为偶数时，ans=ansn*n/4;n=ndiv2；的值。程序设计：Fsum;VarAns:int64;N:int64;I:longint;BeginReadlnn;Whilen>0do//采用倒推思想求最大的奇数因数和BeginIfoddnthenAns:=ans1n*ndiv21div2elseAns:=ansn*ndiv2div2;N:=ndiv2;End;Writelnans;End问题5：过河卒（Soldier）【问题描述】如图，A点有一个过河卒，需要走到目标B点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如图点上的马可以控制9个点（图中除A，B之外的黑点）。卒不能通过对方马的控制点。C棋盘用坐标表示，A点（0，0）、B点（n,m）n,m为不超过100的整数，同样马的位置坐标是需要给出的（约定:C<>A，同时C<>B）。现在要求你计算出卒从A点能够到达B点的路径的条数。【输入数据】B点的坐标（n,m）以及对方马的坐标（,Y）【输出数据】一个整数（路径的条数）。【样例输入】6632

【样例输出】17问题分析：设二维数组a表示从A点走到第I行第j列位置的路径条数。按题意，过河卒只能向下、或者向右行走。1．观察图中行坐标轴和列坐标轴上点的路径条数，则：A=1

2．对于没被马控制的坐标点，如图中点，则：A=2同理：任意一个没被马控制的坐标点点，则：Ａ［Ｉ，Ｊ］＝Ａ［Ｉ－１，Ｊ］＋Ａ［Ｉ，Ｊ－１］3对于被马控制的坐标点，则：Ａ［Ｉ，Ｊ］=0那么，对于已知马点坐标，如何标识被马控制的坐标点呢？如图所示，根据马的走步规则，中心位置马所能控制的点为图中的1~8点，设d、dy表示被马控制点相对于马的坐标位移，则：D=2,1,-1,-2,-2,-1,1,2 Dy=