当前位置:首页 >> IT/计算机 >>

noip讲义4-递推法


递推法
所谓递推,是指从已知的初始条件出发,依据某种递推 关系,逐次推出所要求的各中间结果及最后结果。其中初始 条件或是问题本身已经给定,或是通过对问题的分析与化简 后确定。 可用递推算法求解的题目一般有以下二个特点: 1、问题可以划分成多个状态; 2、除初始状态外,其它各个状态都可以用固定的递推关 系式来表示。 在我们实际解题中,题目不会直接给出递推关系式,而 是需要通过分析各种状态,找出递推关系式。

采用具体化、特殊化的方法寻找规律
平面上n条直线,任两条不平行,任三条不共点,问 这n条直线把这平面划分为多少个部分?

设这n条直线把这平面划分成Fn个部分。 先用具体化特殊化的方法寻找规律,如图所示,易知 的前几项分别为

这些数字之间的规律性不很明显, 较难用不完全归纳法 猜出Fn的一般表达式。但我们可以分析前后项之间的递推关系, 因为这些图形中,后一个都是由前一个添加一条直线而得到的, 添加一条直线便增加若干个区域。

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

一般地,设原来的符合题意的n-1条直线把这平面分成 个区域,再增加一条直线l,就变成n条直线,按题设条 件,这l必须与原有的n-1条直线各有一个交点, 且这n-1个交点 及原有的交点互不重合。这n-1个交点把l划分成n个区间,每 个区间把所在的原来区域一分为二,所以就相应比原来另增 了n个区域,即:
这样,我们就找到了一个从Fn-1到Fn的的递推式,再加上 已知的初始值F1=2,就可以通过n-1步可重复的简单运算推导 出Fn的值。

在平面内画五条直线和一个圆,最多能把平面分成 多少部分?

Fn=Fn-1+2× (n-1)
平面上有8个圆,最多能把平面分成几部分?

5 3 2 1 4 6

圆周上两个点将圆周分为两半,在这两点上写上数1; 然后将两段半圆弧对分,在两个分点上写上相邻两点上的 数之和;再把4段圆弧等分,在分点上写上相邻两点上的数 之和,如此继续下去,问第6步后,圆周上所有点上的数之 和是多少?

分析:先可以采用作图尝试寻找规律。
第一步:圆周上有两个点,两个数的和是1+1=2; 第二步:圆周上有四个点,四个数的和是1+1+2+2=6;增加数之和恰好是第一 步圆周上所有数之和的2倍。 第三步:圆周上有八个点,八个数的和是1+1+2+2+3+3+3+3=18,增加数之和恰 好是第二步数圆周上所有数之和的2倍。 第四步:圆周上有十六个点,十六个数的和1+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5=54, 增加数之和恰好是第三步数圆周上所有数之和的2倍。 ?? 这样我们可以知道,圆周上所有数之和是前一步圆周上所有数之和的3倍。 设An为第n步后得出的圆周上所有数之和,则An=3×An-1

Fn=Fn-1+n
在 n×n的正方形钉子板上(n是钉子板每边上的 钉子数),求连接任意两个钉子所得到的不同长度的 线段种数.

如图1,是棱长为a的小正方体,图2,图3由这样的小正 方体摆放而成。按照这样的方法继续摆放,自上而下分别叫 第一层、第二层、……、第n层,第n层的小正方体的个数记 为sn。请写出求sn的递推公式。

1 3 6 10…

sn ? sn?1 ? n

sn ? sn ?1 ? 2 ? n ? 1(n ? 2) s2 ? 4
如图,有边长为1的等边三角形卡片若干张,使用这些 三角形卡片拼出边长分别是2,3,4,…的等边三角形(如 图所示).根据图形推断,写出求每个等边三角形所用卡 片总数sn的递推公式.

4

9

16

25

36…

Sn=2×sn-1+2
为庆祝“五· 一”国际劳动节,市政府决定在人民广场上增 设一排灯花,其设计由以下图形逐步演变而成,其中圆圈代表 灯花中的灯泡,n代表第n次演变过程,s代表第n次演变后的灯 94 泡的个数。仔细观察下列演变过程,当n=6时,s=_____。

s n ? s n ?1 ? 3 ? 2

n ?2

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

从表中可以看出车上人数最多是56人,所以车上 至少要准备56个座位。 某公共汽车线路上共有15个车站(包括起点站和终点 站)。在每个站上车的人中,恰好在以后各站下去一个。要 使行驶过程中每位乘客都有座位,车上至少要备有多少个座 位?

