基本算法遞推法實(shí)例

1、關(guān)于基本算法遞推法實(shí)例第1頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四采用具體化、特殊化的方法尋找規(guī)律 平面上n條直線，任兩條不平行，任三條不共點(diǎn)，問(wèn)這n條直線把這平面劃分為多少個(gè)部分？第2頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 設(shè)這n條直線把這平面劃分成Fn個(gè)部分。 先用具體化特殊化的方法尋找規(guī)律，如圖所示，易知的前幾項(xiàng)分別為 這些數(shù)字之間的規(guī)律性不很明顯， 較難用不完全歸納法猜出Fn的一般表達(dá)式。但我們可以分析前后項(xiàng)之間的遞推關(guān)系，因?yàn)檫@些圖形中，后一個(gè)都是由前一個(gè)添加一條直線而得到的，添加一條直線便增加若干個(gè)區(qū)域。 第3頁(yè)，共86頁(yè)，2022年，5月20日，

2、6點(diǎn)10分，星期四 一般地，設(shè)原來(lái)的符合題意的n-1條直線把這平面分成 個(gè)區(qū)域，再增加一條直線l，就變成n條直線，按題設(shè)條件，這l必須與原有的n-1條直線各有一個(gè)交點(diǎn), 且這n-1個(gè)交點(diǎn)及原有的交點(diǎn)互不重合。這n-1個(gè)交點(diǎn)把l劃分成n個(gè)區(qū)間，每個(gè)區(qū)間把所在的原來(lái)區(qū)域一分為二，所以就相應(yīng)比原來(lái)另增了n個(gè)區(qū)域，即： 這樣，我們就找到了一個(gè)從Fn-1到Fn的的遞推式，再加上已知的初始值F1=2，就可以通過(guò)n-1步可重復(fù)的簡(jiǎn)單運(yùn)算推導(dǎo)出Fn的值。var a,i,n:longint;begin read(n); a:=2; for i:=2 to n do a:=a+i; writeln(a);end.

3、第4頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 在平面內(nèi)畫五條直線和一個(gè)圓，最多能把平面分成多少部分？ 第5頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四平面上有8個(gè)圓，最多能把平面分成幾部分？ 123456Fn=Fn-1+2 (n-1) 第6頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 圓周上兩個(gè)點(diǎn)將圓周分為兩半，在這兩點(diǎn)上寫上數(shù)1；然后將兩段半圓弧對(duì)分，在兩個(gè)分點(diǎn)上寫上相鄰兩點(diǎn)上的數(shù)之和；再把4段圓弧等分，在分點(diǎn)上寫上相鄰兩點(diǎn)上的數(shù)之和，如此繼續(xù)下去，問(wèn)第6步后，圓周上所有點(diǎn)上的數(shù)之和是多少？ 第7頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四

4、分析:先可以采用作圖嘗試尋找規(guī)律。第一步：圓周上有兩個(gè)點(diǎn)，兩個(gè)數(shù)的和是1+1=2；第二步：圓周上有四個(gè)點(diǎn)，四個(gè)數(shù)的和是1+1+2+2=6；增加數(shù)之和恰好是第一步圓周上所有數(shù)之和的2倍。第三步：圓周上有八個(gè)點(diǎn)，八個(gè)數(shù)的和是1+1+2+2+3+3+3+3=18，增加數(shù)之和恰好是第二步數(shù)圓周上所有數(shù)之和的2倍。第四步：圓周上有十六個(gè)點(diǎn)，十六個(gè)數(shù)的和1+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5=54，增加數(shù)之和恰好是第三步數(shù)圓周上所有數(shù)之和的2倍。這樣我們可以知道，圓周上所有數(shù)之和是前一步圓周上所有數(shù)之和的3倍。設(shè)An為第n步后得出的圓周上所有數(shù)之和，則An=3An1第8頁(yè)，共86頁(yè)

