# noip讲义4-递推法

var a,i,n:longint; begin read(n); a:=2; for i:=2 to n do a:=a+i; writeln(a); end.

Fn=Fn-1+2× (n-1)

5 3 2 1 4 6

Fn=Fn-1+n

1 3 6 10…

sn ? sn?1 ? n

sn ? sn ?1 ? 2 ? n ? 1(n ? 2) s2 ? 4

4

9

16

25

36…

Sn=2×sn-1+2

s n ? s n ?1 ? 3 ? 2

n ?2

Sn=3×sn-1-2×sn-2

Fn=2*Fn-1+1

var a,i,n:longint; begin read(n); a:=1; for i:=2 to n do a:=2*a+1; writeln(a); end.

Fn=Fn-1+2n-1
var f,s,i,n,j:longint; begin read(n); f:=1; for i:=2 to n do begin s:=1; for j:=1 to i-1 do s:=s*2; f:=f+s; end; writeln(f); end.

var{加入高精度运算} a,b:array[1..100] of integer; i,j,n:integer; begin readln(n); a[100]:=1 ;{n=1时} b[100]:=1;{20=1} for i:= 2 to n do begin for j:= 100 downto 1 do b[j]:=b[j]*2;{递推出2i-1} for j:= 100 downto 2 do if b[j]>=10 then begin b[j-1]:=b[j-1]+b[j] div 10 ; b[j]:=b[j] mod 10; end; for j:= 100 downto 1 do begin a[j]:=a[j]+b[j]; if a[j]>=10 then begin a[j-1]:=a[j-1]+a[j] div 10 ; a[j]:=a[j] mod 10; end; end; end; j:=1; while a[j]=0 do j:=j+1; for i:= j to 100 do write(a[i]) ; end.

4

6

10

18

34…

Fn=Fn-1+2n-1

var f,s,i,n,j:longint; begin read(n); f:=4; for i:=2 to n do begin s:=1; for j:=1 to i-1 do s:=s*2; f:=f+s; end; writeln(f); end.

var a,b:array[1..100] of longint; i,j,n:longint; begin readln(n); a[100]:=4 ; b[100]:=1; for i:= 2 to n do begin for j:= 100 downto 1 do b[j]:=b[j]*2; for j:= 100 downto 2 do if b[j]>=10 then begin b[j-1]:=b[j-1]+b[j] div 10 ; b[j]:=b[j] mod 10; end; for j:= 100 downto 1 do begin a[j]:=a[j]+b[j]; if a[j]>=10 then begin a[j-1]:=a[j-1]+a[j] div 10 ; a[j]:=a[j] mod 10; end; end; end; j:=1; while a[j]=0 do j:=j+1; for i:= j to 100 do write(a[i]) ; end.

52+42+32+22+12=55

n2+(n-1)2+(n-2)2+…+22+1

Fn=Fn-1+n2

Var {加入高精度运算} a:array[1..25] of longint; i,j,k,x,n:longint; begin readln(n); a[25]:=1;{n=1时} for i:= 2 to n do begin x:=i*i; for j:= 25 downto 1 do begin a[j]:=a[j]+x mod 10; if a[j]>=10 then begin a[j]:=a[j]-10 ; a[j-1]:=a[j-1]+1; end; x:=x div 10; end; end; j:=1; while a[j]=0 do j:=j+1; for i:= j to 25 do write(a[i]); end.

var a,i,n:longint; begin read(n); a:=1; for i:=2 to n do a:=a+6*(i-1); writeln(a); end.

var {加入高精度运算} a:array[1..50] of longint; i,j,k,x,n:longint; begin readln(n); a[50]:=1; for i:= 2 to n do begin x:=(i-1)*6; for j:= 50 downto 1 do begin x:=x+a[j]; a[j]:=x mod 10 ; x:=x div 10; end; end; j:=1; while a[j]=0 do j:=j+1; for i:= j to 50 do write(a[i]); end.

Fn=7*Fn-1
F0=10

( Fn为第n次扩展后整个三角形的面积 )

Sn=Fn-Fn-1

const max=100; var f1,f2,s:array[1..max] of longint; i,j,k,l,n:longint; begin readln(n); f1[max]:=0 ; f1[max-1]:=1; {F0=10} for i:= 1 to n do begin f2:=f1; k:=0; { ×7 } for j:= max downto 1 do begin k:=k+f1[j]*7; f1[j]:=k mod 10; k:=k div 10; end; end;

