递推与动态规划.docx
- 文档编号:11204564
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:199
- 大小:97.69KB
递推与动态规划.docx
《递推与动态规划.docx》由会员分享,可在线阅读,更多相关《递推与动态规划.docx(199页珍藏版)》请在冰点文库上搜索。
递推与动态规划
目录
第一章递推与动态规划
2001年普及组第1题--数的计数-----------------------ok------------------------
2003年提高组第3题--加分二叉树--------------------ok------------------------
2000年普及组第3题--乘积最大-----------------------ok------------------------
2003年普及组第2题--数字游戏-----------------------ok------------------------
2001年提高组第3题--统计单词个数-----------------ok------------------------
1997年普及组第3题--街道路径条数-----------------ok------------------------
2002年普及组第4题--过河卒--------------------------ok------------------------
1997年普及组第1题--统计正方形和长方形个数--ok------------------------
1997年提高组第3题--骑士游历-----------------------ok------------------------
2000年提高组第4题--方格取数-----------------------ok------------------------
2003年普及组第3题--栈--------------------------------ok------------------------
1996年提高组第3题--挖地雷--------------------------ok------------------------
1999年提高组第1题--拦截导弹-----------------------ok------------------------
2004年提高组第3题--合唱队形-----------------------ok------------------------
2001年普及组第4题--装箱问题-----------------------ok--------------------------
1996年提高组第4题--砝码秤重-----------------------ok--------------------------
第一章递推与动态规划
2001年普及组第1题--数的计数
【问题描述】
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
(1)不作任何处理;
(2)在它的左边加上一个自然数,但该自然数不能超过原数的一半;
(3)加上数后,继续按此规则进行处理,直到不能再加自然数为止。
【输入格式】
输入文件count.in中只有一个数n
【输出格式】
输出文件count.out只有一行,该行只有一个数,表示求得的满足要求的数的个数。
【输入样例】
6
【输出样例】
6
【输入/输出样例说明】
输入数字6按以上处理方法,能得到如下的6个数字:
6
16
26
126
36
136
【官方测试数据】
序号
输入
输出
1
1
1
2
10
14
3
50
786
4
100
9828
5
198
195830
【分析】
一.题意分析
以f[i]表示i经处理能得到的数的个数。
则:
图1数1处理后,
只能得到1
1.如图1所示,1经处理,只能得到1本身(1个数)。
因此f[1]=1;
2
2
1
2
2
1
图2数2处理后,
得到2、12
2.如图2所示,2经处理,能得到的数的个数f[2]:
(1)2本身(1个数)。
(2)2前加1;对1继续处理,能得到的数个数为f[1];
因此,f[2]=1+f[1]=1+1=2。
3
3.如图3所示,3经处理,能得到的数的个数f[3]:
(1)3本身(1个数)。
(2)3前加1;对1继续处理,能得到的数个数为f[1];
因此,f[3]=1+f[1]=1+1=2。
4
4.如图4所示,4经处理,能得到的数的个数f[4]:
(1)4本身(1个数)。
(2)4前加1;对1继续处理,能得到的数个数为f[1];
(3)4前加2;对2继续处理,能得到的数个数为f[2];
因此,f[4]=1+f[1]+f[2]=1+1+2=4。
5.如图5所示,5经处理,能得到的数的个数f[5]:
(1)5本身(1个数)。
(2)5前加1;对1继续处理,能得到的数个数为f[1];
(3)5前加2;对2继续处理,能得到的数个数为f[2];
因此,f[5]=1+f[1]+f[2]=1+1+2=4。
5
6
6.如图6所示,6经处理,能得到的数的个数f[6]:
(1)6本身(1个数)。
(2)6前加1;对1继续处理,能得到的数个数为f[1];
(3)6前加2;对2继续处理,能得到的数个数为f[2];
(4)6前加3;对3继续处理,能得到的数个数为f[3];
因此,f[6]=1+f[1]+f[2]+f[3]=1+1+2+2=6。
图7f[i]的计算公式
如图7所示,一般地,对数字i处理后,能得到的数的个数为:
f[i]=1+f[1]+f[2]+…+f[idiv2]。
二.如图8所示,求数12经处理后,能得到的数的个数的过程
图8f[12]的计算过程
1。
计算f[1];
f[1]=1;
2。
由f[1]计算f[2];
f[2]=1+f[1]=1+1=2;
3。
由f[1]计算f[3];
f[3]=1+f[1]=1+1=2;
4。
由f[1]、f[2]计算f[4];
f[4]=1+f[1]+f[2]=1+1+2=4;
5。
由f[1]、f[2]计算f[5];
f[5]=1+f[1]+f[2]=1+1+2=4;
6。
由f[1]、f[2]、f[3]计算f[6];
f[6]=1+f[1]+f[2]+f[3]=1+1+2+2=6;
7。
由f[1]、f[2]、f[3]、f[4]、f[5]、f[6]计算f[12];
f[12]=1+f[1]+f[2]+f[3]+f[4]+f[5]+f[6]=1+1+2+2+4+4+6=20;
【算法1】
1.输入n;
2.f[1]←1;
3.fori←2tondiv2do{计算f[2]至f[ndiv2]}
4.f[i]←1+f[1]+f[2]+…+f[idiv2];
5.f[n]←1+f[1]+f[2]+…+f[ndiv2];
6.输出f[n];
【参考程序1】
programp2001_1(input,output);
constmaxn=10000;
vari,j,n:
Integer;
f:
array[1..maxn]oflongint;
begin
assign(input,'count.in');reset(input);
assign(output,'count.out');
rewrite(output);
readln(n);
close(input);
f[1]:
=1;
fori:
=2tondiv2do
begin
f[i]:
=1;
forj:
=1toidiv2do
f[i]:
=f[i]+f[j];
end;
f[n]:
=1;
fori:
=1tondiv2do
f[n]:
=f[n]+f[i];
writeln(f[n]);
close(output);
end.
【算法的复杂性】
求f[n]的运算次数:
1.f[1]:
=1的1次;
2.求f[i]的二重循环的运算次数不大于:
=n2/16+5n/8-3/2
3.f[n]:
=1的1次;
4.求f[n]的循环的运算次数不大于n/2次:
因此合计运算次数不大于:
1+n2/16+5n/8-3/2+1+n/2=n2/16+9n/8+1/2次。
因此此算法的时间复杂度为O(n2)。
【算法的改进】
一.递推式的改进
如果输入数据要求n最大规模达到1000000。
此时,上述O(n2)的算法在n较大时,必定超时。
我们寻找更好的算法。
我们将求f[i]的递推式f[i]=1+f[1]+f[2]+…+f[idiv2]作一改进。
(1)f[2k+1]=1+f[1]+f[2]+…+f[(2k+1)div2]
=1+f[1]+f[2]+…+f[k]
=1+f[1]+f[2]+…+f[(2k)div2]
=f[2k];
即f[2k+1]=f[2k]
(2)f[2k+2]=1+f[1]+f[2]+…+f[k+1]
=1+f[1]+f[2]+…+f[k]+f[k+1]
=f[2k]+f[k+1]
即f[2k+2]=f[2k]+f[k+1]
二.几个实例求解过程
1.求f[16],如图9所示。
f[8]
(1)求初值f[1]、f[2]:
f[1]=1;f[2]=2;
(2)求f[3]、f[4]:
f[3]=f[3-1]=f[2]=2;
f[4]=f[4-2]+f[4div2]=f[2]+f[2]=2+2=4;
(3)求f[5]、f[6]:
f[5]=f[5-1]=f[4]=4;
f[6]=f[6-2]+f[6div2]=f[4]+f[3]=4+2=6;
(4)求f[7]、f[8]:
f[7]=f[7-1]=f[6]=6;
f[8]=f[8-2]+f[8div2]=f[6]+f[4]=6+4=10;
(5)求f[16]:
f[16]=1+f[1]+f[2]+f[3]+f[4]+f[5]+f[6]+f[7]+f[8]=1+1+2+2+4+4+6+6+10=36;
2.求f[15]
(1)求初值f[1]、f[2]:
f[1]=1;f[2]=2;
(2)求f[3]、f[4]:
f[3]=f[3-1]=f[2]=2;
f[4]=f[4-2]+f[4div2]=f[2]+f[2]=2+2=4;
(3)求f[5]、f[6]:
f[5]=f[5-1]=f[4]=4;
f[6]=f[6-2]+f[6div2]=f[4]+f[3]=4+2=6;
(4)求f[7]、f[8]:
f[7]=f[7-1]=f[6]=6;
f[8]=f[8-2]+f[8div2]=f[6]+f[4]=6+4=10;
(5)求f[15]:
f[15]=1+f[1]+f[2]+f[3]+f[4]+f[5]+f[6]+f[7]=1+1+2+2+4+4+6+6=26;
【算法2】
1.输入n;
2.f[1]←1;
3.f[2]←2;
4.s←2;
5.逐对产生f[2k+1]、f[2k+2]的值{f[2k+1]←f[2k]和f[2k+2]←f[2k]+f[k+1]};
6.f[n]←1+f[1]+f[2]+…+f[ndiv2];
7.输出f[n];
【参考程序2】
programp2001_1(input,output);
constmaxn=500000;
vari,n,m,s:
longint;
f:
array[1..maxn]ofreal;
g:
real;
begin
assign(input,'count.in');reset(input);
assign(output,'count.out');rewrite(output);
readln(n);
close(input);
f[1]:
=1;
f[2]:
=2;
m:
=ndiv2div2;{其实产生(ndiv2-1)div2对即可}
s:
=2;
fori:
=1tomdo{产生m对}
begin
s:
=s+1;
f[s]:
=f[s-1];{f[2k+1]}
s:
=s+1;
f[s]:
=f[s-2]+f[sdiv2];{f[2k+2]}
end;
g:
=1;
fori:
=1tondiv2do{g=1+f[1]+f[2]+…+f[ndiv2]}
g:
=g+f[i];
writeln(g:
0:
0);
close(output);
end.
【算法2的复杂性】
1.时间复杂度:
(1)产生m对f[2k+1]和f[2k+2]时,f[s]的计算次数为:
2*m=2*(ndiv2div2)≤n/2。
(2)产生m对f[2k+1]和f[2k+2]时,s类加次数为:
2*m=2*(ndiv2div2)≤n/2。
(3)产生g(f[n])时的循环,计算ndiv2≤n/2。
因此最多计算3n/2次。
算法2的时间复杂度为O(n)。
2.空间复杂度:
需要一个f数组保存中间结果。
每个real型数据占8B,因此,需要额外空间为:
500000*8B=4000000B≈4000KB≈4MB。
【问题】
上述程序2运行时,n输入最大的值1000000时,输出为:
1.646006492004638E042
表示当n=100万时,f[n]=1.646006492004638*1042。
即f[100万]有43位数。
而real实型最多只有16位有效数字。
因此,必须采用高精度数来保存各f[i]的值。
若以1位整数表示10进制的1位数字,43位数,需要一个43元素的数组来保存。
则每计算1次f[i]的值,需计算43次。
因此合计计算量为43n。
当取100万时,需进行4300万次运算。
这在限时1秒的情况下,肯定超时。
(当n=100万时,在某机器上,程序2实际测得运行时间为6秒23)。
下面的程序3以1位长整型(longint)来表示高精度数的9位数字。
每个f[i]的43位数,可以用5个长整型数来表示。
如:
(1)1的计数为1,以f[1,1]=1,f[1,2]=0,f[1,3]=0,f[1,4]=0,f[1,5]=0;
(2)4550的计数为187********6422,如图10所示,以f[4550,1]=9136422,f[4550,2]=187894,f[4550,3]=0,f[4550,4]=0,f[4550,5]=0来表示。
图104550的计数,以5个长整型数表示
因为长整型可表示-21亿多至21亿多的数,即它有10位数位。
求f[2k+2]时,f[2k+2]的第j位=f[2k]的第j位+f[k+1]的第j位+求第j-1位时产生的进位。
f[2k]的第j位和f[k+1]的第j位都小于10亿,两者相加,小于20亿,在长整型表示范围内。
当某位相加和超过999999999时,向下一位进位。
处理方法其实类似10进制。
我们可以当作10亿进制处理。
具体算法参见【参考程序3】。
【参考程序3】
programp2001_1(input,output);
constmaxn=500000;
typenum=array[1..5]oflongint;{以5位长整型来表示1个数}
vari,j,n,m,s:
longint;
f:
array[1..maxn]ofnum;
g:
num;
c:
integer;{进位值}
begin
assign(input,'count.in');reset(input);
assign(output,'count.out');rewrite(output);
readln(n);
close(input);
{以下2行求得f[1]=1,以00001表示}
f[1,1]:
=1;
forj:
=2to5dof[1,j]:
=0;
{以下2行求得f[2]=2,以00002表示}
f[2,1]:
=2;
forj:
=2to5dof[2,j]:
=0;
m:
=ndiv2div2;
s:
=2;
fori:
=1tomdo{求得m对f[2k+1]和f[2k+2]}
begin
s:
=s+1;
forj:
=1to5do{第1至第5位}
f[s,j]:
=f[s-1,j];{f[2k+1]的1至5位←f[2k+1]的1至5位}
s:
=s+1;
{以下7行实现:
f[2k+2]←f[2k]+f[k+1]}
c:
=0;{第0位向第1位的进位为0}
forj:
=1to5do{处理第j位加法}
begin{f[2k+2]的第j位←f[2k]的第j位+f[k+1]的第j位+第j-1位向j位的进位}
f[s,j]:
=f[s-2,j]+f[sdiv2,j]+c;
c:
=f[s,j]div1000000000;{第j位向下一位的进位值}
f[s,j]:
=f[s,j]mod1000000000;{当前第j位值,去除进位后的剩余}
end;
end;
g[1]:
=1;{以下2行,f[n]=1}
forj:
=2to5do
g[j]:
=0;
{以下10行,在f[n](即g)原值1基础上,加上f[1]、f[2]、…、f[ndiv2]}
fori:
=1tondiv2do{每次循环加上f[i]}
begin
c:
=0;{第0位向第1位的进位为0}
forj:
=1to5do{处理第j位加法}
begin
g[j]:
=g[j]+f[i,j]+c;{将f[i]的第j位加至f[n]上}
c:
=g[j]div1000000000;{取得第j位向下一位的进位}
g[j]:
=g[j]mod1000000000;{去除进位后的剩余值}
end;
end;
i:
=5;{以下4行,输出最高位}
whileg[i]=0do
i:
=i-1;
write(g[i]);
i:
=i-1;
while(i>0)do{输出最高位外的其余位}
begin
ifg[i]<10then{只有1位数,补8个0;其余依次类推}
write('00000000')
elseifg[i]<100then
write('0000000')
elseifg[i]<1000then
write('000000')
elseifg[i]<10000then
write('00000')
elseifg[i]<100000then
write('0000')
elseifg[i]<1000000then
write('000')
elseifg[i]<10000000then
write('00')
elseifg[i]<100000000then
write('0');
write(g[i]);
i:
=i-1;
end;
writeln;
close(output);
end.
【算法3的复杂性】
1.时间复杂性:
(1)产生m对f[2k+1]和f[2k+2]时,f[s]的计算次数为:
2*m*5=10*(ndiv2div2)≤5n/2。
(2)产生m对f[2k+1]和f[2k+2]时,s类加次数为:
2*m=2*(ndiv2div2)≤n/2。
(3)产生g(f[n])时的循环,计算5*(ndiv2)≤5n/2。
因此最多计算11n/2次。
算法3的时间复杂度为O(n)。
当n=100万时,最多计算550万次。
因此在一秒的时限内,不会超时。
2.空间复杂性:
每个长整型占4B,因此需额外空间:
50万*5*4B=1000万B≈10000KB≈10MB。
【其它解法】
本题的递归解法,参见第册
2003年提高组第3题--加分二叉树
【问题描述】
设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。
每个节点都有一个分数(均为正整数),记第i个节点的分数为di,树tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:
subtree的左子树的加分×subtree的右子树的加分+subtree的根的分数
若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。
不考虑它的空子树。
试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。
要求输出;
(1)tree的最高加分
(2)tree的前序遍历
【输入格式】
输入文件binary.in的第1行:
一个整数n(n<30),为节点个数。
第2行:
n个用空格隔开的整数,为每个节点的分数(分数<100)。
【输出格式】
输出文件binary.out的第1行:
一个整数,为最高加分(结果不会超过4,000,000,000)。
第2行:
n个用空格隔开的整数,为该树的前序遍历。
【输入样例】
5
571210
【输出样例】
145
31245
【官方测试数据】
序号
输入
输出
1
5
911
5781819
42135
2
10
839701
54891921402022
74213569810
3
15
6366794
273891921422456789
531241286710911141315
4
20
317358969
17189193142245678938456
5312416128671091114131518171920
5
25
781495238
9899574224567893345121232
84213657161210911141315201817192321222425
【分析】采用动态规划算法
以样例数据为例。
此时,有5个数依次为571210;
由节点I,I+1,…,p,…,J组成的子树,
它的根为p号节点
因为n个数组成的二叉树的中序序列为1,2,…,n依次递增排列,所以在该树中,若某子树由第i个至第j个元素组成,它的根为p,则它的左子树的节点序号均小于p,右子树的节点序号均大于p。
(如下图)
从第i个至第j个元素构成的所有二叉树中,能取得最高加分值记为f[i,j],取得此最高加分时,该树的根序号为r[i,j]。
则针对样例数据,有以下结论:
1)最高加分为f[1,5];
2)取得最高加分时的根为r[1,5];
3)所有左子树中的元素序号在1至r[1,5]-1之间;
4)所有右子树中的元素序号在r[1,5]+1至5之间;
求f[i,j]的递推公式如下:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划