5、，2022年，5月20日，6點(diǎn)10分，星期四 在nn的正方形釘子板上（n是釘子板每邊上的釘子數(shù)），求連接任意兩個(gè)釘子所得到的不同長(zhǎng)度的線段種數(shù).Fn=Fn-1+n第9頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 如圖1，是棱長(zhǎng)為a的小正方體，圖2，圖3由這樣的小正方體擺放而成。按照這樣的方法繼續(xù)擺放，自上而下分別叫第一層、第二層、第n層，第n層的小正方體的個(gè)數(shù)記為sn。請(qǐng)寫出求sn的遞推公式。1 3 6 10第10頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 如圖，有邊長(zhǎng)為1的等邊三角形卡片若干張，使用這些三角形卡片拼出邊長(zhǎng)分別是2，3，4，的等邊三角形（如圖所示）根據(jù)

6、圖形推斷，寫出求每個(gè)等邊三角形所用卡片總數(shù)sn的遞推公式 4 9 16 25 36第11頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 為慶祝“五一”國(guó)際勞動(dòng)節(jié)，市政府決定在人民廣場(chǎng)上增設(shè)一排燈花，其設(shè)計(jì)由以下圖形逐步演變而成，其中圓圈代表燈花中的燈泡，n代表第n次演變過(guò)程，s代表第n次演變后的燈泡的個(gè)數(shù)。仔細(xì)觀察下列演變過(guò)程，當(dāng)n=6時(shí)，s=_。94 Sn=2sn-1+2Sn=3sn-1-2sn-2第12頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 某公共汽車線路上共有15個(gè)車站（包括起點(diǎn)站和終點(diǎn)站）。在每個(gè)站上車的人中，恰好在以后各站下去一個(gè)。要使行駛過(guò)程中每位乘客都

7、有座位，車上至少要備有多少個(gè)座位？ 從表中可以看出車上人數(shù)最多是56人，所以車上至少要準(zhǔn)備56個(gè)座位。第13頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四練習(xí)1 將一張長(zhǎng)方形的紙對(duì)折，可得到一條折痕，繼續(xù)對(duì)折，對(duì)折時(shí)每次折痕與上次的折痕保持平行，連續(xù)對(duì)折三次后，可得到條折痕，那么對(duì)折n次，可得到幾條折痕？第14頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 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.第15頁(yè)，共86頁(yè)，2022年，5

8、月20日，6點(diǎn)10分，星期四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.Fn=Fn-1+2n-1 第16頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四var加入高精度運(yùn)算 a,b:array1.100 of integer; i,j,n:integer;begin readln(n); a100:=1 ;n=1時(shí) b100:=1;20=1 for i:= 2 to n do b

9、egin for j:= 100 downto 1 do bj:=bj*2;遞推出2i-1 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; end; j:=1; while aj=0 do j:=j+1; for i:= j to 100 do write

10、(ai) ; end.第17頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四練習(xí)2 如圖,第一次把三角形剪去一個(gè)角后,圖中最多有四個(gè)角,第二次再把新產(chǎn)生的角各剪一刀,如此下去,每一次都是把新產(chǎn)生的角各剪一刀,則第n次剪好后,圖中最多有多少個(gè)角? 4 6 10 18 34 Fn=Fn-1+2n-1第18頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四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; write

11、ln(f);end.第19頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四var a,b:array1.100 of longint; i,j,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:

12、=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.第20頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四練習(xí)3 下圖中把大正方形各邊平均分成了5份，此時(shí)有55個(gè)正方形。如果把正方形各邊平均分成n份，那么得到的正方形總數(shù)為多少？52+42+32+22+12=55n2+(n-1)2+(n-2)2+22+1Fn=Fn-1+n2var a,i,n:longin

13、t;begin read(n); a:=1; for i:=2 to n do a:=a+i*i; writeln(a);end.第21頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四Var 加入高精度運(yùn)算 a:array1.25 of longint; i,j,k,x,n:longint;begin readln(n); a25:=1;n=1時(shí) 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+

14、1; end; x:=x div 10; end; end; j:=1; while aj=0 do j:=j+1; for i:= j to 25 do write(ai); end.第22頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四練習(xí)4 如圖，由等圓組成的一組圖中，第1個(gè)圖由1個(gè)圓組成，第2個(gè)圖由7個(gè)圓組成，第3個(gè)圖由19個(gè)圓組成，按照這樣的規(guī)律排列下去，則第9個(gè)圖形由_個(gè)圓組成。 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); wri

15、teln(a);end.第23頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四var 加入高精度運(yùn)算 a: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.第24頁(yè)，