练习1
将一张长方形的纸对折,可得到一条折痕,继续对 折,对折时每次折痕与上次的折痕保持平行,连续对折 三次后,可得到7条折痕,那么对折n次,可得到几条 折痕?

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.

练习2
如图,第一次把三角形剪去一个角后,图中最多有四个 角,第二次再把新产生的角各剪一刀,…,如此下去,每一次 都是把新产生的角各剪一刀,则第n次剪好后,图中最多有 多少个角?

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

练习3

Fn=Fn-1+n2

下图中把大正方形各边平均分成了5份,此时有55个正 方形。如果把正方形各边平均分成n份,那么得到的正方形 总数为多少? var a,i,n:longint; begin read(n); a:=1; for i:=2 to n do a:=a+i*i; writeln(a); end.

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.

练习4

可得递推公式: Fn= Fn-1+6*(n-1)

如图,由等圆组成的一组图中,第1个图由1个圆组成, 第2个图由7个圆组成,第3个图由19个圆组成,……,按照 217 这样的规律排列下去,则第9个图形由__________个圆组成。

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次扩展后整个三角形的面积 )

练习5

Sn=Fn-Fn-1

已知三角形ABC的面积为10,延长边BC到点D,使BC=CD, 延长边CA到点E,使CA=AE,延长边AB到点F,使AB=BF,连 结DE,EF,FD,得到三角形DEF,并记图中阴影部分面积为S1,此时我 们称三角形ABC向外扩展了一次.求经过N次扩展后图中阴影部分 的面积Sn.

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双塔问题
给定A、B、C三根足够长的细柱,在A柱上放有2n个中 间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同 的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情 形)。现要将这些圆盘移到C柱上,在移动过程中可放在B柱 上暂存。要求: (1)每次只能移动一个圆盘; (2)A、B、C三根细柱上的圆盘都要保持上小下大的顺 序; 任务:设An为2n个圆盘完成上述任务所需的最少移动次 数,对于输入的n,输出An。

输入文件hanoi.in为一个正整数n,表示在A柱上放有2n 个圆盘。 输出文件hanoi.out仅一行,包含一个正整数,为完成上 述任务所需的最少移动次数An。 【样例1】 hanoi.in hanoi.out

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…

还可以: An=An-1+2n
解题思路: 递推+高精度 1. 假设当前要移动A轴的N层,即2N个盘子,则需 要将N-1层的2N-2个盘子移动到B轴(辅助轴)上, 再将第N层的2个盘子移动到C轴上(目标轴),然 后再将那N-1层的2N-2个盘子移动到目标轴,共 需要2*An-1+2次。 2. 递推关系式是: An=2*An-1+2 A0=0

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,8,13,…,其中从第三个数 起,每一个数都等于它前面两上数的和。现以这组数中的各个 数作为正方形的边长构造如下正方形:

...
1 1 2 3 5

再分别依次从左到右取2个、3个、4个、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.

通过合理分步、恰当分类找出递推关系

登楼梯
欲登上第10级楼梯,如果规定每步只能跨上一级或 两级,则不同的走法共有( 89种 )

以某位置划分求递推式

若用1或2两数字写n位数,其中任意相邻两个位置 不全为1。记n位数的个数为f(n),则f(8)= ; 用1、2、3三个数字写n位数,要求数中不出现紧 挨着的两个1 。记n位数的个数为g(n),则g(8)= 。 符合条件的n位数可分为两类: Ⅰ.首位是2,则以下n-1位数符合条件的个数为f(n-1); Ⅱ.首位是1,则第二位应是2,以下n-2位的个数为f(n-2). 于是,f(n)=f(n-1)+f(n-2). 故f(n)为斐波那契数列. ∵f(1)=2,f(2)=3 ∴f(8)=55.

设符合条件的n位数共有g(n)种,按首位划分可分成: Ⅰ.首位是2或3,则以下n-1位各有g(n-1)个,共2 g(n-1)个;

Ⅱ.首位是1,第二位只能为2或3,共有2g(n-2)个,
故g(n)=2g(n-1)+2g(n-2)个. 由初始条件g(1) =3; g(2) =8;求得g(8)=3344.

有2×n的一个长方形方格,用一个1×2的骨牌铺满方格。 例如n=3时,为2×3方格。 此时用一个1×2的骨牌铺满方格,共有如下3种铺法:

试对给出的任意一个n(n>0),求出铺法总数的递推公 式。 F(1)=1 F(2)=2
F(n)=F(n-2)+F(n-1) (n>=3)

如果有n元钱,每天去购买下列三种商品之一:蔬菜要 用1元钱,猪肉要用2元钱,鸡蛋要用2元钱.用An表示把 这n元钱用完的所有可能的用法的总数. 如果第一天买蔬菜,则用去1元钱,还剩n-1 元钱, 这n-1元钱的用法有An-1种; 如果第一天买猪肉,则用去2元钱,还剩n-2 元钱, 这n-2元钱的用法有An-2种;

如果第一天买鸡蛋,则用去2元钱,还剩n-2 元钱, 这n-2元钱的用法有An-2种;
所以,An=An-1+2An-2

按前n-1格首尾关系讨论
有排成一行的n个方格,用红、黄、蓝三色涂每个格子, 每格涂一色,要求任何相邻的格不同色,且首尾两格也不同 色。问有多少种涂法?
解:设共有an种涂法,易见a1=3,a2=6,a3=6,且当n≥4时,将

n个格子依次编号后,格1与格(n-1)不相邻。
情形1:格(n-1)涂色与格1不同,此时格n只有一色可涂,且前(n-1) 格满足首尾两格不同色,故有an-1种涂色方法。

情形2:格(n-1)涂色与格1相同,此时格(n-2)与格1涂色必然不同,
不然,格(n-1)与(n-2)相同,于是前(n-2)格有an-2种涂色法。因为格 n与格1不同色,有两种涂色法,故共有2an-2种涂色法。 综上,可得an=an-1+2an-2(n≥4)

错位排列
五个人排成一列,重新站队时,各人都不站在原来的位置上,那么不同的 站队方式共有( ) (A)60种 (B)44种 (C)36种 (D)24种 解:首先我们把人数推广到n个人,即n个人排成一列,重新站队时,各人都不 站在原来的位置上。设满足这样的站队方式有An种,现在我们通过合理分步,恰当 分类来找出递推关系: 第一步:第一个人不站在原来的第一个位置,有n-1种站法。 第二步:假设第一个人站在第2个位置,则第二个人的站法又可以分为两类: 第一类,第二个人恰好站在第一个位置,则余下的 n-2个人有An-2种站队方式;第二 类,第二个人不站在第一个位置,则就是第二个人不站在第一个位置,第三个人不 站在第三个位置,第四个人不站在第四个位置,……,第n个人不站在第n个位置, 所以有An-1种站队方式。 {a } 由分步计数原理和分类计数原理,我们便得到了数列 n 的递推关系式: an ? (n ? 1)(an?2 ? an?1 ) ,显然 a1 ? 0, a2 ? 1 ,再由递推关系有,

a3 ? 2, a4 ? 9 a5 ? 44

在书架上放有编号为1 ,2 ,…,n的n本书。现将 n本书全部取下然后再放回去,当放回去时要求每本书 都不能放在原来的位置上。 例如:n = 3时: 原来位置为:1 2 3 放回去时只能为:3 1 2 或 2 3 1 这两种 问题:求当n = 5时满足以上条件的放法共有多少 种?

染色问题
用4种不同颜色涂四边形的4个顶点,要求每点染一种颜 色,相邻的顶点染不同的颜色,则不同的染色方法有( A ) (A)84种 (B)72种 (C)48种 (D)24种

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!

如图,一个地区分为5个行政区域,现给地图着色,要求 相邻区域不得使用同一颜色,现有四种颜色可供选择,则 不同的着色方法共有 种。

图中2、3、4、5四个区域围成一个四边形,因此可以 把它们看成是一个四边形的4个顶点,而区域1就是这个四 边形对角线的交点。 第一步,先涂区域1,有4种涂法。 第二步,由于区域1跟其余四个区域都相邻,因此涂1 的颜色不能用来涂其余的四个区域,因此第二步相当于用 3种颜色来涂一个四边形的四个顶点,不难得出

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

3 a3 ? A3 ? 6

所以, a4 ? 3 ? 23 ? a3 ? 18
由分步计数原理,得出共有 4 ? 18 ? 72 种涂法。

a3 ? A ? 6
3 3
4

a4 ? 3 ? 2 ? a3 ? 18
3

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

4×30=120

某城市在中心广场建造一个花圃,花圃分成6个部分(如
图),现要栽种4种不同颜色的花,每部分栽种一种且相邻部 分不能栽种同样颜色的花,不同的栽种方法共有 120 种。