for i:= max downto 1 do {相减}
begin if f1[i]<f2[i] then begin f1[i]:=f1[i]+10; f1[i-1]:=f1[i-1]-1; end;

s[i]:=f1[i]-f2[i];
end; j:=1; while s[j]=0 do j:=j+1; for i:= j to max do write(s[i]) ; end.

Hanoi双塔问题

1
【样例2】 hanoi.in 2

2

hanoi.out 6

【限制】 对于50%的数据，1<=n<=25 对于100%的数据，1<=n<=200 【提示】 设法建立An与An-1的递推关系式。

2 6 14 30 62 126 254…

var a:array[1..62]of integer;{存放大数} i,j,n:integer; f:boolean; begin assign(input,'hanoi.in'); assign(output,'hanoi.out'); reset(input); rewrite(output); readln(n);{层数} for i:=1 to 62 do a[i]:=0;{初值} for i:=1 to n do {递推n次} begin for j:=1 to 62 do a[j]:=a[j]*2; {先乘2} a[1]:=a[1]+2; {再在个位上加2} for j:=1 to 62 do if a[j]>9 then begin {处理进位} a[j+1]:=a[j+1]+1; a[j]:=a[j] mod 10; end; end; f:=false; for i:=62 downto 1 do begin if a[i]<>0 then f:=true; if f then write(a[i]); end; close(input); close(output); end.

...
1 1 2 3 5

466 若按此规律继续作矩形，则序号为⑩的矩形周长是＿＿＿。

【问题描述】 一只蜜蜂在上图所示的数字蜂房上爬动,已知它只 能从标号小的蜂房爬到标号大的相邻蜂房,现在问你： 蜜蜂从蜂房M开始爬到蜂房N（M<N），有多少种爬 行路线？ 【输入格式】 输入M，N的值。(1<=M,N<=1000) 【输出格式】 爬行有多少种路线。 【输入样例】bee.in 1 14 【输出样例】bee.out 377

var m,n,i,j,x:longint; a:array[1..1000,1..64] of integer; begin readln(m,n); a[m+1,64]:=1; a[m+2,64]:=2; for i:= m+3 to n do begin x:=0; for j:= 64 downto 1 do begin x:=x+a[i-2,j]+a[i-1,j]; a[i,j]:= x mod 10; x:=x div 10; end; end; j:=1; while a[n,j]=0 do j:=j+1; for i:= j to 64 do write(a[n,i]); writeln; end.

Ⅱ．首位是１，第二位只能为２或３，共有２g(ｎ－２)个，

F(n)=F(n-2)+F(n-1) (n>=3)

ｎ个格子依次编号后，格１与格（n-1）不相邻。

a3 ? 2, a4 ? 9 a5 ? 44

Var i,j,k,m,n:longint; a:array[1..10] of longint; function jc(k:integer):longint;{求K!} var i,j:longint; begin j:=1; for i:= 2 to k do j:=j*i; jc:=j; end; begin readln(n,m);{n是顶点数，m是颜色数}

3 a[3]:=jc(m) div jc(m-3);{初值 a[3] ? Am ? a[3]:=m*(m-1)*(m-2) } (m ? 3)! for i:= 4 to n do begin j:=1; for k:= 1 to i-1 do j:=j*(m-1); { (m ? 1)i ?1 } a[i]:=m*j-a[i-1] ; {递推公式} end; writeln(a[n]); end.

m!

an ? 3 ? 2n?1 ? an?1

3 a3 ? A3 ? 6

a3 ? A ? 6
3 3
4

a4 ? 3 ? 2 ? a3 ? 18
3

a5 ? 3? 2 ? a4 ? 48?18 ? 30

4×30=120

60

4个人进行篮球训练，互相传球接球，要求每个人接球 后马上传给别人，开始由甲发球，并作为第一次传球，第 五次传球后，球又回到甲手中，问有多少种传球方式？

a5=3×3×3×3-21=60。

var a:array[1..100] of longint; n,m,i,j:longint; begin readln(n,m); a[1]:=0; j:=1; for i:= 2 to m do begin j:=j*(n-1); {先求出(n-1)i-1} a[i]:=j-a[i-1]; end; writeln(a[m]); end.

var {加入高精度运算} a:array[1..100,1..100] of integer; s:array[1..100] of integer;