16、共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四練習(xí)5 已知三角形ABC的面積為10，延長(zhǎng)邊BC到點(diǎn)D，使BC=CD，延長(zhǎng)邊CA到點(diǎn)E，使CA=AE，延長(zhǎng)邊AB到點(diǎn)F，使AB=BF，連結(jié)DE,EF,FD,得到三角形DEF,并記圖中陰影部分面積為S1,此時(shí)我們稱三角形ABC向外擴(kuò)展了一次.求經(jīng)過(guò)N次擴(kuò)展后圖中陰影部分的面積Sn.Fn=7*Fn-1 ( Fn為第n次擴(kuò)展后整個(gè)三角形的面積 )F0=10Sn=Fn-Fn-1第25頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四const max=100;var f1,f2,s:array1.max of longint; i,j,k,l,

17、n:longint;begin readln(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 d

18、o j:=j+1; for i:= j to max do write(si) ; end.第26頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四Hanoi雙塔問(wèn)題 給定A、B、C三根足夠長(zhǎng)的細(xì)柱，在A柱上放有2n個(gè)中 間有孔的圓盤，共有n個(gè)不同的尺寸，每個(gè)尺寸都有兩個(gè)相同的圓盤，注意這兩個(gè)圓盤是不加區(qū)分的（下圖為n=3的情形）。現(xiàn)要將這些圓盤移到C柱上，在移動(dòng)過(guò)程中可放在B柱上暫存。要求： （1）每次只能移動(dòng)一個(gè)圓盤； （2）A、B、C三根細(xì)柱上的圓盤都要保持上小下大的順序； 任務(wù)：設(shè)An為2n個(gè)圓盤完成上述任務(wù)所需的最少移動(dòng)次數(shù)，對(duì)于輸入的n，輸出An。第27頁(yè)，共86頁(yè)，2022

19、年，5月20日，6點(diǎn)10分，星期四 輸入文件hanoi.in為一個(gè)正整數(shù)n，表示在A柱上放有2n個(gè)圓盤。 輸出文件hanoi.out僅一行，包含一個(gè)正整數(shù)，為完成上述任務(wù)所需的最少移動(dòng)次數(shù)An。 【樣例1】hanoi.inhanoi.out12【樣例2】hanoi.inhanoi.out26【限制】 對(duì)于50%的數(shù)據(jù)，1=n=25 對(duì)于100%的數(shù)據(jù)，1=n9 then begin 處理進(jìn)位 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

20、 then write(ai); end; close(input); close(output);end.第30頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 在上面的一些例題中，遞推過(guò)程中的某個(gè)狀態(tài)只與前面的一個(gè)狀態(tài)有關(guān)，遞推關(guān)系并不復(fù)雜。如果在遞推中的某個(gè)狀態(tài)與前面的幾個(gè)狀態(tài)、甚至所有狀態(tài)都有關(guān)，就不容易找出遞推關(guān)系式，這就需要我們對(duì)實(shí)際問(wèn)題進(jìn)行分析與歸納，從中找到突破口，總結(jié)出遞推關(guān)系式。 第31頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 意大利著名數(shù)學(xué)家斐波那契在研究兔子繁殖問(wèn)題時(shí)，發(fā)現(xiàn)有這樣一組數(shù)：1，1，2，3，5，8，13，其中從第三個(gè)數(shù)起，每一個(gè)數(shù)都等

21、于它前面兩上數(shù)的和?，F(xiàn)以這組數(shù)中的各個(gè)數(shù)作為正方形的邊長(zhǎng)構(gòu)造如下正方形： 再分別依次從左到右取2個(gè)、3個(gè)、4個(gè)、5個(gè)正方形拼成如下矩形并記為、若按此規(guī)律繼續(xù)作矩形，則序號(hào)為的矩形周長(zhǎng)是。 466 第32頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四【問(wèn)題描述】 一只蜜蜂在上圖所示的數(shù)字蜂房上爬動(dòng),已知它只能從標(biāo)號(hào)小的蜂房爬到標(biāo)號(hào)大的相鄰蜂房,現(xiàn)在問(wèn)你：蜜蜂從蜂房M開始爬到蜂房N（MN），有多少種爬行路線？ 【輸入格式】 輸入M，N的值。(1=M,N0），求出鋪法總數(shù)的遞推公式。F(1)=1F(2)=2F(n)=F(n-2)+F(n-1) (n=3)第40頁(yè)，共86頁(yè)，2022年，5月

22、20日，6點(diǎn)10分，星期四 如果有n元錢,每天去購(gòu)買下列三種商品之一:蔬菜要用1元錢,豬肉要用2元錢,雞蛋要用元錢用An表示把這n元錢用完的所有可能的用法的總數(shù)如果第一天買蔬菜，則用去元錢，還剩n-1元錢， 這n-1元錢的用法有n-1種；如果第一天買豬肉，則用去元錢，還剩n-元錢， 這n-元錢的用法有n-2種； 如果第一天買雞蛋，則用去元錢，還剩n-元錢， 這n-元錢的用法有n-2種； 所以，n=n-1+2n-2第41頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 有排成一行的個(gè)方格，用紅、黃、藍(lán)三色涂每個(gè)格子，每格涂一色，要求任何相鄰的格不同色，且首尾兩格也不同色。問(wèn)有多少種涂法？

23、 解：設(shè)共有n種涂法，易見1，2，3，且當(dāng)時(shí)，將個(gè)格子依次編號(hào)后，格與格（n-1）不相鄰。情形：格（n-1）涂色與格不同，此時(shí)格只有一色可涂，且前（n-1）格滿足首尾兩格不同色，故有n-1種涂色方法。情形：格（n-1）涂色與格相同，此時(shí)格（n-2）與格涂色必然不同，不然，格（n-1）與（n-2）相同，于是前（n-2）格有n-2種涂色法。因?yàn)楦衽c格不同色，有兩種涂色法，故共有n-2種涂色法。綜上，可得nn-1n-2（）按前n-1格首尾關(guān)系討論 第42頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四錯(cuò)位排列 五個(gè)人排成一列，重新站隊(duì)時(shí)，各人都不站在原來(lái)的位置上，那么不同的站隊(duì)方式共有( )

24、 （A）60種 （B）44種 （C）36種 （D）24種 解：首先我們把人數(shù)推廣到n個(gè)人，即n個(gè)人排成一列，重新站隊(duì)時(shí)，各人都不站在原來(lái)的位置上。設(shè)滿足這樣的站隊(duì)方式有An種，現(xiàn)在我們通過(guò)合理分步，恰當(dāng)分類來(lái)找出遞推關(guān)系： 第一步：第一個(gè)人不站在原來(lái)的第一個(gè)位置，有n-1種站法。 第二步：假設(shè)第一個(gè)人站在第2個(gè)位置，則第二個(gè)人的站法又可以分為兩類：第一類，第二個(gè)人恰好站在第一個(gè)位置，則余下的 n-2個(gè)人有An-2種站隊(duì)方式；第二類，第二個(gè)人不站在第一個(gè)位置，則就是第二個(gè)人不站在第一個(gè)位置，第三個(gè)人不站在第三個(gè)位置，第四個(gè)人不站在第四個(gè)位置，第n個(gè)人不站在第n個(gè)位置，所以有An-1種站隊(duì)方式。

25、由分步計(jì)數(shù)原理和分類計(jì)數(shù)原理，我們便得到了數(shù)列 的遞推關(guān)系式： ，顯然 ，再由遞推關(guān)系有，第43頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 在書架上放有編號(hào)為1 ，2 ，n的n本書?，F(xiàn)將n本書全部取下然后再放回去，當(dāng)放回去時(shí)要求每本書都不能放在原來(lái)的位置上。 例如：n = 3時(shí)： 原來(lái)位置為：1 2 3 放回去時(shí)只能為：3 1 2 或 2 3 1 這兩種 問(wèn)題：求當(dāng)n = 5時(shí)滿足以上條件的放法共有多少種？第44頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四染色問(wèn)題 用4種不同顏色涂四邊形的4個(gè)頂點(diǎn)，要求每點(diǎn)染一種顏色，相鄰的頂點(diǎn)染不同的顏色，則不同的染色方法有( )（

26、A）84種（B）72種（C）48種（D）24種A第45頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四第46頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四Var i,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是頂點(diǎn)數(shù)，m是顏色數(shù) a3:=jc(m) div jc(m-3);初值 for i:= 4 to

27、 n do begin j:=1; for k:= 1 to i-1 do j:=j*(m-1); ai:=m*j-ai-1 ; 遞推公式 end; writeln(an);end.a3:=m*(m-1)*(m-2)第47頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四如圖，一個(gè)地區(qū)分為5個(gè)行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有四種顏色可供選擇，則不同的著色方法共有 種。 第48頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 圖中2、3、4、5四個(gè)區(qū)域圍成一個(gè)四邊形，因此可以把它們看成是一個(gè)四邊形的4個(gè)頂點(diǎn)，而區(qū)域1就是這個(gè)四邊形對(duì)角線的交點(diǎn)。 第一步，先

28、涂區(qū)域1，有4種涂法。 第二步，由于區(qū)域1跟其余四個(gè)區(qū)域都相鄰，因此涂1的顏色不能用來(lái)涂其余的四個(gè)區(qū)域，因此第二步相當(dāng)于用3種顏色來(lái)涂一個(gè)四邊形的四個(gè)頂點(diǎn)，不難得出 所以，由分步計(jì)數(shù)原理，得出共有 種涂法。 第49頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 某城市在中心廣場(chǎng)建造一個(gè)花圃，花圃分成6個(gè)部分(如圖)，現(xiàn)要栽種4種不同顏色的花，每部分栽種一種且相鄰部分不能栽種同樣顏色的花，不同的栽種方法共有 種。 120430=120第50頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四傳球問(wèn)題 4個(gè)人進(jìn)行籃球訓(xùn)練，互相傳球接球，要求每個(gè)人接球后馬上傳給別人，開始由甲發(fā)球，并作

29、為第一次傳球，第五次傳球后，球又回到甲手中，問(wèn)有多少種傳球方式？60第51頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四第52頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四分析 :設(shè)第n次傳球后，球又回到甲手中的傳球方式有an種?？梢韵胂笄皀-1次傳球，如果每一次傳球都任選其他三人中的一人進(jìn)行接球，則每次傳球都有3種可能，由乘法原理，共有 333=3 n-1 種傳球方法。這些傳球方式可以分為兩類: 一類是第n-1次恰好傳到甲手中，這有an-1種傳法，它們不符合要求，因?yàn)檫@樣第n次無(wú)法再把球傳給甲； 另一類是第n-1次傳球，球不在甲手中，第n次持球人再將球傳給甲，有an種傳法

