《noip讲义4递推法》由会员分享，可在线阅读，更多相关《noip讲义4递推法（87页珍藏版）》请在金锄头文库上搜索。
1、noipnoip讲义讲义4 4递推法递推法采用具体化、特殊化的方法寻找规律采用具体化、特殊化的方法寻找规律平面上平面上n条直线，任两条不平行，任三条不共点，问条直线，任两条不平行，任三条不共点，问这这n条直线把这平面划分为多少个部分？条直线把这平面划分为多少个部分？设这设这n条直线把这平面划分成条直线把这平面划分成Fn个部分。个部分。先用具体化特殊化的方法寻找规律，如图所示，易知先用具体化特殊化的方法寻找规律，如图所示，易知的前几项分别为的前几项分别为这些数字之间的规律性不很明显，这些数字之间的规律性不很明显，较难用不完全归纳法猜较难用不完全归纳法猜出出Fn的一般表达式。但我们可以分析前后项之
2、间的递推关系，的一般表达式。但我们可以分析前后项之间的递推关系，因为这些图形中，后一个都是由前一个添加一条直线而得到的，因为这些图形中，后一个都是由前一个添加一条直线而得到的，添加一条直线便增加若干个区域。添加一条直线便增加若干个区域。一般地，设原来的符合题意的一般地，设原来的符合题意的n-1条直线把这平面分成条直线把这平面分成个区域，再增加一条直线个区域，再增加一条直线l，就变成，就变成n条直线，按题设条条直线，按题设条件，这件，这l必须与原有的必须与原有的n-1条直线各有一个交点条直线各有一个交点,且这且这n-1个交点个交点及原有的交点互不重合。这及原有的交点互不重合。这n-1个交点把个交
3、点把l划分成划分成n个区间，每个区间，每个区间把所在的原来区域一分为二，所以就相应比原来另增了个区间把所在的原来区域一分为二，所以就相应比原来另增了n个区域，即：个区域，即：这样，我们就找到了一个从这样，我们就找到了一个从Fn-1到到Fn的的递推式，再加上的的递推式，再加上已知的初始值已知的初始值F1=2，就可以通过，就可以通过n-1步可重复的简单运算推导步可重复的简单运算推导出出Fn的值。的值。vara,i,n:longint;beginread(n);a:=2;fori:=2tondoa:=a+i;writeln(a);end.在平面内画五条直线和一个圆，最多能把平面分成在平面内画五条直线
4、和一个圆，最多能把平面分成多少部分？多少部分？平面上有平面上有8个圆，最多能把平面分成几部分？个圆，最多能把平面分成几部分？ 123456Fn=Fn-1+2(n-1) 圆周上两个点将圆周分为两半，在这两点上写上数圆周上两个点将圆周分为两半，在这两点上写上数1 1；然后将两段半圆弧对分，在两个分点上写上相邻两点上的数然后将两段半圆弧对分，在两个分点上写上相邻两点上的数之和；再把之和；再把4 4段圆弧等分，在分点上写上相邻两点上的数之段圆弧等分，在分点上写上相邻两点上的数之和，如此继续下去，问第和，如此继续下去，问第6 6步后，圆周上所有点上的步后，圆周上所有点上的数数之和之和是多少？是多少？ 分
5、析分析: :先可以采用作图尝试寻找规律。先可以采用作图尝试寻找规律。第一步：圆周上有两个点，两个数的和是第一步：圆周上有两个点，两个数的和是1+1=21+1=2；第二步：圆周上有四个点，四个数的和是第二步：圆周上有四个点，四个数的和是1+1+2+2=61+1+2+2=6；增加数之和恰好是第一步；增加数之和恰好是第一步圆周上所有数之和的圆周上所有数之和的2 2倍。倍。第三步：圆周上有八个点，八个数的和是第三步：圆周上有八个点，八个数的和是1+1+2+2+3+3+3+3=181+1+2+2+3+3+3+3=18，增加数之和恰，增加数之和恰好是第二步数圆周上所有数之和的好是第二步数圆周上所有数之和的
6、2 2倍。倍。第四步：圆周上有十六个点，十六个数的和第四步：圆周上有十六个点，十六个数的和1+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5=541+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5=54，增加数之和恰好是第三步数圆周上所有数之和的增加数之和恰好是第三步数圆周上所有数之和的2 2倍。倍。这样我们可以知道，圆周上所有数之和是前一步圆周上所有数之和的这样我们可以知道，圆周上所有数之和是前一步圆周上所有数之和的3 3倍。倍。设设A An n为第为第n n步后得出的圆周上所有数之和，则步后得出的圆周上所有数之和，则A An n=3A=3An n1 1在在nn的正方
7、形钉子板上（的正方形钉子板上（n是钉子板每边上的是钉子板每边上的钉子数），求连接任意两个钉子所得到的不同长度的钉子数），求连接任意两个钉子所得到的不同长度的线段种数线段种数.Fn=Fn-1+n如图如图1，是棱长为，是棱长为a的小正方体，图的小正方体，图2，图，图3由这样的小正由这样的小正方体摆放而成。按照这样的方法继续摆放，自上而下分别叫方体摆放而成。按照这样的方法继续摆放，自上而下分别叫第一层、第二层、第一层、第二层、第、第n层，第层，第n层的小正方体的个数记层的小正方体的个数记为为sn。请写出求。请写出求sn的递推公式。的递推公式。13610如图，有边长为如图，有边长为1的等边三角形卡片若
8、干张，使用这些的等边三角形卡片若干张，使用这些三角形卡片拼出边长分别是三角形卡片拼出边长分别是2，3，4，的等边三角形（如的等边三角形（如图所示）根据图形推断，写出求每个等边三角形所用卡片图所示）根据图形推断，写出求每个等边三角形所用卡片总数总数sn的递推公式的递推公式49162536为庆祝为庆祝“五五一一”国际劳动节，市政府决定在人民广场上增设国际劳动节，市政府决定在人民广场上增设一排灯花，其设计由以下图形逐步演变而成，其中圆圈代表灯一排灯花，其设计由以下图形逐步演变而成，其中圆圈代表灯花中的灯泡，花中的灯泡，n代表第代表第n次演变过程，次演变过程，s代表第代表第n次演变后的灯泡次演变后的灯
9、泡的个数。仔细观察下列演变过程，当的个数。仔细观察下列演变过程，当n=6时，时，s=_。94Sn=2sn-1+2Sn=3sn-1-2sn-2某公共汽车线路上共有某公共汽车线路上共有15个车站（包括起点站和终点站）个车站（包括起点站和终点站）。在每个站上车的人中，恰好在以后各站下去一个。要使行。在每个站上车的人中，恰好在以后各站下去一个。要使行驶过程中每位乘客都有座位，车上至少要备有多少个座位？驶过程中每位乘客都有座位，车上至少要备有多少个座位？从表中可以看出车上人数最多是从表中可以看出车上人数最多是56人，所以车上人，所以车上至少要准备至少要准备56个座位。个座位。练习练习1 将一张长方形的纸
10、对折，可得到一条折痕，继续对将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到条折痕，那么对折三次后，可得到条折痕，那么对折n次，可得到几条次，可得到几条折痕？折痕？Fn=2*Fn-1+1vara,i,n:longint;beginread(n);a:=1;fori:=2tondoa:=2*a+1;writeln(a);end.varf,s,i,n,j:longint;beginread(n);f:=1;fori:=2tondobegins:=1;forj:=1toi-1dos:=s*2;f
11、:=f+s;end;writeln(f);end.Fn=Fn-1+2n-1var加入高精度运算加入高精度运算a,b:array1.100ofinteger;i,j,n:integer;beginreadln(n);a100:=1;n=1时时b100:=1;20=1fori:=2tondobeginforj:=100downto1dobj:=bj*2;递推出递推出2i-1forj:=100downto2doifbj=10thenbeginbj-1:=bj-1+bjdiv10;bj:=bjmod10;end;forj:=100downto1dobeginaj:=aj+bj;ifaj=10thenb
12、eginaj-1:=aj-1+ajdiv10;aj:=ajmod10;end;end;end;j:=1;whileaj=0doj:=j+1;fori:=jto100dowrite(ai);end.练习练习2 如图如图,第一次把三角形剪去一个角后第一次把三角形剪去一个角后,图中最多有四个图中最多有四个角角,第二次再把新产生的角各剪一刀第二次再把新产生的角各剪一刀,如此下去如此下去,每一次每一次都是把新产生的角各剪一刀都是把新产生的角各剪一刀,则第则第n次剪好后次剪好后,图中图中最多最多有有多少个角多少个角?46101834Fn=Fn-1+2n-1varf,s,i,n,j:longint;begi
13、nread(n);f:=4;fori:=2tondobegins:=1;forj:=1toi-1dos:=s*2;f:=f+s;end;writeln(f);end.vara,b:array1.100oflongint;i,j,n:longint;beginreadln(n);a100:=4;b100:=1;fori:=2tondobeginforj:=100downto1dobj:=bj*2;forj:=100downto2doifbj=10thenbeginbj-1:=bj-1+bjdiv10;bj:=bjmod10;end;forj:=100downto1dobeginaj:=aj+bj
14、;ifaj=10thenbeginaj-1:=aj-1+ajdiv10;aj:=ajmod10;end;end;end;j:=1;whileaj=0doj:=j+1;fori:=jto100dowrite(ai);end.练习练习3下图中把大正方形各边平均分成了下图中把大正方形各边平均分成了5份，此时有份，此时有55个正方个正方形。如果把正方形各边平均分成形。如果把正方形各边平均分成n份，那么得到的正方形总数份，那么得到的正方形总数为多少？为多少？52+42+32+22+12=55n2+(n-1)2+(n-2)2+22+1Fn=Fn-1+n2vara,i,n:longint;beginread
15、(n);a:=1;fori:=2tondoa:=a+i*i;writeln(a);end.Var加入高精度运算加入高精度运算a:array1.25oflongint;i,j,k,x,n:longint;beginreadln(n);a25:=1;n=1时时fori:=2tondobeginx:=i*i;forj:=25downto1dobeginaj:=aj+xmod10;ifaj=10thenbeginaj:=aj-10;aj-1:=aj-1+1;end;x:=xdiv10;end;end;j:=1;whileaj=0doj:=j+1;fori:=jto25dowrite(ai);end.练
16、习练习4 如图，由等圆组成的一组图中，第如图，由等圆组成的一组图中，第1个图由个图由1个圆组成，个圆组成，第第2个图由个图由7个圆组成，第个圆组成，第3个图由个图由19个圆组成，个圆组成，按照，按照这样的规律排列下去，则第这样的规律排列下去，则第9个图形由个图形由_个圆组成。个圆组成。217可得递推公式可得递推公式:Fn=Fn-1+6*（n1）vara,i,n:longint;beginread(n);a:=1;fori:=2tondoa:=a+6*(i-1);writeln(a);end.var加入高精度运算加入高精度运算a:array1.50oflongint;i,j,k,x,n:long
17、int;beginreadln(n);a50:=1;fori:=2tondobeginx:=(i-1)*6;forj:=50downto1dobeginx:=x+aj;aj:=xmod10;x:=xdiv10;end;end;j:=1;whileaj=0doj:=j+1;fori:=jto50dowrite(ai);end.练习练习5已知三角形已知三角形ABC的面积为的面积为10，延长边，延长边BC到点到点D，使，使BC=CD，延长边延长边CA到点到点E，使，使CA=AE，延长边，延长边AB到点到点F，使，使AB=BF，连，连结结DE,EF,FD,得到三角形得到三角形DEF,并记图中阴影部分面
18、积为并记图中阴影部分面积为S1,此时我此时我们称三角形们称三角形ABC向外扩展了一次向外扩展了一次.求经过求经过N次扩展后图中阴影部分次扩展后图中阴影部分的面积的面积Sn.Fn=7*Fn-1(Fn为第为第n次扩展后整个三角形的面积次扩展后整个三角形的面积)F0=10Sn=Fn-Fn-1constmax=100;varf1,f2,s:array1.maxoflongint;i,j,k,l,n:longint;beginreadln(n);f1max:=0;f1max-1:=1;F0=10fori:=1tondobeginf2:=f1;k:=0;7forj:=maxdownto1dobegink:
19、=k+f1j*7;f1j:=kmod10;k:=kdiv10;end;end;fori:=maxdownto1do相减相减beginiff1if2ithenbeginf1i:=f1i+10;f1i-1:=f1i-1-1;end;si:=f1i-f2i;end;j:=1;whilesj=0doj:=j+1;fori:=jtomaxdowrite(si);end.Hanoi双塔双塔问题问题 给定给定A、B、C三根足够长的细柱，在三根足够长的细柱，在A柱上放有柱上放有2n个中个中 间有孔的圆盘，共有间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这
20、两个圆盘是不加区分的（下图为的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）的情形）。现要将这些圆盘移到。现要将这些圆盘移到C柱上，在移动过程中可放在柱上，在移动过程中可放在B柱上暂柱上暂存。要求：存。要求： （1）每次只能移动一个圆盘；）每次只能移动一个圆盘； （2）A、B、C三根细柱上的圆盘都要保持上小下大的顺三根细柱上的圆盘都要保持上小下大的顺序；序； 任务：设任务：设An为为2n个圆盘完成上述任务所需的最少移动次个圆盘完成上述任务所需的最少移动次数，对于输入的数，对于输入的n，输出，输出An。 输入文件输入文件hanoi.in为一个正整数为一个正整数n，表示在，表示在A柱上放有
21、柱上放有2n个圆盘。个圆盘。 输出文件输出文件hanoi.out仅一行，包含一个正整数仅一行，包含一个正整数，为完成上为完成上述任务所需的最少移动次数述任务所需的最少移动次数An。 【样例【样例1】hanoi.inhanoi.out12【样例【样例2】hanoi.inhanoi.out26【限制】【限制】 对于对于50%的数据，的数据，1=n=25 对于对于100%的数据，的数据，1=n9 then begin 处理进位处理进位 aj+1:=aj+1+1; aj:=aj mod 10; end; end; f:=false; for i:=62 downto 1 do begin if ai0
22、 then f:=true; if f then write(ai); end; close(input); close(output);end.在上面的一些例题中，递推过程中的某个状态在上面的一些例题中，递推过程中的某个状态只与前面的一个状态有关，递推关系并不复杂。如只与前面的一个状态有关，递推关系并不复杂。如果在递推中的某个状态与前面的几个状态、甚至所果在递推中的某个状态与前面的几个状态、甚至所有状态都有关，就不容易找出递推关系式，这就需有状态都有关，就不容易找出递推关系式，这就需要我们对实际问题进行分析与归纳，从中找到突破要我们对实际问题进行分析与归纳，从中找到突破口，总结出递推关系式。
23、口，总结出递推关系式。意大利著名数学家斐波那契在研究兔子繁殖问题时，发现意大利著名数学家斐波那契在研究兔子繁殖问题时，发现有这样一组数：有这样一组数：1，1，2，3，5，8，13，其中从第三个数，其中从第三个数起，每一个数都等于它前面两上数的和。现以这组数中的各个起，每一个数都等于它前面两上数的和。现以这组数中的各个数作为正方形的边长构造如下正方形：数作为正方形的边长构造如下正方形：再分别依次从左到右取再分别依次从左到右取2个、个、3个、个、4个、个、5个正方形拼成个正方形拼成如下矩形并记为如下矩形并记为、若按此规律继续作矩形，则序号为若按此规律继续作矩形，则序号为的矩形周长是。的矩形周长是。
24、466【问题描述】【问题描述】一只蜜蜂在上图所示的数字蜂房上爬动一只蜜蜂在上图所示的数字蜂房上爬动,已知它只已知它只能从标号小的蜂房爬到标号大的相邻蜂房能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：现在问你：蜜蜂从蜂房蜜蜂从蜂房M开始爬到蜂房开始爬到蜂房N（MN），有多少种爬），有多少种爬行路线？行路线？【输入格式】【输入格式】输入输入M，N的值。的值。(1=M,N0），求出铺法总数的递推公式。），求出铺法总数的递推公式。F(1)=1F(2)=2F(n)=F(n-2)+F(n-1)(n=3)如果有如果有n元钱元钱,每天去购买下列三种商品之一每天去购买下列三种商品之一:蔬菜要蔬菜要用用1元钱元
25、钱,猪肉要用猪肉要用2元钱元钱,鸡蛋要用元钱用鸡蛋要用元钱用An表示把这表示把这n元钱用完的所有可能的用法的总数元钱用完的所有可能的用法的总数如果第一天买蔬菜，则用去元钱，还剩如果第一天买蔬菜，则用去元钱，还剩n-1元钱，元钱，这这n-1元钱的用法有元钱的用法有n-1种；种；如果第一天买猪肉，则用去元钱，还剩如果第一天买猪肉，则用去元钱，还剩n-元钱，元钱，这这n-元钱的用法有元钱的用法有n-2种；种；如果第一天买鸡蛋，则用去元钱，还剩如果第一天买鸡蛋，则用去元钱，还剩n-元钱，元钱，这这n-元钱的用法有元钱的用法有n-2种；种；所以，所以，n=n-1+2n-2有排成一行的个方格，用红、黄、蓝
26、三色涂每个格子，有排成一行的个方格，用红、黄、蓝三色涂每个格子，每格涂一色，要求任何相邻的格不同色，且首尾两格也不同色。每格涂一色，要求任何相邻的格不同色，且首尾两格也不同色。问有多少种涂法？问有多少种涂法？解：解：设共有设共有n种涂法，易见种涂法，易见1，2，3，且当，且当时，将时，将个格子依次编号后，格与格（个格子依次编号后，格与格（n-1）不相邻。）不相邻。情形情形：格（：格（n-1）涂色与格不同，此时格只有一色可涂，且前（）涂色与格不同，此时格只有一色可涂，且前（n-1）格满足首尾两格不同色，故有格满足首尾两格不同色，故有n-1种涂色方法。种涂色方法。情形情形：格（：格（n-1）涂色与
27、格相同，此时格（）涂色与格相同，此时格（n-2）与格涂色必然不同，）与格涂色必然不同，不然，格（不然，格（n-1）与（）与（n-2）相同，于是前（）相同，于是前（n-2）格有）格有n-2种涂色法。因为格种涂色法。因为格与格不同色，有两种涂色法，故共有与格不同色，有两种涂色法，故共有n-2种涂色法。种涂色法。综上，可得综上，可得nn-1n-2（）按前按前n-1格首尾关系讨论格首尾关系讨论错位排列错位排列五个人排成一列，重新站队时，各人都不站在原来的位置上，那么不同的站五个人排成一列，重新站队时，各人都不站在原来的位置上，那么不同的站队方式共有队方式共有()（A）60种种（B）44种种（C）36种
28、种（D）24种种解：首先我们把人数推广到解：首先我们把人数推广到n个人，即个人，即n个人排成一列，重新站队时，各人都不个人排成一列，重新站队时，各人都不站在原来的位置上。设满足这样的站队方式有站在原来的位置上。设满足这样的站队方式有An种，现在我们通过合理分步，恰当种，现在我们通过合理分步，恰当分类分类来来找出递推关系：找出递推关系：第一步第一步：第一个人不站在原来的第一个位置，有：第一个人不站在原来的第一个位置，有n-1种站法。种站法。第二步第二步：假设第一个人站在第：假设第一个人站在第2个位置，则第二个人的站法又可以分为两类：个位置，则第二个人的站法又可以分为两类：第第一类一类，第二个人恰
29、好站在第一个位置，则余下的，第二个人恰好站在第一个位置，则余下的n-2个人有个人有An-2种站队方式；种站队方式；第二类第二类，第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不站在第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不站在第三个位置，第四个人不站在第四个位置，第三个位置，第四个人不站在第四个位置，第，第n个人不站在第个人不站在第n个位置，所以个位置，所以有有An-1种站队方式。种站队方式。由分步计数原理和分类计数原理，我们便得到了数列由分步计数原理和分类计数原理，我们便得到了数列的递推关系式：的递推关系式：，显然，显然，再由递推关系有，再由递推
30、关系有， 在书架上放有编号为在书架上放有编号为1 ，2 ，n的的n本书。现将本书。现将n本书全部取下然后再放回去，当放回去时要求每本书本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。都不能放在原来的位置上。 例如：例如：n = 3时：时： 原来位置为：原来位置为：1 2 3 放回去时只能为：放回去时只能为：3 1 2 或或 2 3 1 这两种这两种 问题：求当问题：求当n = 5时满足以上条件的放法共有多少时满足以上条件的放法共有多少种？种？染色问题染色问题 用用4种不同颜色涂四边形的种不同颜色涂四边形的4个顶点，要求每点染一种颜个顶点，要求每点染一种颜色，相邻的顶点染不
31、同的颜色，则不同的染色方法有色，相邻的顶点染不同的颜色，则不同的染色方法有()（A）84种种（B）72种种（C）48种种（D）24种种AVari,j,k,m,n:longint;a:array1.10oflongint;functionjc(k:integer):longint;求求K!vari,j:longint;beginj:=1;fori:=2tokdoj:=j*i;jc:=j;end;beginreadln(n,m);n是顶点数，是顶点数，m是颜色数是颜色数a3:=jc(m)divjc(m-3);初值初值fori:=4tondobeginj:=1;fork:=1toi-1doj:=j*
32、(m-1);ai:=m*j-ai-1;递推公式递推公式end;writeln(an);end.a3:=m*(m-1)*(m-2)如图，一个地区分为如图，一个地区分为5个行政区域，现给地图着色，要求个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有四种颜色可供选择，则相邻区域不得使用同一颜色，现有四种颜色可供选择，则不同的着色方法共有不同的着色方法共有种。种。图中图中2、3、4、5四个区域围成一个四边形，因此可以四个区域围成一个四边形，因此可以把它们看成是一个四边形的把它们看成是一个四边形的4个顶点，而区域个顶点，而区域1就是这个四就是这个四边形对角线的交点。边形对角线的交点。第一步，
33、先涂区域第一步，先涂区域1，有，有4种涂法。种涂法。第二步，由于区域第二步，由于区域1跟其余四个区域都相邻，因此涂跟其余四个区域都相邻，因此涂1的颜色不能用来涂其余的四个区域，因此第二步相当于用的颜色不能用来涂其余的四个区域，因此第二步相当于用3种颜色来涂一个四边形的四个顶点，不难得出种颜色来涂一个四边形的四个顶点，不难得出所以，所以，由分步计数原理，得出共有由分步计数原理，得出共有种涂法。种涂法。某城市在中心广场建造一个花圃，花圃分成某城市在中心广场建造一个花圃，花圃分成6个部分个部分(如如图图)，现要栽种，现要栽种4种不同颜色的花，每部分栽种一种且相邻部种不同颜色的花，每部分栽种一种且相邻
34、部分不能栽种同样颜色的花，不同的栽种方法共有分不能栽种同样颜色的花，不同的栽种方法共有种。种。120430=120传球传球问题问题 4个人进行篮球训练，互相传球接球，要求每个人接球个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？五次传球后，球又回到甲手中，问有多少种传球方式？60分析分析 :设第设第n次传球后，球又回到甲手中的传球方式有次传球后，球又回到甲手中的传球方式有an种种。可以想象前。可以想象前n-1次传球，如次传球，如果每一次传球都任选其他
35、三人中的一人进行接球，则每次传球都有果每一次传球都任选其他三人中的一人进行接球，则每次传球都有3种可能，由乘法原种可能，由乘法原理，共有理，共有 333=3 n-1 种传球方法。这些传球方式可以分为两类种传球方法。这些传球方式可以分为两类: 一类是第一类是第n-1次恰好传到甲手中，这有次恰好传到甲手中，这有an-1种传法，它们不符合要求，因为这样第种传法，它们不符合要求，因为这样第n次无法再把球传给甲；次无法再把球传给甲； 另一类是第另一类是第n-1次传球，球不在甲手中，第次传球，球不在甲手中，第n次持球人再将球传给甲，有次持球人再将球传给甲，有an种传法。种传法。 根据加法原理，有根据加法原
36、理，有an-1+an=3 n-1 。 由于甲是发球者，一次传球后球又回到甲手中的传球方式是不存在的，所以由于甲是发球者，一次传球后球又回到甲手中的传球方式是不存在的，所以a1=0。 利用递推关系可以得到利用递推关系可以得到 a2=3-0=3， a3=33-3=6， a4=333-6=21， a5=3333-21=60。 这说明经过这说明经过5次传球后，球仍回到甲手中的传球方法有次传球后，球仍回到甲手中的传球方法有60种。种。vara:array1.100oflongint;n,m,i,j:longint;beginreadln(n,m);a1:=0;j:=1;fori:=2tomdobegin
37、j:=j*(n-1);先求出先求出(n-1)i-1ai:=j-ai-1;end;writeln(am);end.var加入高精度运算加入高精度运算a:array1.100,1.100ofinteger;s:array1.100ofinteger;i,j,t,k,n,m:longint;beginreadln(n,m);a1,100:=0;s100:=1;fori:=2tomdobeginforj:=100downto1dosj:=sj*(n-1);forj:=100downto1doifsj9thenbeginsj-1:=sj-1+sjdiv10;sj:=sjmod10;end;forj:=1
38、00downto1doai,j:=sj-ai-1,j;forj:=100downto1doifai,j0thenbeginai,j-1:=ai,j-1-1;ai,j:=ai,j+10;end;end;j:=1;whileam,j=0doj:=j+1;fori:=jto100dowrite(am,i);end.凸多边形划分凸多边形划分 在一个凸多边形中，通过若干条互不相交的对角线，把这在一个凸多边形中，通过若干条互不相交的对角线，把这个凸多边形剖分成了若干个三角形。现在的任务是根据输入的个凸多边形剖分成了若干个三角形。现在的任务是根据输入的凸多边形的边数，求不同剖分的方案数凸多边形的边数，求不同
39、剖分的方案数Cn。比如当。比如当n=5时，有时，有如下如下5种不同的方案，所以种不同的方案，所以C5=5。输入文件输入文件14.in：一个正整数，表示凸多边形的边数。：一个正整数，表示凸多边形的边数。(n=21)输出文件输出文件14.out：一个正整数，表示方案总数。：一个正整数，表示方案总数。如图所示，我们以如图所示，我们以p1pn这条边为基准边，再找这条边为基准边，再找pk来构成三角形，来构成三角形，则原则原凸凸n边形被剖解成了边形被剖解成了p1pkpn和两个和两个凸多边形，其中一个是凸多边形，其中一个是由由p1,p2,pk构成的构成的凸凸k边形，另一个是由边形，另一个是由pk,pk+1,
40、pn构成的构成的凸凸n-k+1边形，根据乘法原理，选择边形，根据乘法原理，选择pk这个顶点的分解方案为这个顶点的分解方案为种。而种。而k可以选可以选2到到n-1，所以根据加法原理，得出总，所以根据加法原理，得出总的方案数为的方案数为注意，就这个递推关系而言，临界值应为注意，就这个递推关系而言，临界值应为C2=1，而不是，而不是C3=1，否则递推关系就得不到正确解，这与原问题的实际情况，否则递推关系就得不到正确解，这与原问题的实际情况可能不符（即两边形），其实这只是理解上的差异可能不符（即两边形），其实这只是理解上的差异P1PnP2P3PkPn-1Pn-2constmax=21;varc:arr
41、ay2.maxoflongint;n,i,k:integer;total:longint;beginreadln(n);c2:=1;fori:=3tondobeginci:=0;fork:=2toi-1doci:=ci+ck*ci-k+1;end;writeln(cn);end.求路径总数求路径总数下图是某居民小区道路图，小明每天由家（点）到学校（点），他下图是某居民小区道路图，小明每天由家（点）到学校（点），他只沿道路向上或向右行走，那么他最多有（）天走不同线路？只沿道路向上或向右行走，那么他最多有（）天走不同线路？10152128364541020355684120165515357012
42、6210330495vari,j,n,m:integer;a:array1.20,1.20oflongint;beginread(n,m);fillchar(a,sizeof(a),0);fori:=1tondoaI,1:=1;forj:=1tomdoa1,j:=1;fori:=2tondoforj:=2tomdoaI,j:=aI,j-1+ai-1,j;writeln(an,m);end.要想到达坐标为（要想到达坐标为（i,j）的顶点的话，必定）的顶点的话，必定要经过坐标为（要经过坐标为（i-1,j）的顶点或坐标为）的顶点或坐标为（i,j-1）的顶点，设）的顶点，设a(I,j)表示从点表示从点
43、A到顶点到顶点(I,j)的路径总条数，则的路径总条数，则a(I,j)=a(I,j-1)+a(i-1,j)输入：输入：59输出：输出：495街道路径街道路径 设有一个设有一个NM（1=N=50，1=M=50）的街）的街道，规定行人从道，规定行人从A(1,1)出发，在街道上出发，在街道上只能向东或北行走只能向东或北行走。 若在此街道中，设置一个矩形障碍区域（包括围住该若在此街道中，设置一个矩形障碍区域（包括围住该区域的的街道）不让行人通行，如上图中用区域的的街道）不让行人通行，如上图中用“”表示的部表示的部分。此矩形障碍区域用分。此矩形障碍区域用2对顶点坐标给出，如上图中的对顶点坐标给出，如上图中
44、的2对对顶点坐标为顶点坐标为(2，2),(8，4)，此时从，此时从A出发到达出发到达B的路径有的路径有两条。两条。 现给出现给出N、M，同时再给出此街道中的矩形障碍区域的，同时再给出此街道中的矩形障碍区域的2对顶点坐标对顶点坐标(x1,y1)，（，（x2,y2），请求出此时所有从），请求出此时所有从A出出发到达发到达B的路径的条数。的路径的条数。 由于在街上只能向东或北方向行走，因此要想达到坐标由于在街上只能向东或北方向行走，因此要想达到坐标为（为（i,j）的顶点的话，必定要经过坐标为（）的顶点的话，必定要经过坐标为（i-1,j）的顶点或）的顶点或坐标为（坐标为（i,j-1）的顶点，假设从起始
45、顶点到达坐标为（）的顶点，假设从起始顶点到达坐标为（i,j）的顶点的路径总数为的顶点的路径总数为ai,j，则，则ai,j= ai-1,j +ai,j-1。因此我们可以采用逐因此我们可以采用逐行行递推的方法来求出从起始顶点到达任递推的方法来求出从起始顶点到达任意一个顶点的路径总数。意一个顶点的路径总数。varn,m,i,j,x1,x2,y1,y2:integer;a:array1.50,1.50oflongint;b:array1.50,1.50ofboolean;beginreadln(n,m);行列要分清行列要分清readln(x1,y1,x2,y2);fillchar(a,sizeof(a
46、),0);fillchar(b,sizeof(b),true);fori:=y1toy2doforj:=x1tox2dobi,j:=false;fori:=1tomdobeginifnot(bi,1)thenbreak;ai,1:=1;end;forj:=1tondobeginifnot(b1,j)thenbreak;a1,j:=1;end;fori:=2tomdoforj:=2tondoifbi,jthenai,j:=ai-1,j+ai,j-1;write(am,n);end.有可能障碍区域靠边有可能障碍区域靠边如输入如输入9512842应输出应输出31 Var加入高精度运算加入高精度运算n
47、,m,i,j,x1,x2,y1,y2,k,g:integer;a:array1.50,1.50,1.30oflongint;b:array1.50,1.50ofboolean;beginreadln(n,m);readln(x1,y1,x2,y2);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),true);fori:=y1toy2doforj:=x1tox2dobi,j:=false;fori:=1tomdobeginifnot(bi,1)thenbreak;ai,1,1:=1;end;forj:=1tondobeginifnot(b1,j)then
48、break;a1,j,1:=1;end;fori:=2tomdoforj:=2tondoifbi,jthenbeging:=0;fork:=1to30dobeginai,j,k:=ai-1,j,k+ai,j-1,k+g;g:=ai,j,kdiv10;ai,j,k:=ai,j,kmod10;end;end;j:=30;fori:=30downto1doifam,n,i=0thenj:=j-1;fori:=jdownto1dowrite(am,n,i);end.过河卒过河卒 如图，如图，A A 点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标 B B 点。卒行走规则：可以向点。卒行走规则：
49、可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C C点），点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C C 点上的马可以控制点上的马可以控制 9 9 个点（图中的个点（图中的P1P1，P2 P8 P2 P8 和和 C C）。卒不能通过对方）。卒不能通过对方马的控制点。棋盘用坐标表示，马的控制点。棋盘用坐标表示，A A 点（点（0 0，0 0）、）、B B 点（点（n,mn,m）( ( n,mn,m为不超过为不超过 2020的整数的
50、整数) )，同样马的位置坐标是需要给出的（约定，同样马的位置坐标是需要给出的（约定: CA: CA，同时，同时CBCB）。）。现在要求你计算出卒从现在要求你计算出卒从 A A 点能够到达点能够到达 B B 点的路径的条数。点的路径的条数。 输入文件输入文件5.in5.in，只有一行，共，只有一行，共4 4个正整数，前个正整数，前2 2个数表示个数表示B B点的坐标，后点的坐标，后2 2个数表示对方马的坐标。个数表示对方马的坐标。 输出文件输出文件5.out5.out，只有一行，一个整数（表示路径的条数）。，只有一行，一个整数（表示路径的条数）。 样例样例: : 输入输入 6 6 3 2 6 6
51、 3 2 输出输出 17 17分析分析:要到达棋盘上的一个点，只能从左边过来或是从上面要到达棋盘上的一个点，只能从左边过来或是从上面下来，所以根据加法原理，到达某一点的路径数目，等于下来，所以根据加法原理，到达某一点的路径数目，等于到达其相邻上、左两点的路径数目之和，因此我们可以使到达其相邻上、左两点的路径数目之和，因此我们可以使用逐行递推的方法来求出从起始顶点到终点的路径数目，用逐行递推的方法来求出从起始顶点到终点的路径数目，如果有障碍，只要将到达该点的路径数目设置为即可。如果有障碍，只要将到达该点的路径数目设置为即可。const x1:array1.8of integer=(2,2,1,-
52、1,-2,-2,-1,1); y1:array1.8of integer=(1,-1,-2,-2,-1,1,2,2);var b:array0.20,0.20 of boolean; i,j,x,y,k,p,n,m:integer; a:array0.20,0.20 of integer;beginreadln(n,m,x,y); fillchar(b,sizeof(b),true); fillchar(a,sizeof(a),0);bx,y:=false;for i:=1 to 8 do if (x+x1i=0)and(x+x1i=0)and(y+y1i=0)and(x+x1i=0)and(
53、y+y1i1) do j:=j-1; for i:=j downto 1 do write(an,m,i); end.传球游戏传球游戏【问题描述】【问题描述】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。游戏规则是这样的：老师带着同学们一起做传球游戏。游戏规则是这样的：n个同学站成一个个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老个同学可以把球
54、传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。败者，要给大家表演一个节目。聪明的小蛮提出了一个有趣的问题：聪明的小蛮提出了一个有趣的问题：有多少种不同的传球方法可以有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了使得从小蛮手里开始传的球，传了m次后，又回到小蛮手里。次后，又回到小蛮手里。两种传球方两种传球方法被视为不同的方法，当且仅当这两种方法中，接到球的同学按接球顺法被视为不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成
55、的序列是不同的。比如有序组成的序列是不同的。比如有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.in3ball.out32【限制】【
56、限制】40%的数据满足：的数据满足：3=n=30，1=m=20100%的数据满足：的数据满足：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
57、,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)中。中。vari,j,k,n,m:longint;f:array0.30,0.30oflongint;beginreadln(n,m);fillchar(f,sizeof(f),0);f1,0:=1;fork:=1tomdobeginf1,k:=f2,k-1+fn,k-1;当球在当球在1号同学时号同学时fori:=2ton-1dofi,k:=
58、fi-1,k-1+fi+1,k-1;fn,k:=fn-1,k-1+f1,k-1;当球在当球在n号同学时号同学时end;write(f1,m);end.传球传球问题问题 4个人进行篮球训练，互相传球接球，要求每个人接球个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？五次传球后，球又回到甲手中，问有多少种传球方式？Varn,m,i,j,k,l,g:longint;a:array0.30,1.30,1.100oflongint;beginread(n,m)
59、;a0,1,1:=1;fori:=1tomdobeginforj:=1tondofork:=1tondoifjkthenbeging:=0;forl:=1to100dobeging:=ai,j,l+ai-1,k,l+g;ai,j,l:=gmod10;g:=gdiv10;end;end;end;l:=100;whileam,1,l=0dol:=l-1;fori:=ldownto1dowrite(am,1,i);end.整数划分整数划分把一个正整数把一个正整数N划分成一些正整数的和，例如：划分成一些正整数的和，例如：N=n1+n2+nk且满足且满足1=n1=n2=nk=N，叫做叫做N的一个划分。求
60、不同的划分的数量。的一个划分。求不同的划分的数量。当当n=4时，划分数为时，划分数为4。4=1+1+1+1；4=1+1+2；4=1+3；4=2+2；设设表示把正整数表示把正整数a做分划、其中最大的一份恰好是做分划、其中最大的一份恰好是b的方案总数。的方案总数。设表示把正整数设表示把正整数a做分划、其中最大的一份不大于做分划、其中最大的一份不大于b的方案总数。的方案总数。显然有：显然有：所以：所以：当当i=jthengi,j:=gi-j,j+gi,j-1elsegi,j:=gi,j-1;writeln(gn,n-1);end.倒推法倒推法我们把由已知初始值为我们把由已知初始值为1，通过递推关，通
61、过递推关系式系式n=g(Fn-1)求出其最终结果求出其最终结果Fn的递推方式的递推方式称为顺推法同理，把已知最终结果为称为顺推法同理，把已知最终结果为Fn，通，通过递推关系式过递推关系式n-1=g(Fn)，求出其初始值，求出其初始值1的的递推方式称之为倒推法。递推方式称之为倒推法。四个人做火柴游戏四个人做火柴游戏,每一局三个人赢每一局三个人赢,一个人输一个人输,输者要按赢输者要按赢者手中赢得火柴根数赔偿者手中赢得火柴根数赔偿,即赢者手中有多少根火柴即赢者手中有多少根火柴,输者就赔输者就赔他多少他多少?4次之后次之后,每人恰好输过一次而且手中都恰好有每人恰好输过一次而且手中都恰好有16根根?求求
62、四人原有火柴数四人原有火柴数?把第一局输的人记为，把第二局输的人记为，把第三把第一局输的人记为，把第二局输的人记为，把第三局输的人记为，把第四局输的人记为，用倒退法可知：局输的人记为，把第四局输的人记为，用倒退法可知：开始骑士游历骑士游历 设有一个设有一个n*m的棋盘的棋盘(2=n=50，2=m(2,3)-(4,4)。若不存。若不存在路径在路径,则输出则输出no。算法分析算法分析：我们先将棋盘的横坐标规定为：我们先将棋盘的横坐标规定为i，纵坐标规定为，纵坐标规定为j，对于一个，对于一个nm的棋盘，的棋盘，i的值从的值从1到到n，j的值从的值从1到到m。棋盘上的任意点都可以用坐。棋盘上的任意点都
63、可以用坐标标(i,j)表示。对于马的移动方法，我们用表示。对于马的移动方法，我们用K来表示四种移动方向来表示四种移动方向(1,2,3,4)；而每种移动方法用偏移值来表示，并将这些偏移值分别保存在数组；而每种移动方法用偏移值来表示，并将这些偏移值分别保存在数组dx和和dy中，如下表中，如下表：K KDxkDxk DykDyk 12122-13 3124 41-2根据马走的规则，马可以由（根据马走的规则，马可以由（i-dxk,j-dyk）走到）走到(i,j)。只要马能从。只要马能从（1，1）走到（）走到（i-dxk,j-dyk），就一定能走到（），就一定能走到（i,j）,马走的坐标必须保马走的坐标
64、必须保证在棋盘上证在棋盘上。我们以（。我们以（n,m）为起点向左递推，当递推到（）为起点向左递推，当递推到（i-dxk,j-dyk）的位置是（的位置是（1，1）时，就找到了一条从（）时，就找到了一条从（1，1）到（）到（n,m）的路径。）的路径。我们用一个二维数组我们用一个二维数组a表示棋盘，采用倒推法，从终点表示棋盘，采用倒推法，从终点(n,m)往左递推，往左递推，设初始值设初始值an,m为（为（-1，-1），如果从），如果从(i,j)一步能走到一步能走到(n,m)，就将，就将(n,m)存放存放在在ai,j中。如下表，中。如下表，a3,2和和a2,3的值是（的值是（4，4），表示从这两个点都
65、可），表示从这两个点都可以到达坐标（以到达坐标（4,4）。从（）。从（1,1）可到达（）可到达（2，3）、（）、（3，2）两个点，所以）两个点，所以a1,1存放两个点中的任意一个即可。递推结束以后，如果存放两个点中的任意一个即可。递推结束以后，如果a1,1值为值为(0,0)说说明不存在路径，否则明不存在路径，否则a1,1值就是马走下一步的坐标，以此递推输出路径。值就是马走下一步的坐标，以此递推输出路径。-1,-14,44,42,3constdx:array1.4ofinteger=(2,2,1,1);dy:array1.4ofinteger=(1,-1,2,-2);typemap=record
66、x,y:integer;end;vari,j,n,m,k:integer;a:array0.50,0.50ofmap;beginread(n,m);fillchar(a,sizeof(a),0);an,m.x:=-1;an,m.y:=-1;标记为终点标记为终点fori:=ndownto2do倒推倒推forj:=mdownto1doifai,j.x0thenfork:=1to4dobeginai-dxk,j-dyk.x:=i;ai-dxk,j-dyk.y:=j;end;ifa1,1.x=0thenwriteln(no)elsebegin存在路径存在路径i:=1;j:=1;write(,i,j,)
67、;whileai,j.x-1dobegink:=i;i:=ai,j.x;j:=ak,j.y;write(-(,i,j,);end;end;end.乘火车乘火车火车从始发站（称为第火车从始发站（称为第1站）开出，在始发站上车的人数为站）开出，在始发站上车的人数为a，然后到达第然后到达第2站，在第站，在第2站有人上、下车，但上、下车的人数相同，站有人上、下车，但上、下车的人数相同，因此在第因此在第2站开出时（即在到达第站开出时（即在到达第3站之前）车上的人数保持为站之前）车上的人数保持为a人。人。从第从第3站起（包括第站起（包括第3站）上、下车的人数有一定规律：上车的人数站）上、下车的人数有一定规
68、律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：站），都满足此规律。现给出的条件是：共有共有n个车站，始发站上车的人数为个车站，始发站上车的人数为a，最后一站下车的人数是，最后一站下车的人数是m（全部下车）。试问第（全部下车）。试问第x站开出时车上的人数是多少？站开出时车上的人数是多少？输入文件输入文件chc.in：一行四个整数：一行四个整数a，n，m和和x（中间用空格隔开）（中间用空格隔开）输出文件输出文件chc.out：一行一个
69、整数（从：一行一个整数（从x站开出时车上的人数）站开出时车上的人数）样例样例:chc.in46324chc.out18分析：分析：设设upi为为i站的上车人数、站的上车人数、downi为为i站的下车人数、站的下车人数、pi为为i站开出时车站开出时车上的人数（上的人数（1in）。初始时）。初始时up1=p1=a，down1=0。依次枚举第依次枚举第2站的上车人数为站的上车人数为1，2，设第设第2站的上车人数为站的上车人数为kup2=down2=k，p2=p1+up2-down2=a按照下式递推第按照下式递推第3站站第第n-1站的车上人数站的车上人数upi=upi-1+upi-2downi=upi
70、-1pi=pi-1+upi-downi=pi-1+upi-2(3in-1)计算从计算从x站开出时车上的人数站开出时车上的人数若若pn-1=m，则输出，则输出px；否则；否则kk+1，返回，返回，直至，直至pn-1m为为止。因为止。因为p相对相对k是递增的，因此在当前是递增的，因此在当前pn-1m的情况下，无论的情况下，无论k值怎值怎样增加也不会使得样增加也不会使得pn-1=m的。的。constmaxn=100;vara，n，m，x，k，i：integer；p，down，up：array1.maxnofinteger；beginreadln(a，n，m，x)；fillchar(p，sizeof(
71、p)，0)；up1:=a；down1:=0；p1:=a；k:=1;repeatup2:=k；down2:=k；p2:=p1；枚举第枚举第2站的上车人数、下车人数和车上人数站的上车人数、下车人数和车上人数fori:=3ton-1dobegin递推第递推第3站站第第n-1站的车上人数站的车上人数upi:=upi-1+upi-2；downi:=upi-1；pi:=pi-1+upi-2；end；ifpn-1=mthen若若n站下车的人数为站下车的人数为m，则输出从，则输出从x站开出时车上的人数，并退出站开出时车上的人数，并退出beginwriteln(px)；exit；end；k:=k+1；第第2站上车人数增加站上车人数增加1untilpn-1m；直至无法满足此规律为止直至无法满足此规律为止end.结束结束