for j:= 100 downto 1 do
a[i,j]:=s[j]-a[i-1,j]; for j:= 100 downto 1 do

i,j,t,k,n,m:longint;
begin readln(n,m); a[1,100]:=0 ; s[100]:=1; for i:= 2 to m do begin for j:= 100 downto 1 do

if a[i,j]<0 then
begin a[i,j-1]:=a[i,j-1]-1; a[i,j]:=a[i,j]+10; end; end; j:=1; while a[m,j]=0 do j:=j+1; for i:= j to 100 do write(a[m,i]); end.

s[j]:=s[j]*(n-1);
for j:= 100 downto 1 do if s[j]>9 then

begin
s[j-1]:=s[j-1]+s[j] div 10; s[j]:= s[j] mod 10; end;

Pn Pn-1

P1 P2 P3 Pk

Pn-2

Ck ? Cn?k ?1 种。而k可以选2到n-1，所以根据加法原理，得出总

Cn ? ? Ck ? Cn?k ?1
k ?2

n ?1

const max=21; var c:array[2..max] of longint; n,i,k:integer; total:longint; begin readln(n); c[2]:=1; for i:=3 to n do begin c[i]:=0; for k:=2 to i-1 do c[i]:=c[i]+c[k]*c[i-k+1]; end; writeln(c[n]); end.

5 4
３ ２ １

15 10
６ ３ １

35 70 20 35
10 ４ １ 15 ５ １

126

210

330

495 Ｂ

56
21 ６ １

84
28 ７ １

120 165

36 ８ １

45 ９ １

var i,j,n,m:integer; a:array[1..20,1..20] of longint; begin read(n,m); fillchar(a,sizeof(a),0); for i:=1 to n do a[I,1]:=1; for j:=1 to m do a[1,j]:=1; for i:=2 to n do for j:=2 to m do a[I,j]:=a[I,j-1]+a[i-1,j]; writeln(a[n,m]); end.

var n,m,i,j,x1,x2,y1,y2:integer; a:array[1..50,1..50] of longint; b:array[1..50,1..50] of boolean; begin readln(n,m);{行列要分清} readln(x1,y1,x2,y2); fillchar(a,sizeof(a),0) ; fillchar(b,sizeof(b),true); for i:=y1 to y2 do for j:=x1 to x2 do b[i,j]:=false; for i:=1 to m do 有可能障碍区域靠边 begin if not(b[i,1]) then break ; a[i,1]:=1; 如输入 end; for j:=1 to n do 9 5 begin if not(b[1,j]) then break ; a[1,j]:=1; 1 2 8 4 end; 应输出 for i:=2 to m do for j:=2 to n do if b[i,j] then a[i,j]:=a[i-1,j]+a[i,j-1]; 1 write(a[m,n]); end.

Var{加入高精度运算} n,m,i,j,x1,x2,y1,y2,k,g:integer; a:array[1..50,1..50,1..30] of longint; b:array[1..50,1..50] of boolean; begin readln(n,m); readln(x1,y1,x2,y2); fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),true); for i:=y1 to y2 do for j:=x1 to x2 do b[i,j]:=false; for i:=1 to m do begin if not(b[i,1]) then break; a[i,1,1]:=1; end; for j:=1 to n do begin if not(b[1,j]) then break; a[1,j,1]:=1; end;

for i:=2 to m do for j:=2 to n do if b[i,j] then begin g:=0; for k:=1 to 30 do begin
a[i,j,k]:=a[i-1,j,k]+a[i,j-1,k]+g;

g:=a[i,j,k] div 10; a[i,j,k]:=a[i,j,k] mod 10; end; end; j:=30; for i:=30 downto 1 do if a[m,n,i]=0 then j:=j-1; for i:=j downto 1 do write(a[m,n,i]); end.