30、。 根據(jù)加法原理，有an-1+an=3 n-1 。 由于甲是發(fā)球者，一次傳球后球又回到甲手中的傳球方式是不存在的，所以a1=0。 利用遞推關(guān)系可以得到 a2=3-0=3， a3=33-3=6， a4=333-6=21， a5=3333-21=60。 這說(shuō)明經(jīng)過(guò)5次傳球后，球仍回到甲手中的傳球方法有60種。第53頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四var a:array1.100 of longint; n,m,i,j:longint;begin readln(n,m); a1:=0; j:=1; for i:= 2 to m do begin j:=j*(n-1); 先求出

31、(n-1)i-1 ai:=j-ai-1; end; writeln(am);end.第54頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四var 加入高精度運(yùn)算 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:= 100 downto 1 do sj:=sj*(n-1); for j:= 100 downto 1 do if sj9 then b

32、egin 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,i);end.第55頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四凸多邊形劃分 在一個(gè)凸多邊形中，通過(guò)若干條互不相交的對(duì)

33、角線，把這個(gè)凸多邊形剖分成了若干個(gè)三角形?，F(xiàn)在的任務(wù)是根據(jù)輸入的凸多邊形的邊數(shù)，求不同剖分的方案數(shù)Cn。比如當(dāng)n=5時(shí)，有如下5種不同的方案，所以C5=5。輸入文件14.in：一個(gè)正整數(shù)，表示凸多邊形的邊數(shù)。(n=21)輸出文件14.out：一個(gè)正整數(shù)，表示方案總數(shù)。第56頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四如圖所示，我們以p1pn這條邊為基準(zhǔn)邊，再找pk來(lái)構(gòu)成三角形，則原凸n邊形被剖解成了p1pkpn和兩個(gè)凸多邊形，其中一個(gè)是由p1,p2,pk構(gòu)成的凸k邊形，另一個(gè)是由pk,pk+1,pn構(gòu)成的凸n-k+1邊形，根據(jù)乘法原理，選擇pk這個(gè)頂點(diǎn)的分解方案為 種。而k可以選2