传球问题

60

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

分析 :设第n次传球后,球又回到甲手中的传球方式有an种。可以想象前n-1次传球,如 果每一次传球都任选其他三人中的一人进行接球,则每次传球都有3种可能,由乘法原 理,共有 3×3×……×3=3 n-1 种传球方法。这些传球方式可以分为两类: 一类是第n-1次恰好传到甲手中,这有an-1种传法,它们不符合要求,因为这样第n 次无法再把球传给甲; 另一类是第n-1次传球,球不在甲手中,第n次持球人再将球传给甲,有an种传法。

根据加法原理,有an-1+an=3 n-1 。
由于甲是发球者,一次传球后球又回到甲手中的传球方式是不存在的,所以a1=0。 利用递推关系可以得到 a2=3-0=3, a3=3×3-3=6, a4=3×3×3-6=21,

a5=3×3×3×3-21=60。
这说明经过5次传球后,球仍回到甲手中的传球方法有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;

凸多边形划分
在一个凸多边形中,通过若干条互不相交的对角线,把这 个凸多边形剖分成了若干个三角形。现在的任务是根据输入的 凸多边形的边数,求不同剖分的方案数Cn。比如当n=5时,有 如下5种不同的方案,所以C5=5。 输入文件14.in:一个正整数,表示凸多边形的边数。(n<=21) 输出文件14.out:一个正整数,表示方案总数。

Pn Pn-1

P1 P2 P3 Pk

Pn-2

如图所示,我们以p1pn这条边为基准边,再找pk来构成三角形, 则原凸n边形被剖解成了△p1pkpn和两个凸多边形,其中一个是 由p1,p2,…,pk构成的凸k边形,另一个是由pk,pk+1,…,pn构成的凸 n-k+1边形,根据乘法原理,选择pk这个顶点的分解方案为

Ck ? Cn?k ?1 种。而k可以选2到n-1,所以根据加法原理,得出总
的方案数为

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

n ?1

注意,就这个递推关系而言,临界值应为C2=1,而不是 C3=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.

求路径总数
下图是某居民小区道路图,小明每天由家(A点)到学校(B点), 他只沿道路向上或向右行走,那么他最多有( 495 )天走不同线路?




5 4
3 2 1

15 10
6 3 1

35 70 20 35
10 4 1 15 5 1

126

210

330

495 B

56
21 6 1

84
28 7 1

120 165





36 8 1

45 9 1

要想到达坐标为(i,j)的顶点的话,必定 要经过坐标为(i-1,j)的顶点或坐标为 (i,j-1)的顶点,设a(I,j)表示从点A到顶点 (I,j)的路径总条数,则a(I,j)=a(I,j-1)+a(i-1,j)

输入:5 9
输出:495

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.

街道路径

设有一个N*M(1<=N<=50,1<=M<=50)的街 由于在街上只能向东或北方向行走,因此要想达到坐标 道,规定行人从A(1,1)出发,在街道上只能向东或北行走。 为(i,j)的顶点的话,必定要经过坐标为(i-1,j)的顶点 若在此街道中,设置一个矩形障碍区域(包括围住该 或坐标为(i,j-1)的顶点,假设从起始顶点到达坐标为 区域的的街道)不让行人通行,如上图中用“*”表示的 (i,j)的顶点的路径总数为a[i,j],则a[i,j]= a[i-1,j] 部分。此矩形障碍区域用2对顶点坐标给出,如上图中的2 +a[i,j-1]。因此我们可以采用逐行递推的方法来求出从起 对顶点坐标为(2,2),(8,4),此时从A出发到达B的路径 始顶点到达任意一个顶点的路径总数。 有两条。 现给出N、M,同时再给出此街道中的矩形障碍区域的 2对顶点坐标(x1,y1),(x2,y2),请求出此时所有从A出 发到达B的路径的条数。

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.

过河卒
如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向 下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点), 该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点(图中的P1,P2 ? P8 和 C)。卒不能通过对方 马的控制点。棋盘用坐标表示,A 点(0,0)、B 点(n,m)( n,m为不超过 20的整数),同样马的位置坐标是需要给出的(约定: C<>A,同时C<>B)。 现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 分析:要到达棋盘上的一个点,只能从左边过来或是从上面 输入文件5.in,只有一行,共4个正整数,前2个数表示B点的坐标,后2 下来,所以根据加法原理,到达某一点的路径数目,等于 个数表示对方马的坐标。 到达其相邻上、左两点的路径数目之和,因此我们可以使 输出文件5.out,只有一行,一个整数(表示路径的条数)。 样例: 用逐行递推的方法来求出从起始顶点到终点的路径数目, 输入 6 6 3 2 如果有障碍,只要将到达该点的路径数目设置为0即可。 输出 17

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