const (-2,1) (-2,-1) x1:array[1..8]of integer=(2,2,1,-1,-2,-2,-1,1); y1:array[1..8]of integer=(1,-1,-2,-2,-1,1,2,2); (-1,-2) (-1,2) var b:array[0..20,0..20] of boolean; i,j,x,y,k,p,n,m:integer; (1,-2) (1,2) a:array[0..20,0..20] of integer; begin (2,-1) (2,1) readln(n,m,x,y); fillchar(b,sizeof(b),true); fillchar(a,sizeof(a),0); b[x,y]:=false; for i:=1 to 8 do if (x+x1[i]>=0)and(x+x1[i]<=n)and(y+y1[i]>=0)and(y+y1[i]<=m) then b[x+x1[i],y+y1[i]]:=false; for i:=0 to n do begin if not(b[i,0]) then break; for i:=1 to n do a[i,0]:=1; for j:=1 to m do end; if b[i,j] then for i:=0 to m do begin a[i,j]:=a[i-1,j]+a[i,j-1]; if not(b[0,i]) then break; 有些控制点有 write(a[n,m]); a[0,i]:=1; end. end; 可能在边上

const{加入高精度运算} L=30; x1:array[1..8]of integer=(2,2,1,-1,-2,-2,-1,1); y1:array[1..8]of integer=(1,-1,-2,-2,-1,1,2,2); var b:array[0..20,0..20] of boolean; i,j,x,y,k,p,n,m:integer; a:array[0..20,0..20,1..L] of integer; begin readln(n,m,x,y); fillchar(b,sizeof(b),true); fillchar(a,sizeof(a),0); b[x,y]:=false; for i:=1 to 8 do if (x+x1[i]>=0)and(x+x1[i]<=n)and(y+y1[i]>=0)and(y+y1[i]<=m) then b[x+x1[i],y+y1[i]]:=false; for i:=0 to n do begin if not(b[i,0]) then break; a[i,0,1]:=1; end; for i:=0 to m do begin if not(b[0,i]) then break; a[0,i,1]:=1; end;

for i:=1 to n do for j:=1 to m do if b[i,j] then begin k:=0; for p:=1 to L do begin a[i,j,p]:=a[i-1,j,p]+a[i,j-1,p]+k; k:=a[i,j,p] div 10; a[i,j,p]:=a[i,j,p] mod 10; end; end; j:=L; while (a[n,m,j]=0) and(j>1) do j:=j-1; for i:=j downto 1 do write(a[n,m,i]); end.

【问题描述】 上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次， 老师带着同学们一起做传球游戏。游戏规则是这样的：n个同学站成一个 圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每 个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老 师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是 败者，要给大家表演一个节目。 聪明的小蛮提出了一个有趣的问题：有多少种不同的传球方法可以 使得从小蛮手里开始传的球，传了m次后，又回到小蛮手里。两种传球 方法被视为不同的方法，当且仅当这两种方法中，接到球的同学按接球 顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设小蛮 为一号，球传了3次后回到小蛮手里的方式有 1-> 2-> 3-> 1 和 1-> 3-> 2-> 1 ，共2种。

【输入】 输入文件ball.in共一行，有两个用空格隔开的整数n，m （3<=n<=30，1<=m<=30）。 【输出】 输出文件ball.out共一行，有一个整数，表示符合题意的 方法数。 【输入输出样例】 ball.in 3 ball.out 32 【限制】 40%的数据满足：3<=n<=30，1<=m<=20 100%的数据满足：3<=n<=30，1<=m<=30

var i,j,k,n,m:longint; f:array[0..30,0..30] of longint; begin readln(n,m); fillchar(f,sizeof(f),0); f[1,0]:=1; for k:=1 to m do begin f[1,k]:=f[2,k-1]+f[n,k-1]; {当球在1号同学时} for i:= 2 to n-1 do f[i,k]:=f[i-1,k-1]+f[i+1,k-1]; f[n,k]:=f[n-1,k-1]+f[1,k-1]; {当球在n号同学时} end; write(f[1,m]); end.

4个人进行篮球训练，互相传球接球，要求每个人接球 后马上传给别人，开始由甲发球，并作为第一次传球，第 五次传球后，球又回到甲手中，问有多少种传球方式？

Var n,m,i,j,k,l,g:longint; a:array[0..30,1..30,1..100] of longint;

begin
read(n,m); a[0,1,1]:=1; for i:=1 to m do

begin
for j:=1 to n do for k:=1 to n do if j<>k then begin g:=0; for l:=1 to 100 do begin g:=a[i,j,l]+a[i-1,k,l]+g; a[i,j,l]:=g mod 10 ; g:=g div 10;

end;
end; end; l:=100; while a[m,1,l]=0 do l:=l-1; for i:=l downto 1 do write(a[m,1,i]); end.

4=1+1+1+1； 4=1+1+2； 4=2+2； 4=1+3；

? ?

? ?

? f ?i, j ? ? g ?i ? j , j ? ? j ? ? g ?i, j ? ? ? f ?i, k ? k ?1 ?

j k ?1

g ?i, j ? ? ? f ?i, k ? ? ? f (i, k ) ? f (i, j ) ? g ?i, j ? 1? ? g ?i ? j, j ?
k ?1

j ?1

g 当i<j时，根据 g ?i, j ? 的含义， i ? j, j 无意义。 当j=1时，对i做任意剖分、其中最大的一份不大于1的方案只有一种。即： i=1+1+1+…+1（共i个1）;所以： g ?i ,1? =1

?

?

g ?i, j ? =

?g ?i, j ? 1?, (i ? j ) ? ?g ?i, j ? 1? ? g (i ? j, j ), (i ?? j )

g ?i,1? =1{初始条件}

? ?

? ?

var g:array[0..100,0..100] of longint; n,i,j:integer; begin readln(n); fillchar(g,sizeof(g),0); for j:=0 to n do g[j,1]:=1;{初始条件} for i:=0 to n do for j:=2 to n do if i>=j then g[i,j]:=g[i-j,j]+g[i,j-1] else g[i,j]:=g[i,j-1]; writeln( g[n,n-1] ); end.

４ ３ ２ １ 开始

Ａ １６ ８ ４ ２ ３３

Ｂ １６ ８ ４ ３４ １７

Ｃ １６ ８ ３６ １８ ９

Ｄ １６ ４０ ２０ １０ ５

(1,2,3,4)；而每种移动方法用偏移值来表示，并将这些偏移值分别保存

K
1 2 3 4

Dx[k]
2 2 1 1

Dy[k]
1 -1 2 -2

-1,-1 4,4 4,4 2,3

const if a[1,1].x=0 then writeln('no') dx:array[1..4]of integer=(2,2,1,1); else begin{存在路径} dy:array[1..4]of integer=(1,-1,2,-2); type i:=1;j:=1; map=record write('(',i,',',j,')'); x,y:integer; while a[i,j].x<>-1 do end; begin var i,j,n,m,k:integer; k:=i; a:array[0..50,0..50] of map; i:=a[i,j].x ; j:=a[k,j].y; begin write('->(',i,',',j,')'); read(n,m); end; fillchar(a,sizeof(a),0); a[n,m].x:=-1 ; a[n,m].y:=-1;{标记为终点} end; for i:=n downto 2 do {倒推} end. for j:=m downto 1 do if a[i,j].x<>0 then for k:=1 to 4 do begin a[i-dx[k],j-dy[k]].x:=i; a[i-dx[k],j-dy[k]].y:=j; end;

const maxn=100; var a，n，m，x ，k，i：integer； p，down，up：array[1..maxn] of integer； begin readln(a，n，m，x)； fillchar(p，sizeof(p)，0)； up[1]:=a；down[1] :=0；p[1] :=a； k:=1; repeat up[2]:=k；down[2]:=k；p[2]:=p[1]；{枚举第2站的上车人数、下车人数和车上人数} for i:=3 to n-1 do begin {递推第3站…第n-1站的车上人数} up[i] :=up[i-1]+up[i-2]； down[i] :=up[i-1]； p[i] :=p[i-1]+up[i-2]； end； if p[n-1]=m then {若n站下车的人数为m，则输出从x站开出时车上的人数，并退出} begin writeln(p[x])； exit； end； k:=k+1；{第2站上车人数增加1} until p[n-1]>m；{直至无法满足此规律为止} end.

noip算法总结2016
noip算法总结2016 算法总结一、 动态规划和递推 dp...利用贪心来确定状态 、 分治分而治之的思想在...凸包的常用求法是 graham 扫描法,先把点按横坐标...
NOIP名校讲义
NOIP名校讲义_学科竞赛_高中教育_教育专区。NOIP学习...数组存储二进制数的各个数位是一种比较好的方 法...其他位置上的数可利用其上一行的数递推出来,其值...
noip分区联赛1

NOIP2002普及组解题报告
<=10000,因此,为 了加快速度,我们可以用筛选法将 ...[参考程序 参考程序] 参考程序 NOIpC3.pas 题四:...(i, j)有无障碍,递推方程如下: F[0,0] F[...
noip完整考纲

NOIP问题求解集合