34、到n-1，所以根據(jù)加法原理，得出總的方案數(shù)為 注意，就這個(gè)遞推關(guān)系而言，臨界值應(yīng)為C2=1，而不是C3=1，否則遞推關(guān)系就得不到正確解，這與原問(wèn)題的實(shí)際情況可能不符（即兩邊形），其實(shí)這只是理解上的差異P1PnP2P3PkPn-1Pn-2第57頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四const 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:=ci+

35、ck*ci-k+1; end; writeln(cn);end.第58頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四求路徑總數(shù)下圖是某居民小區(qū)道路圖，小明每天由家（點(diǎn)）到學(xué)校（點(diǎn)），他只沿道路向上或向右行走，那么他最多有（）天走不同線路？1015212836 454 1020 355684120 1655 1535 70126 210 330 495第59頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四var i,j,n,m:integer; a:array1.20,1.20 of longint;begin read(n,m); fillchar(a,sizeof(a),0

36、); 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.要想到達(dá)坐標(biāo)為（i,j）的頂點(diǎn)的話，必定要經(jīng)過(guò)坐標(biāo)為（i-1,j）的頂點(diǎn)或坐標(biāo)為（i,j-1）的頂點(diǎn)，設(shè)a(I,j)表示從點(diǎn)A到頂點(diǎn)(I,j)的路徑總條數(shù)，則a(I,j)=a(I,j-1)+a(i-1,j)輸入：5 9輸出：495第60頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四街道路徑 設(shè)有一個(gè)NM（1=N=50，1=M=50）