分析: 设f(i,k)表示经过k次传球到编号为i的人手中的方案数。可 以发现,传到i号同学的球只能来自于i的左边一个同学或者右 边一个同学,这两个同学的编号分别是i-1、i+1,所以可以得 到以下的递推公式: f(i,k)=f(i-1,k-1)+f(i+1,k-1) 当i=1或n时,需单独处理: 1. f(1,k)=f(2,k-1)+f(n,k-1) 2. f(n,k)=f(n-1,k-1)+f(1,k-1) 从1号同学开始传球,可确定初始条件:f(1,0)=1 可根据传球次数进行递推,结果在f(1,m)中。

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.

整数划分
把一个正整数N划分成一些正整数的和,例如: N =n1+n2+…+nk 且满足1<=n1<=n2<=…<=nk <= N , 叫做N的一个划分。求不同的划分的数量。 当n=4时,划分数为4。 4=1+1+1+1; 4=1+1+2; 4=1+3; 4=2+2;

4=1+1+1+1; 4=1+1+2; 4=2+2; 4=1+3;
设 f i, j 表示把正整数a做分划、其中最大的一份恰好是b的方案总数。 设 g i, j 表示把正整数a做分划、其中最大的一份不大于b的方案总数。 显然有:

? ?

? ?

? 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{初始条件}
我们可以按照i、j递增的顺序来计算 g i, j 的值,这 样在计算 g i, j 的时候, ?i, j ?1? 和 g ?i ? j, j ? 都已 g 经得到,故我们只用进行一次简单的加法运算即可. 最后的g(n,n-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.

倒推法
我们把由已知初始值为F1,通过递推关 系式Fn=g(Fn-1)求出其最终结果Fn的递推方式 称为顺推法.同理,把已知最终结果为Fn,通 过递推关系式Fn-1=g(Fn),求出其初始值F1的 递推方式称之为倒推法。

四个人做火柴游戏,每一局三个人赢,一个人输,输者要按 赢者手中赢得火柴根数赔偿,即赢者手中有多少根火柴,输者就 赔他多少?4次之后,每人恰好输过一次而且手中都恰好有16根? 求四人原有火柴数? 把第一局输的人记为A,把第二局输的人记为B,把第三 局输的人记为C,把第四局输的人记为D,用倒退法可知:

4 3 2 1 开始

A 16 8 4 2 33

B 16 8 4 34 17

C 16 8 36 18 9

D 16 40 20 10 5

骑士游历
设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如上图,在棋盘上左下角

有一个中国象棋马。
马走的规则为:1.马走日字 2.马只能向右走,即如下图所示:

任务: 当n、m 输入之后,找出一条从左下角到右上角的路径。 例如: n=4,m=4时,输出路径时格式如下:(1,1)->(2,3)->(4,4)。若不存 在路径,则输出‘no’。

算法分析:我们先将棋盘的横坐标规定为i,纵坐标规定为j,对于一个 n×m的棋盘,i的值从1到n,j的值从1到m。棋盘上的任意点都可以用 坐标(i,j)表示。对于马的移动方法,我们用K来表示四种移动方向

(1,2,3,4);而每种移动方法用偏移值来表示,并将这些偏移值分别保存
在数组dx和dy中,如下表 :
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

根据马走的规则,马可以由(i-dx[k],j-dy[k])走到(i,j)。只要马能从 (1,1)走到(i-dx[k],j-dy[k]),就一定能走到(i,j),马走的坐标必须保 证在棋盘上。我们以(n,m)为起点向左递推,当递推到(i-dx[k],j-dy[k]) 的位置是(1,1)时,就找到了一条从(1,1)到(n,m)的路径。 我们用一个二维数组a表示棋盘,采用倒推法,从终点(n,m)往左递推, 设初始值a[n,m]为(-1,-1),如果从(i,j)一步能走到(n,m),就将(n,m)存放 在a[i,j]中。如下表,a[3,2]和a[2,3]的值是(4,4),表示从这两个点都可 以到达坐标(4,4)。从(1,1)可到达(2,3)、(3,2)两个点,所以 a[1,1]存放两个点中的任意一个即可。递推结束以后,如果a[1,1]值为(0,0) 说明不存在路径,否则a[1,1]值就是马走下一步的坐标,以此递推输出路径。

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;

乘火车
火车从始发站(称为第1站)开出,在始发站上车的人数为a, 然后到达第2站,在第2站有人上、下车,但上、下车的人数相同, 因此在第2站开出时(即在到达第3站之前)车上的人数保持为a人。 从第3站起(包括第3站)上、下车的人数有一定规律:上车的人数 都是前两站上车人数之和,而下车人数等于上一站上车人数,一直 到终点站的前一站(第n-1站),都满足此规律。现给出的条件是: 共有n个车站,始发站上车的人数为a,最后一站下车的人数是m (全部下车)。试问第x站开出时车上的人数是多少? 输入文件chc.in:一行四个整数a,n,m和x(中间用空格隔开) 输出文件chc.out:一行一个整数(从x站开出时车上的人数) 样例 : chc.in 4 6 32 4 chc.out 18

分析: 设up[i]为i站的上车人数、down[i]为i站的下车人数、p[i]为i站开出时 车上的人数(1≤i≤n)。初始时up[1]=p[1]=a,down[1]=0。 ①依次枚举第2站的上车人数为1,2,…… 设第2站的上车人数为k up[2]=down[2]=k ,p[2]=p[1]+up[2]-down[2]=a ②按照下式递推第3站…第n-1站的车上人数 up[i]=up[i-1]+up[i-2] down[i]=up[i-1] p[i]=p[i-1]+up[i]-down[i]=p[i-1]+up[i-2] (3≤i≤n-1) ③计算从x站开出时车上的人数 若p[n-1]=m,则输出p[x];否则k←k+1,返回①…,直至p[n-1]>m为 止。因为p相对k是递增的,因此在当前p[n-1]>m的情况下,无论k值 怎样增加也不会使得p[n-1]=m的。

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.


相关文章:
递推算法
递推分倒推法和顺推法 两种形式。一般分析思路: If 求解初始条件 f1 then ...(NOIP2002 初中组第四题) 【问题描述】棋盘上 A 点有一个过河卒,需要走到...
递推算法
递推算法 13页 免费 递推算法 17页 1财富值 noip讲义6-回溯法 38页 免费 ...【样例】 Count.in 11 Count.out 1 4 1 1 1 1 1 1 1 1 解题思路: ...
递推
题, 我们把这样的求解思路 (算法)称之为递推法。...在历年 noip 的复赛当中,参赛选手对于这 类题目都...(i=4;i<22;i++) { cuopai[i]=(i-1)*(...
NOIP算法总结
NOIP算法总结_电脑基础知识_IT/计算机_专业资料。...(4)找出边界条件。19 (5)设定初始值。 (6)递推...O(m^3) 法 2: 设 Q[i]表示前 i 天能达到...
名校noip讲义-背包问题思路
名校noip讲义-背包问题思路_学科竞赛_高中教育_教育专区...小学四年级趣味数学题216份文档 2015全国两会专题傅莹:“史上最严环保法”对污染表示“零容忍” 俞正声...
递归递推
递推和递归 4页 免费 第十讲 递归与递推式 26页 免费 (2)递归与递推 7页 1财富值喜欢此文档的还喜欢 递推与递归应用 16页 免费 pascal递归算法 noip竞赛...
2014noip复赛模拟练习4(答案)
2014noip复赛模拟练习4(答案)_学科竞赛_初中教育_教育专区。编程输入若干个字符串...一味递推不寻求算法优化 ,速度较之搜索提高不少 ,但一旦数据规模过大 ,很难...
NOIP信息学奥赛复赛做题指导
NOIP试题信息学奥赛初赛... 14页 4下载券 noip第...对于规律,需要强调的是 归纳法 ,从 N 过渡到 N+...该问题所 有情况的一般规律,并由此建立一个递推...
NOIP问题求解集合
递推公式给出的某人从底层开始走完全部楼梯的走法为(用 F(N))记录不同案...答: 5 2. 答: 11 NOIP2006 普及二、问题求解:每题 5 分) ( 1. 4 次...
noip2015提高组复赛试题答案
noip2015提高组复赛试题答案_IT认证_资格考试/认证_...设某算法的计算时间表示为递推关系式 T(n) = T...[i] > mid 4) inc(count) 5) rbound := ...
更多相关标签: