noip讲义4递推法.ppt

《noip讲义4递推法.ppt》由会员分享，可在线阅读，更多相关《noip讲义4递推法.ppt（87页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、采用具体化、特殊化的方法寻找规律采用具体化、特殊化的方法寻找规律 平面上平面上n条直线，任两条不平行，任三条不共点，问条直线，任两条不平行，任三条不共点，问这这n条直线把这平面划分为多少个部分？条直线把这平面划分为多少个部分？ 设这设这n条直线把这平面划分成条直线把这平面划分成Fn个部分。个部分。 先用具体化特殊化的方法寻找规律，如图所示，易知先用具体化特殊化的方法寻找规律，如图所示，易知的前几项分别为的前几项分别为 这些数字之间的规律性不很明显，这些数字之间的规律性不很明显， 较难用不完全归纳法较难用不完全归纳法猜出猜出Fn的一般表达式。但我们可以分析前后项之间的递推关系，的一般表达式。但我

2、们可以分析前后项之间的递推关系，因为这些图形中，后一个都是由前一个添加一条直线而得到的，因为这些图形中，后一个都是由前一个添加一条直线而得到的，添加一条直线便增加若干个区域。添加一条直线便增加若干个区域。 一般地，设原来的符合题意的一般地，设原来的符合题意的n-1条直线把这平面分成条直线把这平面分成 个区域，再增加一条直线个区域，再增加一条直线l，就变成，就变成n条直线，按题设条条直线，按题设条件，这件，这l必须与原有的必须与原有的n-1条直线各有一个交点条直线各有一个交点, 且这且这n-1个交点个交点及原有的交点互不重合。这及原有的交点互不重合。这n-1个交点把个交点把l划分成划分成n个区间

3、，每个区间，每个区间把所在的原来区域一分为二，所以就相应比原来另增个区间把所在的原来区域一分为二，所以就相应比原来另增了了n个区域，即：个区域，即： 这样，我们就找到了一个从这样，我们就找到了一个从Fn-1到到Fn的的递推式，再加上的的递推式，再加上已知的初始值已知的初始值F1=2，就可以通过，就可以通过n-1步可重复的简单运算推导步可重复的简单运算推导出出Fn的值。的值。var a,i,n:longint;begin read(n); a:=2; for i:=2 to n do a:=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=3=3A An n1 1 在在 n

7、n的正方形钉子板上（的正方形钉子板上（n是钉子板每边上的是钉子板每边上的钉子数），求连接任意两个钉子所得到的不同长度的钉子数），求连接任意两个钉子所得到的不同长度的线段种数线段种数.Fn=Fn-1+n 如图如图1，是棱长为，是棱长为a的小正方体，图的小正方体，图2，图，图3由这样的小正由这样的小正方体摆放而成。按照这样的方法继续摆放，自上而下分别叫方体摆放而成。按照这样的方法继续摆放，自上而下分别叫第一层、第二层、第一层、第二层、第、第n层，第层，第n层的小正方体的个数记层的小正方体的个数记为为sn。请写出求。请写出求sn的递推公式。的递推公式。1 3 6 10nssnn1 如图，有边长为如图

8、，有边长为1的等边三角形卡片若干张，使用这些的等边三角形卡片若干张，使用这些三角形卡片拼出边长分别是三角形卡片拼出边长分别是2，3，4，的等边三角形（如的等边三角形（如图所示）根据图形推断，写出求每个等边三角形所用卡图所示）根据图形推断，写出求每个等边三角形所用卡片总数片总数sn的递推公式的递推公式 4 9 16 25 364)2( 1221snnssnn 为庆祝为庆祝“五五一一”国际劳动节，市政府决定在人民广场上增国际劳动节，市政府决定在人民广场上增设一排灯花，其设计由以下图形逐步演变而成，其中圆圈代表设一排灯花，其设计由以下图形逐步演变而成，其中圆圈代表灯花中的灯泡，灯花中的灯泡，n代表第

9、代表第n次演变过程，次演变过程，s代表第代表第n次演变后的灯次演变后的灯泡的个数。仔细观察下列演变过程，当泡的个数。仔细观察下列演变过程，当n=6时，时，s=_。94 2n1nn23ssSn=2sn-1+2Sn=3sn-1-2sn-2 某公共汽车线路上共有某公共汽车线路上共有15个车站（包括起点站和终点个车站（包括起点站和终点站）。在每个站上车的人中，恰好在以后各站下去一个。要站）。在每个站上车的人中，恰好在以后各站下去一个。要使行驶过程中每位乘客都有座位，车上至少要备有多少个座使行驶过程中每位乘客都有座位，车上至少要备有多少个座位？位？ 从表中可以看出车上人数最多是从表中可以看出车上人数最多

10、是56人，所以车上人，所以车上至少要准备至少要准备56个座位。个座位。练习练习1 将一张长方形的纸对折，可得到一条折痕，继续对将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到条折痕，那么对折三次后，可得到条折痕，那么对折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.var f,s,i,n,j:longint;

11、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.Fn=Fn-1+2n-1 var加入高精度运算加入高精度运算 a,b:array1.100 of integer; i,j,n:integer;begin readln(n); a100:=1 ;n=1时时 b100:=1;20=1 for i:= 2 to n do begin for j:= 100 downto 1 do bj:=bj*2;递推出递推出2i-1 for j:= 10

12、0 downto 2 do if bj=10 then begin bj-1:=bj-1+bj div 10 ; bj:=bj mod 10; end; for j:= 100 downto 1 do begin aj:=aj+bj; if aj=10 then begin aj-1:=aj-1+aj div 10 ; aj:=aj mod 10; end; end; end; j:=1; while aj=0 do j:=j+1; for i:= j to 100 do write(ai) ; end.练习练习2 如图如图,第一次把三角形剪去一个角后第一次把三角形剪去一个角后,图中最多有四个

13、图中最多有四个角角,第二次再把新产生的角各剪一刀第二次再把新产生的角各剪一刀,如此下去如此下去,每一次每一次都是把新产生的角各剪一刀都是把新产生的角各剪一刀,则第则第n次剪好后次剪好后,图中图中最多最多有有多少个角多少个角? 4 6 10 18 34 Fn=Fn-1+2n-1var 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:array1.100 of longint; i,j,

14、n:longint;begin readln(n); a100:=4 ; b100:=1; for i:= 2 to n do begin for j:= 100 downto 1 do bj:=bj*2; for j:= 100 downto 2 do if bj=10 then begin bj-1:=bj-1+bj div 10 ; bj:=bj mod 10; end; for j:= 100 downto 1 do begin aj:=aj+bj; if aj=10 then begin aj-1:=aj-1+aj div 10 ; aj:=aj mod 10; end; end;

15、end; j:=1; while aj=0 do j:=j+1; for i:= j to 100 do write(ai) ;end.练习练习3 下图中把大正方形各边平均分成了下图中把大正方形各边平均分成了5份，此时有份，此时有55个正个正方形。如果把正方形各边平均分成方形。如果把正方形各边平均分成n份，那么得到的正方形份，那么得到的正方形总数为多少？总数为多少？52+42+32+22+12=55n2+(n-1)2+(n-2)2+22+1Fn=Fn-1+n2var a,i,n:longint;begin read(n); a:=1; for i:=2 to n do a:=a+i*i; wr

16、iteln(a);end.Var 加入高精度运算加入高精度运算 a:array1.25 of longint; i,j,k,x,n:longint;begin readln(n); a25:=1;n=1时时 for i:= 2 to n do begin x:=i*i; for j:= 25 downto 1 do begin aj:=aj+x mod 10; if aj=10 then begin aj:=aj-10 ; aj-1:=aj-1+1; end; x:=x div 10; end; end; j:=1; while aj=0 do j:=j+1; for i:= j to 25

17、do write(ai); end.练习练习4 如图，由等圆组成的一组图中，第如图，由等圆组成的一组图中，第1个图由个图由1个圆组成，个圆组成，第第2个图由个图由7个圆组成，第个圆组成，第3个图由个图由19个圆组成，个圆组成，按照，按照这样的规律排列下去，则第这样的规律排列下去，则第9个图形由个图形由_个圆组成。个圆组成。 217可得递推公式可得递推公式:Fn= Fn-1+6*（n1）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:

18、array1.50 of longint; i,j,k,x,n:longint;begin readln(n); a50:=1; for i:= 2 to n do begin x:=(i-1)*6; for j:= 50 downto 1 do begin x:=x+aj; aj:=x mod 10 ; x:=x div 10; end; end; j:=1; while aj=0 do j:=j+1; for i:= j to 50 do write(ai);end.练习练习5 已知三角形已知三角形ABC的面积为的面积为10，延长边，延长边BC到点到点D，使，使BC=CD，延长边延长边CA

19、到点到点E，使，使CA=AE，延长边，延长边AB到点到点F，使，使AB=BF，连，连结结DE,EF,FD,得到三角形得到三角形DEF,并记图中阴影部分面积为并记图中阴影部分面积为S1,此时我此时我们称三角形们称三角形ABC向外扩展了一次向外扩展了一次.求经过求经过N次扩展后图中阴影部分次扩展后图中阴影部分的面积的面积Sn.Fn=7*Fn-1 ( Fn为第为第n次扩展后整个三角形的面积次扩展后整个三角形的面积 )F0=10Sn=Fn-Fn-1const max=100;var f1,f2,s:array1.max of longint; i,j,k,l,n:longint;begin readl

20、n(n); f1max:=0 ; f1max-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+f1j*7; f1j:=k mod 10; k:=k div 10; end; end; for i:= max downto 1 do 相减相减 begin if f1if2i then begin f1i:=f1i+10; f1i-1:=f1i-1-1; end; si:=f1i-f2i; end; j:=1; while sj=0 do j:=j+1; for i:= j

21、 to max do write(si) ; end.Hanoi双塔双塔问题问题 给定给定A、B、C三根足够长的细柱，在三根足够长的细柱，在A柱上放有柱上放有2n个中个中 间有孔的圆盘，共有间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情的情形）。现要将这些圆盘移到形）。现要将这些圆盘移到C柱上，在移动过程中可放在柱上，在移动过程中可放在B柱柱上暂存。要求：上暂存。要求： （1）每次只能移动一个圆盘；）每次只能移动一个圆盘； （2）A、B、C三根细柱上的圆盘都要

22、保持上小下大的顺三根细柱上的圆盘都要保持上小下大的顺序；序； 任务：设任务：设An为为2n个圆盘完成上述任务所需的最少移动次个圆盘完成上述任务所需的最少移动次数，对于输入的数，对于输入的n，输出，输出An。 输入文件输入文件hanoi.in为一个正整数为一个正整数n，表示在，表示在A柱上放有柱上放有2n个圆盘。个圆盘。 输出文件输出文件hanoi.out仅一行，包含一个正整数仅一行，包含一个正整数，为完成上为完成上述任务所需的最少移动次数述任务所需的最少移动次数An。 【样例【样例1】hanoi.inhanoi.out12【样例【样例2】hanoi.inhanoi.out26【限制】【限制】

23、对于对于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 then f:=true; if f then write(ai); end; close(input); close(output);end. 在上面的一些例题中，递推过程中的某个状态在上面的一些例题中，递推过程中的某个状态只与前面的一个状态有关，递推关系并不复杂。如只与前面的一个状态有关，递推关系并不

24、复杂。如果在递推中的某个状态与前面的几个状态、甚至所果在递推中的某个状态与前面的几个状态、甚至所有状态都有关，就不容易找出递推关系式，这就需有状态都有关，就不容易找出递推关系式，这就需要我们对实际问题进行分析与归纳，从中找到突破要我们对实际问题进行分析与归纳，从中找到突破口，总结出递推关系式。口，总结出递推关系式。 意大利著名数学家斐波那契在研究兔子繁殖问题时，发现意大利著名数学家斐波那契在研究兔子繁殖问题时，发现有这样一组数：有这样一组数：1，1，2，3，5，8，13，其中从第三个数，其中从第三个数起，每一个数都等于它前面两上数的和。现以这组数中的各个起，每一个数都等于它前面两上数的和。现以

25、这组数中的各个数作为正方形的边长构造如下正方形：数作为正方形的边长构造如下正方形： 1 1 2 3 5 . 再分别依次从左到右取再分别依次从左到右取2个、个、3个、个、4个、个、5个正方形拼成个正方形拼成如下矩形并记为如下矩形并记为、若按此规律继续作矩形，则序号为若按此规律继续作矩形，则序号为的矩形周长是。的矩形周长是。 466 【问题描述】【问题描述】 一只蜜蜂在上图所示的数字蜂房上爬动一只蜜蜂在上图所示的数字蜂房上爬动,已知它只已知它只能从标号小的蜂房爬到标号大的相邻蜂房能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：现在问你：蜜蜂从蜂房蜜蜂从蜂房M开始爬到蜂房开始爬到蜂房N（MN），有多

26、少种爬），有多少种爬行路线？行路线？ 【输入格式】【输入格式】 输入输入M，N的值。的值。(1=M,N0），求出铺法总数的递推公），求出铺法总数的递推公式。式。F(1)=1F(2)=2F(n)=F(n-2)+F(n-1) (n=3) 如果有如果有n元钱元钱,每天去购买下列三种商品之一每天去购买下列三种商品之一:蔬菜要蔬菜要用用1元钱元钱,猪肉要用猪肉要用2元钱元钱,鸡蛋要用元钱用鸡蛋要用元钱用An表示把表示把这这n元钱用完的所有可能的用法的总数元钱用完的所有可能的用法的总数如果第一天买蔬菜，则用去元钱，还剩如果第一天买蔬菜，则用去元钱，还剩n-1元钱，元钱， 这这n-1元钱的用法有元钱的用法有

27、n-1种；种；如果第一天买猪肉，则用去元钱，还剩如果第一天买猪肉，则用去元钱，还剩n-元钱，元钱， 这这n-元钱的用法有元钱的用法有n-2种；种； 如果第一天买鸡蛋，则用去元钱，还剩如果第一天买鸡蛋，则用去元钱，还剩n-元钱，元钱， 这这n-元钱的用法有元钱的用法有n-2种；种； 所以，所以，n=n-1+2n-2 有排成一行的个方格，用红、黄、蓝三色涂每个格子，有排成一行的个方格，用红、黄、蓝三色涂每个格子，每格涂一色，要求任何相邻的格不同色，且首尾两格也不同每格涂一色，要求任何相邻的格不同色，且首尾两格也不同色。问有多少种涂法？色。问有多少种涂法？ 解：解：设共有设共有n种涂法，易见种涂法，

28、易见1，2，3，且当，且当时，将时，将个格子依次编号后，格与格（个格子依次编号后，格与格（n-1）不相邻。）不相邻。情形情形：格（：格（n-1）涂色与格不同，此时格只有一色可涂，且前（）涂色与格不同，此时格只有一色可涂，且前（n-1）格满足首尾两格不同色，故有格满足首尾两格不同色，故有n-1种涂色方法。种涂色方法。情形情形：格（：格（n-1）涂色与格相同，此时格（）涂色与格相同，此时格（n-2）与格涂色必然不同，）与格涂色必然不同，不然，格（不然，格（n-1）与（）与（n-2）相同，于是前（）相同，于是前（n-2）格有）格有n-2种涂色法。因为格种涂色法。因为格与格不同色，有两种涂色法，故共有

29、与格不同色，有两种涂色法，故共有n-2种涂色法。种涂色法。综上，可得综上，可得nn-1n-2（）按前按前n-1格首尾关系讨论格首尾关系讨论 错位排列错位排列 五个人排成一列，重新站队时，各人都不站在原来的位置上，那么不同的五个人排成一列，重新站队时，各人都不站在原来的位置上，那么不同的站队方式共有站队方式共有( ) （A）60种种 （B）44种种 （C）36种种 （D）24种种 解：首先我们把人数推广到解：首先我们把人数推广到n个人，即个人，即n个人排成一列，重新站队时，各人都不个人排成一列，重新站队时，各人都不站在原来的位置上。设满足这样的站队方式有站在原来的位置上。设满足这样的站队方式有A

30、n种，现在我们通过合理分步，恰当种，现在我们通过合理分步，恰当分类分类来来找出递推关系：找出递推关系： 第一步第一步：第一个人不站在原来的第一个位置，有：第一个人不站在原来的第一个位置，有n-1种站法。种站法。 第二步第二步：假设第一个人站在第：假设第一个人站在第2个位置，则第二个人的站法又可以分为两类：个位置，则第二个人的站法又可以分为两类：第一类第一类，第二个人恰好站在第一个位置，则余下的，第二个人恰好站在第一个位置，则余下的 n-2个人有个人有An-2种站队方式；种站队方式；第二第二类类，第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不，第二个人不站在第一个位置，则就

31、是第二个人不站在第一个位置，第三个人不站在第三个位置，第四个人不站在第四个位置，站在第三个位置，第四个人不站在第四个位置，第，第n个人不站在第个人不站在第n个位置，个位置，所以有所以有An-1种站队方式。种站队方式。 由分步计数原理和分类计数原理，我们便得到了数列由分步计数原理和分类计数原理，我们便得到了数列 的递推关系式：的递推关系式： ，显然，显然 ，再由递推关系有，再由递推关系有，na)(1(12nnnaana1, 021aa9,243aa445a 在书架上放有编号为在书架上放有编号为1 ，2 ，n的的n本书。现将本书。现将n本书全部取下然后再放回去，当放回去时要求每本书本书全部取下然后

32、再放回去，当放回去时要求每本书都不能放在原来的位置上。都不能放在原来的位置上。 例如：例如：n = 3时：时： 原来位置为：原来位置为：1 2 3 放回去时只能为：放回去时只能为：3 1 2 或或 2 3 1 这两种这两种 问题：求当问题：求当n = 5时满足以上条件的放法共有多少时满足以上条件的放法共有多少种？种？染色问题染色问题 用用4种不同颜色涂四边形的种不同颜色涂四边形的4个顶点，要求每点染一种颜个顶点，要求每点染一种颜色，相邻的顶点染不同的颜色，则不同的染色方法有色，相邻的顶点染不同的颜色，则不同的染色方法有( )（A）84种种（B）72种种（C）48种种（D）24种种AVar i,

33、j,k,m,n:longint; a:array1.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是颜色数是颜色数 a3:=jc(m) div jc(m-3);初值初值 for i:= 4 to n do begin j:=1; for k:= 1 to i-1 do j:=j*(m-1); ai:=m*j-ai-1 ; 递推公式递推公式 end; w

34、riteln(an);end.)!3(!33mmAam1) 1(ima3:=m*(m-1)*(m-2)如图，一个地区分为如图，一个地区分为5个行政区域，现给地图着色，要求个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有四种颜色可供选择，则相邻区域不得使用同一颜色，现有四种颜色可供选择，则不同的着色方法共有不同的着色方法共有 种。种。 图中图中2、3、4、5四个区域围成一个四边形，因此可以四个区域围成一个四边形，因此可以把它们看成是一个四边形的把它们看成是一个四边形的4个顶点，而区域个顶点，而区域1就是这个四就是这个四边形对角线的交点。边形对角线的交点。 第一步，先涂区域第一步，先涂

35、区域1，有，有4种涂法。种涂法。 第二步，由于区域第二步，由于区域1跟其余四个区域都相邻，因此涂跟其余四个区域都相邻，因此涂1的颜色不能用来涂其余的四个区域，因此第二步相当于用的颜色不能用来涂其余的四个区域，因此第二步相当于用3种颜色来涂一个四边形的四个顶点，不难得出种颜色来涂一个四边形的四个顶点，不难得出 所以，所以，由分步计数原理，得出共有由分步计数原理，得出共有 种涂法。种涂法。 1123nnnaa6333 Aa1823334aa72184 某城市在中心广场建造一个花圃，花圃分成某城市在中心广场建造一个花圃，花圃分成6个部分个部分(如如图图)，现要栽种，现要栽种4种不同颜色的花，每部分栽

36、种一种且相邻部种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法共有分不能栽种同样颜色的花，不同的栽种方法共有 种。种。 1206333 Aa1823334aa30184823445aa430=120传球传球问题问题 4个人进行篮球训练，互相传球接球，要求每个人接球个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？五次传球后，球又回到甲手中，问有多少种传球方式？60分析分析 :设第设第n次传球后，球又回到甲手中的传球方式有次传

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

38、不在甲手中，第n次持球人再将球传给甲，有次持球人再将球传给甲，有an种传法。种传法。 根据加法原理，有根据加法原理，有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种。种。var a:array1.100 of longint; n

39、,m,i,j:longint;begin readln(n,m); a1:=0; j:=1; for i:= 2 to m do begin j:=j*(n-1); 先求出先求出(n-1)i-1 ai:=j-ai-1; end; writeln(am);end.var 加入高精度运算加入高精度运算 a:array1.100,1.100 of integer; s:array1.100 of integer; i,j,t,k,n,m:longint;begin readln(n,m); a1,100:=0 ; s100:=1; for i:= 2 to m do begin for j:= 10

40、0 downto 1 do sj:=sj*(n-1); for j:= 100 downto 1 do if sj9 then begin sj-1:=sj-1+sj div 10; sj:= sj mod 10; end; for j:= 100 downto 1 do ai,j:=sj-ai-1,j; for j:= 100 downto 1 do if ai,j0 then begin ai,j-1:=ai,j-1-1; ai,j:=ai,j+10; end; end; j:=1; while am,j=0 do j:=j+1; for i:= j to 100 do write(am,

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

42、如图所示，我们以如图所示，我们以p1pn这条边为基准边，再找这条边为基准边，再找pk来构成三角形，来构成三角形，则原凸则原凸n边形被剖解成了边形被剖解成了p1pkpn和两个凸多边形，其中一个是和两个凸多边形，其中一个是由由p1,p2,pk构成的凸构成的凸k边形，另一个是由边形，另一个是由pk,pk+1,pn构成的凸构成的凸n-k+1边形，根据乘法原理，选择边形，根据乘法原理，选择pk这个顶点的分解方案为这个顶点的分解方案为 种。而种。而k可以选可以选2到到n-1，所以根据加法原理，得出总，所以根据加法原理，得出总的方案数为的方案数为 注意，就这个递推关系而言，临界值应为注意，就这个递推关系而言

43、，临界值应为C2=1，而不是，而不是C3=1，否则递推关系就得不到正确解，这与原问题的实际情况，否则递推关系就得不到正确解，这与原问题的实际情况可能不符（即两边形），其实这只是理解上的差异可能不符（即两边形），其实这只是理解上的差异1knkCC1knkCC12nknCP1PnP2P3PkPn-1Pn-2const max=21;var c:array2.max of longint; n,i,k:integer; total:longint;begin readln(n); c2:=1; for i:=3 to n do begin ci:=0; for k:=2 to i-1 do ci:=

44、ci+ck*ci-k+1; end; writeln(cn);end.求路径总数求路径总数下图是某居民小区道路图，小明每天由家（点）到学校（点），下图是某居民小区道路图，小明每天由家（点）到学校（点），他只沿道路向上或向右行走，那么他最多有（）天走不同线路？他只沿道路向上或向右行走，那么他最多有（）天走不同线路？1015212836 454 1020 355684120 1655 1535 70126 210 330 495var i,j,n,m:integer; a:array1.20,1.20 of longint;begin read(n,m); fillchar(a,sizeof(a)

45、,0); for i:=1 to n do aI,1:=1; for j:=1 to m do a1,j:=1; for i:=2 to n do for j:=2 to m do aI,j:=aI,j-1+ai-1,j; writeln(an,m);end.要想到达坐标为（要想到达坐标为（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输出：输出

46、：495街道路径街道路径 设有一个设有一个NM（1=N=50，1=M=50）的街）的街道，规定行人从道，规定行人从A(1,1)出发，在街道上出发，在街道上只能向东或北行走只能向东或北行走。 若在此街道中，设置一个矩形障碍区域（包括围住该若在此街道中，设置一个矩形障碍区域（包括围住该区域的的街道）不让行人通行，如上图中用区域的的街道）不让行人通行，如上图中用“”表示的表示的部分。此矩形障碍区域用部分。此矩形障碍区域用2对顶点坐标给出，如上图中的对顶点坐标给出，如上图中的2对顶点坐标为对顶点坐标为(2，2),(8，4)，此时从，此时从A出发到达出发到达B的路径的路径有两条。有两条。 现给出现给出N

47、、M，同时再给出此街道中的矩形障碍区域的，同时再给出此街道中的矩形障碍区域的2对顶点坐标对顶点坐标(x1,y1)，（，（x2,y2），请求出此时所有从），请求出此时所有从A出出发到达发到达B的路径的条数。的路径的条数。 由于在街上只能向东或北方向行走，因此要想达到坐标由于在街上只能向东或北方向行走，因此要想达到坐标为（为（i,j）的顶点的话，必定要经过坐标为（）的顶点的话，必定要经过坐标为（i-1,j）的顶点）的顶点或坐标为（或坐标为（i,j-1）的顶点，假设从起始顶点到达坐标为）的顶点，假设从起始顶点到达坐标为（i,j）的顶点的路径总数为）的顶点的路径总数为ai,j，则，则ai,j= ai-

48、1,j +ai,j-1。因此我们可以采用逐。因此我们可以采用逐行行递推的方法来求出从起递推的方法来求出从起始顶点到达任意一个顶点的路径总数。始顶点到达任意一个顶点的路径总数。var n,m,i,j,x1,x2,y1,y2:integer; a:array1.50,1.50 of longint; b:array1.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

49、for j:=x1 to x2 do bi,j:=false; for i:=1 to m do begin if not(bi,1) then break ; ai,1:=1; end; for j:=1 to n do begin if not(b1,j) then break ; a1,j:=1; end; for i:=2 to m do for j:=2 to n do if bi,j then ai,j:=ai-1,j+ai,j-1; write(am,n);end.有可能障碍区域靠边有可能障碍区域靠边如输入如输入9 52 8 4应输出应输出11 Var加入高精度运算加入高精度运算

50、 n,m,i,j,x1,x2,y1,y2,k,g:integer; a:array1.50,1.50,1.30 of longint; b:array1.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 bi,j:=false; for i:=1 to m do begin if not(bi,1) then break; ai,1,1:=1; e