37、的街道，規(guī)定行人從A(1,1)出發(fā)，在街道上只能向東或北行走。 若在此街道中，設(shè)置一個(gè)矩形障礙區(qū)域（包括圍住該區(qū)域的的街道）不讓行人通行，如上圖中用“”表示的部分。此矩形障礙區(qū)域用2對(duì)頂點(diǎn)坐標(biāo)給出，如上圖中的2對(duì)頂點(diǎn)坐標(biāo)為(2，2),(8，4)，此時(shí)從A出發(fā)到達(dá)B的路徑有兩條。 現(xiàn)給出N、M，同時(shí)再給出此街道中的矩形障礙區(qū)域的2對(duì)頂點(diǎn)坐標(biāo)(x1,y1)，（x2,y2），請(qǐng)求出此時(shí)所有從A出發(fā)到達(dá)B的路徑的條數(shù)。 由于在街上只能向東或北方向行走，因此要想達(dá)到坐標(biāo)為（i,j）的頂點(diǎn)的話，必定要經(jīng)過(guò)坐標(biāo)為（i-1,j）的頂點(diǎn)或坐標(biāo)為（i,j-1）的頂點(diǎn)，假設(shè)從起始頂點(diǎn)到達(dá)坐標(biāo)為（i,j）的頂點(diǎn)的路徑

38、總數(shù)為ai,j，則ai,j= ai-1,j +ai,j-1。因此我們可以采用逐行遞推的方法來(lái)求出從起始頂點(diǎn)到達(dá)任意一個(gè)頂點(diǎn)的路徑總數(shù)。第61頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四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

39、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; 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.有可能障礙區(qū)域靠邊如輸入9 52 8 4應(yīng)輸出1第62頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，

40、星期四 Var加入高精度運(yùn)算 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

41、; ai,1,1:=1; end; for j:=1 to n do begin if not(b1,j) then break; a1,j,1:=1; end; for i:=2 to m do for j:=2 to n do if bi,j then begin g:=0; for k:=1 to 30 do begin ai,j,k:=ai-1,j,k+ai,j-1,k+g; g:=ai,j,k div 10; ai,j,k:=ai,j,k mod 10; end; end; j:=30; for i:=30 downto 1 do if am,n,i=0 then j:=j-1; f

42、or i:=j downto 1 do write(am,n,i);end.第63頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四過(guò)河卒 如圖，A 點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo) B 點(diǎn)。卒行走規(guī)則：可以向下、或者向右。同時(shí)在棋盤上的任一點(diǎn)有一個(gè)對(duì)方的馬（如上圖的C點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。例如上圖 C 點(diǎn)上的馬可以控制 9 個(gè)點(diǎn)（圖中的P1，P2 P8 和 C）。卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤用坐標(biāo)表示，A 點(diǎn)（0，0）、B 點(diǎn)（n,m）( n,m為不超過(guò) 20的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的（約定: CA，同時(shí)CB）?，F(xiàn)在要求你計(jì)算出卒從 A

43、點(diǎn)能夠到達(dá) B 點(diǎn)的路徑的條數(shù)。 輸入文件5.in，只有一行，共4個(gè)正整數(shù)，前2個(gè)數(shù)表示B點(diǎn)的坐標(biāo)，后2個(gè)數(shù)表示對(duì)方馬的坐標(biāo)。 輸出文件5.out，只有一行，一個(gè)整數(shù)（表示路徑的條數(shù)）。 樣例: 輸入 6 6 3 2 輸出 17分析:要到達(dá)棋盤上的一個(gè)點(diǎn)，只能從左邊過(guò)來(lái)或是從上面下來(lái)，所以根據(jù)加法原理，到達(dá)某一點(diǎn)的路徑數(shù)目，等于到達(dá)其相鄰上、左兩點(diǎn)的路徑數(shù)目之和，因此我們可以使用逐行遞推的方法來(lái)求出從起始頂點(diǎn)到終點(diǎn)的路徑數(shù)目，如果有障礙，只要將到達(dá)該點(diǎn)的路徑數(shù)目設(shè)置為即可。第64頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四const x1:array1.8of integer=(2

44、,2,1,-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=

45、0)and(y+y1i1) do j:=j-1; for i:=j downto 1 do write(an,m,i); end.第67頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四傳球游戲【問(wèn)題描述】 上體育課的時(shí)候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著同學(xué)們一起做傳球游戲。游戲規(guī)則是這樣的：n個(gè)同學(xué)站成一個(gè)圓圈，其中的一個(gè)同學(xué)手里拿著一個(gè)球，當(dāng)老師吹哨子時(shí)開始傳球，每個(gè)同學(xué)可以把球傳給自己左右的兩個(gè)同學(xué)中的一個(gè)（左右任意），當(dāng)老師再次吹哨子時(shí)，傳球停止，此時(shí)，拿著球沒有傳出去的那個(gè)同學(xué)就是敗者，要給大家表演一個(gè)節(jié)目。 聰明的小蠻提出了一個(gè)有趣的問(wèn)題：有多少種不同的傳

46、球方法可以使得從小蠻手里開始傳的球，傳了m次后，又回到小蠻手里。兩種傳球方法被視為不同的方法，當(dāng)且僅當(dāng)這兩種方法中，接到球的同學(xué)按接球順序組成的序列是不同的。比如有3個(gè)同學(xué)1號(hào)、2號(hào)、3號(hào)，并假設(shè)小蠻為一號(hào)，球傳了3次后回到小蠻手里的方式有 1- 2- 3- 1 和 1- 3- 2- 1 ，共2種。第68頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四【輸入】 輸入文件ball.in共一行，有兩個(gè)用空格隔開的整數(shù)n，m（3=n=30，1=m=30）?！据敵觥?輸出文件ball.out共一行，有一個(gè)整數(shù)，表示符合題意的方法數(shù)?！据斎胼敵鰳永?ball.in 3 ball.out 32【

47、限制】 40%的數(shù)據(jù)滿足：3=n=30，1=m=20 100%的數(shù)據(jù)滿足：3=n=30，1=m=30第69頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四分析： 設(shè)f(i,k)表示經(jīng)過(guò)k次傳球到編號(hào)為i的人手中的方案數(shù)?？梢园l(fā)現(xiàn)，傳到i號(hào)同學(xué)的球只能來(lái)自于i的左邊一個(gè)同學(xué)或者右邊一個(gè)同學(xué)，這兩個(gè)同學(xué)的編號(hào)分別是i-1、i+1，所以可以得到以下的遞推公式： f(i,k)=f(i-1,k-1)+f(i+1,k-1) 當(dāng)i=1或n時(shí)，需單獨(dú)處理： 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號(hào)同學(xué)開始傳球，可確定初始

48、條件：f(1,0)=1 可根據(jù)傳球次數(shù)進(jìn)行遞推，結(jié)果在f(1,m)中。第70頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四var i,j,k,n,m:longint; f:array0.30,0.30 of longint;begin readln(n,m); fillchar(f,sizeof(f),0); f1,0:=1; for k:=1 to m do begin f1,k:=f2,k-1+fn,k-1; 當(dāng)球在1號(hào)同學(xué)時(shí) for i:= 2 to n-1 do fi,k:=fi-1,k-1+fi+1,k-1; fn,k:=fn-1,k-1+f1,k-1; 當(dāng)球在n號(hào)同學(xué)時(shí)

49、end; write(f1,m);end.第71頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四傳球問(wèn)題 4個(gè)人進(jìn)行籃球訓(xùn)練，互相傳球接球，要求每個(gè)人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問(wèn)有多少種傳球方式？第72頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四Var n,m,i,j,k,l,g:longint; a:array0.30,1.30,1.100 of longint;begin read(n,m); a0,1,1:=1; for i:=1 to m do begin for j:=1 to n do for k:=1 t

50、o n do if jk then begin g:=0; for l:=1 to 100 do begin g:=ai,j,l+ai-1,k,l+g; ai,j,l:=g mod 10 ; g:=g div 10; end; end; end;l:=100;while am,1,l=0 do l:=l-1;for i:=l downto 1 do write(am,1,i);end.第73頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四整數(shù)劃分 把一個(gè)正整數(shù)N劃分成一些正整數(shù)的和，例如：N =n1+n2+nk 且滿足1=n1=n2=nk = N ，叫做N的一個(gè)劃分。求不同的劃分的數(shù)量

51、。 當(dāng)n=4時(shí)，劃分?jǐn)?shù)為4。 4=1+1+1+1； 4=1+1+2； 4=1+3； 4=2+2； 第74頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四設(shè) 表示把正整數(shù)a做分劃、其中最大的一份恰好是b的方案總數(shù)。設(shè)表示把正整數(shù)a做分劃、其中最大的一份不大于b的方案總數(shù)。顯然有：所以：當(dāng)i=j then gi,j:=gi-j,j+gi,j-1 else gi,j:=gi,j-1; writeln( gn,n-1 );end.第77頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四倒推法 我們把由已知初始值為1，通過(guò)遞推關(guān)系式n=g(Fn-1)求出其最終結(jié)果Fn的遞推方式稱為順推法同

52、理，把已知最終結(jié)果為Fn，通過(guò)遞推關(guān)系式n-1=g(Fn)，求出其初始值1的遞推方式稱之為倒推法。第78頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四 四個(gè)人做火柴游戲,每一局三個(gè)人贏,一個(gè)人輸,輸者要按贏者手中贏得火柴根數(shù)賠償,即贏者手中有多少根火柴,輸者就賠他多少?4次之后,每人恰好輸過(guò)一次而且手中都恰好有16根?求四人原有火柴數(shù)?把第一局輸?shù)娜擞洖?，把第二局輸?shù)娜擞洖椋训谌州數(shù)娜擞洖?，把第四局輸?shù)娜擞洖椋玫雇朔芍洪_始第79頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四騎士游歷 設(shè)有一個(gè)n*m的棋盤(2=n=50，2=m(2,3)-(4,4)。若不存 在路徑,則輸出no。第80頁(yè)，共86頁(yè)，2022年，5月20日，6點(diǎn)10分，星期四算法分析：我們先將棋盤的橫坐標(biāo)規(guī)定為i，縱坐標(biāo)規(guī)定為j，對(duì)于一個(gè)nm的棋盤，i的值從1到n，j的值從1到m。棋盤上的任意點(diǎn)都可以用坐標(biāo)(i,j)表示。對(duì)于馬的移動(dòng)方法，我們用K來(lái)表示四種移動(dòng)方向(1,2,3,4)；而每種移動(dòng)方法用偏移值來(lái)表示，并將這些偏移值分別保存在數(shù)組dx