1、遞推法遞推法 所謂遞推，是指從已知的初始條件出發，依據某種遞推所謂遞推，是指從已知的初始條件出發，依據某種遞推關系，逐次推出所要求的各中間結果及最后結果。其中初始關系，逐次推出所要求的各中間結果及最后結果。其中初始條件或是問題本身已經給定，或是通過對問題的分析與化簡條件或是問題本身已經給定，或是通過對問題的分析與化簡后確定。后確定。 可用遞推算法求解的題目一般有以下二個特點：可用遞推算法求解的題目一般有以下二個特點： 1、問題可以劃分成多個狀態；、問題可以劃分成多個狀態； 2、除初始狀態外，其它各個狀態都可以用固定的遞推關、除初始狀態外，其它各個狀態都可以用固定的遞推關系式來表示。系式來表示。

2、 在我們實際解題中，題目不會直接給出遞推關系式，而在我們實際解題中，題目不會直接給出遞推關系式，而是需要通過分析各種狀態，找出遞推關系式。是需要通過分析各種狀態，找出遞推關系式。采用具體化、特殊化的方法尋找規律采用具體化、特殊化的方法尋找規律 平面上平面上n條直線，任兩條不平行，任三條不共點，問條直線，任兩條不平行，任三條不共點，問這這n條直線把這平面劃分為多少個部分？條直線把這平面劃分為多少個部分？ 設這設這n條直線把這平面劃分成條直線把這平面劃分成Fn個部分。個部分。 先用具體化特殊化的方法尋找規律，如圖所示，易知先用具體化特殊化的方法尋找規律，如圖所示，易知的前幾項分別為的前幾項分別為

3、這些數字之間的規律性不很明顯，這些數字之間的規律性不很明顯， 較難用不完全歸納法較難用不完全歸納法猜出猜出Fn的一般表達式。但我們可以分析前后項之間的遞推關系，的一般表達式。但我們可以分析前后項之間的遞推關系，因為這些圖形中，后一個都是由前一個添加一條直線而得到的，因為這些圖形中，后一個都是由前一個添加一條直線而得到的，添加一條直線便增加若干個區域。添加一條直線便增加若干個區域。 一般地，設原來的符合題意的一般地，設原來的符合題意的n-1條直線把這平面分成條直線把這平面分成 個區域，再增加一條直線個區域，再增加一條直線l，就變成，就變成n條直線，按題設條條直線，按題設條件，這件，這l必須與原有

4、的必須與原有的n-1條直線各有一個交點條直線各有一個交點, 且這且這n-1個交點個交點及原有的交點互不重合。這及原有的交點互不重合。這n-1個交點把個交點把l劃分成劃分成n個區間，每個區間，每個區間把所在的原來區域一分為二，所以就相應比原來另增個區間把所在的原來區域一分為二，所以就相應比原來另增了了n個區域，即：個區域，即： 這樣，我們就找到了一個從這樣，我們就找到了一個從Fn-1到到Fn的的遞推式，再加上的的遞推式，再加上已知的初始值已知的初始值F1=2，就可以通過，就可以通過n-1步可重復的簡單運算推導步可重復的簡單運算推導出出Fn的值。的值。var a,i,n:longint;begin

5、 read(n); a:=2; for i:=2 to n do a:=a+i; writeln(a);end. 在平面內畫五條直線和一個圓，最多能把平面分成在平面內畫五條直線和一個圓，最多能把平面分成多少部分？多少部分？ 平面上有平面上有8個圓，最多能把平面分成幾部分？個圓，最多能把平面分成幾部分？ 123456Fn=Fn-1+2 (n-1) 圓周上兩個點將圓周分為兩半，在這兩點上寫上數圓周上兩個點將圓周分為兩半，在這兩點上寫上數1 1；然后將兩段半圓弧對分，在兩個分點上寫上相鄰兩點上的然后將兩段半圓弧對分，在兩個分點上寫上相鄰兩點上的數之和；再把數之和；再把4 4段圓弧等分，在分點上寫上相

6、鄰兩點上的數段圓弧等分，在分點上寫上相鄰兩點上的數之和，如此繼續下去，問第之和，如此繼續下去，問第6 6步后，圓周上所有點上的步后，圓周上所有點上的數數之之和是多少？和是多少？ 分析分析: :先可以采用作圖嘗試尋找規律。先可以采用作圖嘗試尋找規律。第一步：圓周上有兩個點，兩個數的和是第一步：圓周上有兩個點，兩個數的和是1+1=21+1=2；第二步：圓周上有四個點，四個數的和是第二步：圓周上有四個點，四個數的和是1+1+2+2=61+1+2+2=6；增加數之和恰好是第一步；增加數之和恰好是第一步圓周上所有數之和的圓周上所有數之和的2 2倍。倍。第三步：圓周上有八個點，八個數的和是第三步：圓周上有

7、八個點，八個數的和是1+1+2+2+3+3+3+3=181+1+2+2+3+3+3+3=18，增加數之和恰，增加數之和恰好是第二步數圓周上所有數之和的好是第二步數圓周上所有數之和的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倍。倍。這樣我們可以知道，圓周上所有數之和是前一步圓周上所有數之和的這樣我們可以知道，圓周上所有數之和

8、是前一步圓周上所有數之和的3 3倍。倍。設設A An n為第為第n n步后得出的圓周上所有數之和，則步后得出的圓周上所有數之和，則A An n=3=3A An n1 1 在在 nn的正方形釘子板上（的正方形釘子板上（n是釘子板每邊上的是釘子板每邊上的釘子數），求連接任意兩個釘子所得到的不同長度的釘子數），求連接任意兩個釘子所得到的不同長度的線段種數線段種數.Fn=Fn-1+n 如圖如圖1，是棱長為，是棱長為a的小正方體，圖的小正方體，圖2，圖，圖3由這樣的小正由這樣的小正方體擺放而成。按照這樣的方法繼續擺放，自上而下分別叫方體擺放而成。按照這樣的方法繼續擺放，自上而下分別叫第一層、第二層、第一

9、層、第二層、第、第n層，第層，第n層的小正方體的個數記層的小正方體的個數記為為sn。請寫出求。請寫出求sn的遞推公式。的遞推公式。1 3 6 10nssnn1 如圖，有邊長為如圖，有邊長為1的等邊三角形卡片若干張，使用這些的等邊三角形卡片若干張，使用這些三角形卡片拼出邊長分別是三角形卡片拼出邊長分別是2，3，4，的等邊三角形（如的等邊三角形（如圖所示）根據圖形推斷，寫出求每個等邊三角形所用卡圖所示）根據圖形推斷，寫出求每個等邊三角形所用卡片總數片總數sn的遞推公式的遞推公式 4 9 16 25 364)2( 1221snnssnn 為慶祝為慶祝“五五一一”國際勞動節，市政府決定在人民廣場上增國

10、際勞動節，市政府決定在人民廣場上增設一排燈花，其設計由以下圖形逐步演變而成，其中圓圈代表設一排燈花，其設計由以下圖形逐步演變而成，其中圓圈代表燈花中的燈泡，燈花中的燈泡，n代表第代表第n次演變過程，次演變過程，s代表第代表第n次演變后的燈次演變后的燈泡的個數。仔細觀察下列演變過程，當泡的個數。仔細觀察下列演變過程，當n=6時，時，s=_。94 2n1nn23ssSn=2sn-1+2Sn=3sn-1-2sn-2 某公共汽車線路上共有某公共汽車線路上共有15個車站（包括起點站和終點個車站（包括起點站和終點站）。在每個站上車的人中，恰好在以后各站下去一個。要站）。在每個站上車的人中，恰好在以后各站下

11、去一個。要使行駛過程中每位乘客都有座位，車上至少要備有多少個座使行駛過程中每位乘客都有座位，車上至少要備有多少個座位？位？ 從表中可以看出車上人數最多是從表中可以看出車上人數最多是56人，所以車上人，所以車上至少要準備至少要準備56個座位。個座位。練習練習1 將一張長方形的紙對折，可得到一條折痕，繼續對將一張長方形的紙對折，可得到一條折痕，繼續對折，對折時每次折痕與上次的折痕保持平行，連續對折折，對折時每次折痕與上次的折痕保持平行，連續對折三次后，可得到條折痕，那么對折三次后，可得到條折痕，那么對折n次，可得到幾條次，可得到幾條折痕？折痕？ Fn=2*Fn-1+1 var a,i,n:long

12、int;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;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時時 b1

13、00:=1;20=1 for i:= 2 to n do begin 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

14、j:=j+1; for i:= j to 100 do write(ai) ; end.練習練習2 如圖如圖,第一次把三角形剪去一個角后第一次把三角形剪去一個角后,圖中最多有四個圖中最多有四個角角,第二次再把新產生的角各剪一刀第二次再把新產生的角各剪一刀,如此下去如此下去,每一次每一次都是把新產生的角各剪一刀都是把新產生的角各剪一刀,則第則第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; f

15、or 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,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

16、 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.練習練習3 下圖中把大正方形各邊平均分成了下圖中把大正方形各邊平均分成了5份，此時有份，此時有55個正個正方形。如果把正方形各邊平均分成方形。如果把正方形各邊平均分成n份，那么得到的正方形份，那么得到的正方形總數為多少？總數為多少？52+42+32+22+12=55n2+(n-1)2+

17、(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; writeln(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

18、 ; 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 do write(ai); end.練習練習4 如圖，由等圓組成的一組圖中，第如圖，由等圓組成的一組圖中，第1個圖由個圖由1個圓組成，個圓組成，第第2個圖由個圖由7個圓組成，第個圓組成，第3個圖由個圖由19個圓組成，個圓組成，按照，按照這樣的規律排列下去，則第這樣的規律排列下去，則第9個圖形由個圖形由_個圓組成。個圓組成。 217可得遞推公式可得遞推公式:Fn= Fn-1+6*（n1）var a,i,n:longint

19、;begin read(n); a:=1; for i:=2 to n do a:=a+6*(i-1); writeln(a);end.var 加入高精度運算加入高精度運算 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:

20、= j to 50 do write(ai);end.練習練習5 已知三角形已知三角形ABC的面積為的面積為10，延長邊，延長邊BC到點到點D，使，使BC=CD，延長邊延長邊CA到點到點E，使，使CA=AE，延長邊，延長邊AB到點到點F，使，使AB=BF，連，連結結DE,EF,FD,得到三角形得到三角形DEF,并記圖中陰影部分面積為并記圖中陰影部分面積為S1,此時我此時我們稱三角形們稱三角形ABC向外擴展了一次向外擴展了一次.求經過求經過N次擴展后圖中陰影部分次擴展后圖中陰影部分的面積的面積Sn.Fn=7*Fn-1 ( Fn為第為第n次擴展后整個三角形的面積次擴展后整個三角形的面積 )F0=1

21、0Sn=Fn-Fn-1const max=100;var f1,f2,s:array1.max of longint; i,j,k,l,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

22、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 to max do write(si) ; end.Hanoi雙塔雙塔問題問題 給定給定A、B、C三根足夠長的細柱，在三根足夠長的細柱，在A柱上放有柱上放有2n個中個中 間有孔的圓盤，共有間有孔的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區分的（下圖為的圓盤，注意這兩個圓盤是不加區分的（下圖為n=3的情的情形）。現要將這些圓盤移到形）。現要將這些圓盤移

23、到C柱上，在移動過程中可放在柱上，在移動過程中可放在B柱柱上暫存。要求：上暫存。要求： （1）每次只能移動一個圓盤；）每次只能移動一個圓盤； （2）A、B、C三根細柱上的圓盤都要保持上小下大的順三根細柱上的圓盤都要保持上小下大的順序；序； 任務：設任務：設An為為2n個圓盤完成上述任務所需的最少移動次個圓盤完成上述任務所需的最少移動次數，對于輸入的數，對于輸入的n，輸出，輸出An。 輸入文件輸入文件hanoi.in為一個正整數為一個正整數n，表示在，表示在A柱上放有柱上放有2n個圓盤。個圓盤。 輸出文件輸出文件hanoi.out僅一行，包含一個正整數僅一行，包含一個正整數，為完成上為完成上述任

24、務所需的最少移動次數述任務所需的最少移動次數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 then f:=true; if f then write(ai); end; close(input); close(outp

25、ut);end. 在上面的一些例題中，遞推過程中的某個狀態在上面的一些例題中，遞推過程中的某個狀態只與前面的一個狀態有關，遞推關系并不復雜。如只與前面的一個狀態有關，遞推關系并不復雜。如果在遞推中的某個狀態與前面的幾個狀態、甚至所果在遞推中的某個狀態與前面的幾個狀態、甚至所有狀態都有關，就不容易找出遞推關系式，這就需有狀態都有關，就不容易找出遞推關系式，這就需要我們對實際問題進行分析與歸納，從中找到突破要我們對實際問題進行分析與歸納，從中找到突破口，總結出遞推關系式。口，總結出遞推關系式。 意大利著名數學家斐波那契在研究兔子繁殖問題時，發現意大利著名數學家斐波那契在研究兔子繁殖問題時，發現有這

26、樣一組數：有這樣一組數：1，1，2，3，5，8，13，其中從第三個數，其中從第三個數起，每一個數都等于它前面兩上數的和。現以這組數中的各個起，每一個數都等于它前面兩上數的和。現以這組數中的各個數作為正方形的邊長構造如下正方形：數作為正方形的邊長構造如下正方形： 1 1 2 3 5 . 再分別依次從左到右取再分別依次從左到右取2個、個、3個、個、4個、個、5個正方形拼成個正方形拼成如下矩形并記為如下矩形并記為、若按此規律繼續作矩形，則序號為若按此規律繼續作矩形，則序號為的矩形周長是。的矩形周長是。 466 【問題描述】【問題描述】 一只蜜蜂在上圖所示的數字蜂房上爬動一只蜜蜂在上圖所示的數字蜂房上

27、爬動,已知它只已知它只能從標號小的蜂房爬到標號大的相鄰蜂房能從標號小的蜂房爬到標號大的相鄰蜂房,現在問你：現在問你：蜜蜂從蜂房蜜蜂從蜂房M開始爬到蜂房開始爬到蜂房N（MN），有多少種爬），有多少種爬行路線？行路線？ 【輸入格式】【輸入格式】 輸入輸入M，N的值。的值。(1=M,N0），求出鋪法總數的遞推公），求出鋪法總數的遞推公式。式。F(1)=1F(2)=2F(n)=F(n-2)+F(n-1) (n=3) 如果有如果有n元錢元錢,每天去購買下列三種商品之一每天去購買下列三種商品之一:蔬菜要蔬菜要用用1元錢元錢,豬肉要用豬肉要用2元錢元錢,雞蛋要用元錢用雞蛋要用元錢用An表示把表示把這這n元錢

28、用完的所有可能的用法的總數元錢用完的所有可能的用法的總數如果第一天買蔬菜，則用去元錢，還剩如果第一天買蔬菜，則用去元錢，還剩n-1元錢，元錢， 這這n-1元錢的用法有元錢的用法有n-1種；種；如果第一天買豬肉，則用去元錢，還剩如果第一天買豬肉，則用去元錢，還剩n-元錢，元錢， 這這n-元錢的用法有元錢的用法有n-2種；種； 如果第一天買雞蛋，則用去元錢，還剩如果第一天買雞蛋，則用去元錢，還剩n-元錢，元錢， 這這n-元錢的用法有元錢的用法有n-2種；種； 所以，所以，n=n-1+2n-2 有排成一行的個方格，用紅、黃、藍三色涂每個格子，有排成一行的個方格，用紅、黃、藍三色涂每個格子，每格涂一色

29、，要求任何相鄰的格不同色，且首尾兩格也不同每格涂一色，要求任何相鄰的格不同色，且首尾兩格也不同色。問有多少種涂法？色。問有多少種涂法？ 解：解：設共有設共有n種涂法，易見種涂法，易見1，2，3，且當，且當時，將時，將個格子依次編號后，格與格（個格子依次編號后，格與格（n-1）不相鄰。）不相鄰。情形情形：格（：格（n-1）涂色與格不同，此時格只有一色可涂，且前（）涂色與格不同，此時格只有一色可涂，且前（n-1）格滿足首尾兩格不同色，故有格滿足首尾兩格不同色，故有n-1種涂色方法。種涂色方法。情形情形：格（：格（n-1）涂色與格相同，此時格（）涂色與格相同，此時格（n-2）與格涂色必然不同，）與格

30、涂色必然不同，不然，格（不然，格（n-1）與（）與（n-2）相同，于是前（）相同，于是前（n-2）格有）格有n-2種涂色法。因為格種涂色法。因為格與格不同色，有兩種涂色法，故共有與格不同色，有兩種涂色法，故共有n-2種涂色法。種涂色法。綜上，可得綜上，可得nn-1n-2（）按前按前n-1格首尾關系討論格首尾關系討論 錯位排列錯位排列 五個人排成一列，重新站隊時，各人都不站在原來的位置上，那么不同的五個人排成一列，重新站隊時，各人都不站在原來的位置上，那么不同的站隊方式共有站隊方式共有( ) （A）60種種 （B）44種種 （C）36種種 （D）24種種 解：首先我們把人數推廣到解：首先我們把人

31、數推廣到n個人，即個人，即n個人排成一列，重新站隊時，各人都不個人排成一列，重新站隊時，各人都不站在原來的位置上。設滿足這樣的站隊方式有站在原來的位置上。設滿足這樣的站隊方式有An種，現在我們通過合理分步，恰當種，現在我們通過合理分步，恰當分類分類來來找出遞推關系：找出遞推關系： 第一步第一步：第一個人不站在原來的第一個位置，有：第一個人不站在原來的第一個位置，有n-1種站法。種站法。 第二步第二步：假設第一個人站在第：假設第一個人站在第2個位置，則第二個人的站法又可以分為兩類：個位置，則第二個人的站法又可以分為兩類：第一類第一類，第二個人恰好站在第一個位置，則余下的，第二個人恰好站在第一個位

32、置，則余下的 n-2個人有個人有An-2種站隊方式；種站隊方式；第二第二類類，第二個人不站在第一個位置，則就是第二個人不站在第一個位置，第三個人不，第二個人不站在第一個位置，則就是第二個人不站在第一個位置，第三個人不站在第三個位置，第四個人不站在第四個位置，站在第三個位置，第四個人不站在第四個位置，第，第n個人不站在第個人不站在第n個位置，個位置，所以有所以有An-1種站隊方式。種站隊方式。 由分步計數原理和分類計數原理，我們便得到了數列由分步計數原理和分類計數原理，我們便得到了數列 的遞推關系式：的遞推關系式： ，顯然，顯然 ，再由遞推關系有，再由遞推關系有，na)(1(12nnnaana1

33、, 021aa9,243aa445a 在書架上放有編號為在書架上放有編號為1 ，2 ，n的的n本書。現將本書。現將n本書全部取下然后再放回去，當放回去時要求每本書本書全部取下然后再放回去，當放回去時要求每本書都不能放在原來的位置上。都不能放在原來的位置上。 例如：例如：n = 3時：時： 原來位置為：原來位置為：1 2 3 放回去時只能為：放回去時只能為：3 1 2 或或 2 3 1 這兩種這兩種 問題：求當問題：求當n = 5時滿足以上條件的放法共有多少時滿足以上條件的放法共有多少種？種？染色問題染色問題 用用4種不同顏色涂四邊形的種不同顏色涂四邊形的4個頂點，要求每點染一種顏個頂點，要求每

34、點染一種顏色，相鄰的頂點染不同的顏色，則不同的染色方法有色，相鄰的頂點染不同的顏色，則不同的染色方法有( )（A）84種種（B）72種種（C）48種種（D）24種種AVar 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是頂點數，是頂點數，m是顏色數是顏色數 a3:=jc(m) div jc(m-3);初值初值 for

35、 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; writeln(an);end.)!3(!33mmAam1) 1(ima3:=m*(m-1)*(m-2)如圖，一個地區分為如圖，一個地區分為5個行政區域，現給地圖著色，要求個行政區域，現給地圖著色，要求相鄰區域不得使用同一顏色，現有四種顏色可供選擇，則相鄰區域不得使用同一顏色，現有四種顏色可供選擇，則不同的著色方法共有不同的著色方法共有 種。種。 圖中圖中2、3、4、5四個區域圍成一個四邊形，因此可以四個區域圍成一個四邊

36、形，因此可以把它們看成是一個四邊形的把它們看成是一個四邊形的4個頂點，而區域個頂點，而區域1就是這個四就是這個四邊形對角線的交點。邊形對角線的交點。 第一步，先涂區域第一步，先涂區域1，有，有4種涂法。種涂法。 第二步，由于區域第二步，由于區域1跟其余四個區域都相鄰，因此涂跟其余四個區域都相鄰，因此涂1的顏色不能用來涂其余的四個區域，因此第二步相當于用的顏色不能用來涂其余的四個區域，因此第二步相當于用3種顏色來涂一個四邊形的四個頂點，不難得出種顏色來涂一個四邊形的四個頂點，不難得出 所以，所以，由分步計數原理，得出共有由分步計數原理，得出共有 種涂法。種涂法。 1123nnnaa6333 Aa

37、1823334aa72184 某城市在中心廣場建造一個花圃，花圃分成某城市在中心廣場建造一個花圃，花圃分成6個部分個部分(如如圖圖)，現要栽種，現要栽種4種不同顏色的花，每部分栽種一種且相鄰部種不同顏色的花，每部分栽種一種且相鄰部分不能栽種同樣顏色的花，不同的栽種方法共有分不能栽種同樣顏色的花，不同的栽種方法共有 種。種。 1206333 Aa1823334aa30184823445aa430=120傳球傳球問題問題 4個人進行籃球訓練，互相傳球接球，要求每個人接球個人進行籃球訓練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發球，并作為第一次傳球，第后馬上傳給別人，開始由甲發球，并作

38、為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方式？五次傳球后，球又回到甲手中，問有多少種傳球方式？60分析分析 :設第設第n次傳球后，球又回到甲手中的傳球方式有次傳球后，球又回到甲手中的傳球方式有an種種。可以想象前。可以想象前n-1次傳球，如次傳球，如果每一次傳球都任選其他三人中的一人進行接球，則每次傳球都有果每一次傳球都任選其他三人中的一人進行接球，則每次傳球都有3種可能，由乘法原種可能，由乘法原理，共有理，共有 333=3 n-1 種傳球方法。這些傳球方式可以分為兩類種傳球方法。這些傳球方式可以分為兩類: 一類是第一類是第n-1次恰好傳到甲手中，這有次恰好傳到甲手中，這有a

39、n-1種傳法，它們不符合要求，因為這樣第種傳法，它們不符合要求，因為這樣第n次無法再把球傳給甲；次無法再把球傳給甲； 另一類是第另一類是第n-1次傳球，球不在甲手中，第次傳球，球不在甲手中，第n次持球人再將球傳給甲，有次持球人再將球傳給甲，有an種傳法。種傳法。 根據加法原理，有根據加法原理，有an-1+an=3 n-1 。 由于甲是發球者，一次傳球后球又回到甲手中的傳球方式是不存在的，所以由于甲是發球者，一次傳球后球又回到甲手中的傳球方式是不存在的，所以a1=0。 利用遞推關系可以得到利用遞推關系可以得到 a2=3-0=3， a3=33-3=6， a4=333-6=21， a5=3333-2

40、1=60。 這說明經過這說明經過5次傳球后，球仍回到甲手中的傳球方法有次傳球后，球仍回到甲手中的傳球方法有60種。種。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); 先求出先求出(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

41、,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 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-

42、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.凸多邊形劃分凸多邊形劃分 在一個凸多邊形中，通過若干條互不相交的對角線，把這在一個凸多邊形中，通過若干條互不相交的對角線，把這個凸多邊形剖分成了若干個三角形。現在的任務是根據輸入的個凸多邊形剖分成了若干個三角形。現在的任務是根據輸入的凸多邊形的邊數，求不同剖分的方案數凸多邊形的邊數，求不同剖分的方案數Cn。比如當。比如當n=5時，有時，有如下如下5種不同的方案，所以種不同的方案，所以C5=5。輸入文件輸入

43、文件14.in：一個正整數，表示凸多邊形的邊數。：一個正整數，表示凸多邊形的邊數。(n=21)輸出文件輸出文件14.out：一個正整數，表示方案總數。：一個正整數，表示方案總數。如圖所示，我們以如圖所示，我們以p1pn這條邊為基準邊，再找這條邊為基準邊，再找pk來構成三角形，來構成三角形，則原凸則原凸n邊形被剖解成了邊形被剖解成了p1pkpn和兩個凸多邊形，其中一個是和兩個凸多邊形，其中一個是由由p1,p2,pk構成的凸構成的凸k邊形，另一個是由邊形，另一個是由pk,pk+1,pn構成的凸構成的凸n-k+1邊形，根據乘法原理，選擇邊形，根據乘法原理，選擇pk這個頂點的分解方案為這個頂點的分解方

44、案為 種。而種。而k可以選可以選2到到n-1，所以根據加法原理，得出總，所以根據加法原理，得出總的方案數為的方案數為 注意，就這個遞推關系而言，臨界值應為注意，就這個遞推關系而言，臨界值應為C2=1，而不是，而不是C3=1，否則遞推關系就得不到正確解，這與原問題的實際情況，否則遞推關系就得不到正確解，這與原問題的實際情況可能不符（即兩邊形），其實這只是理解上的差異可能不符（即兩邊形），其實這只是理解上的差異1knkCC1knkCC12nknCP1PnP2P3PkPn-1Pn-2const max=21;var c:array2.max of longint; n,i,k:integer; to

45、tal:longint;begin readln(n); c2:=1; for i:=3 to n do begin ci:=0; for k:=2 to i-1 do ci:=ci+ck*ci-k+1; end; writeln(cn);end.求路徑總數求路徑總數下圖是某居民小區道路圖，小明每天由家（點）到學校（點），下圖是某居民小區道路圖，小明每天由家（點）到學校（點），他只沿道路向上或向右行走，那么他最多有（）天走不同線路？他只沿道路向上或向右行走，那么他最多有（）天走不同線路？1015212836 454 1020 355684120 1655 1535 70126 210 330

46、495var i,j,n,m:integer; a:array1.20,1.20 of longint;begin read(n,m); fillchar(a,sizeof(a),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）的頂

47、點，設）的頂點，設a(I,j)表示從點表示從點A到頂點到頂點(I,j)的路徑總條數，則的路徑總條數，則a(I,j)=a(I,j-1)+a(i-1,j)輸入：輸入：5 9輸出：輸出：495街道路徑街道路徑 設有一個設有一個NM（1=N=50，1=M=50）的街）的街道，規定行人從道，規定行人從A(1,1)出發，在街道上出發，在街道上只能向東或北行走只能向東或北行走。 若在此街道中，設置一個矩形障礙區域（包括圍住該若在此街道中，設置一個矩形障礙區域（包括圍住該區域的的街道）不讓行人通行，如上圖中用區域的的街道）不讓行人通行，如上圖中用“”表示的表示的部分。此矩形障礙區域用部分。此矩形障礙區域用2對

48、頂點坐標給出，如上圖中的對頂點坐標給出，如上圖中的2對頂點坐標為對頂點坐標為(2，2),(8，4)，此時從，此時從A出發到達出發到達B的路徑的路徑有兩條。有兩條。 現給出現給出N、M，同時再給出此街道中的矩形障礙區域的，同時再給出此街道中的矩形障礙區域的2對頂點坐標對頂點坐標(x1,y1)，（，（x2,y2），請求出此時所有從），請求出此時所有從A出出發到達發到達B的路徑的條數。的路徑的條數。 由于在街上只能向東或北方向行走，因此要想達到坐標由于在街上只能向東或北方向行走，因此要想達到坐標為（為（i,j）的頂點的話，必定要經過坐標為（）的頂點的話，必定要經過坐標為（i-1,j）的頂點）的頂點或

49、坐標為（或坐標為（i,j-1）的頂點，假設從起始頂點到達坐標為）的頂點，假設從起始頂點到達坐標為（i,j）的頂點的路徑總數為）的頂點的路徑總數為ai,j，則，則ai,j= ai-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);行列要分清行列要分清 readl

50、n(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; 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:=

51、ai-1,j+ai,j-1; write(am,n);end.有可能障礙區域靠邊有可能障礙區域靠邊如輸入如輸入9 52 8 4應輸出應輸出11 Var加入高精度運算加入高精度運算 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

52、 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; 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,

53、k mod 10; end; end; j:=30; for i:=30 downto 1 do if am,n,i=0 then j:=j-1; for i:=j downto 1 do write(am,n,i);end.過河卒過河卒 如圖，如圖，A A 點有一個過河卒，需要走到目標點有一個過河卒，需要走到目標 B B 點。卒行走規則：可以向點。卒行走規則：可以向下、或者向右。同時在棋盤上的任一點有一個對方的馬（如上圖的下、或者向右。同時在棋盤上的任一點有一個對方的馬（如上圖的C C點），點），該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。例如上圖該馬所在的點和所有跳躍一步可達的點

54、稱為對方馬的控制點。例如上圖 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的整數的整數) )，同樣馬的位置坐標是需要給出的（約定，同樣馬的位置坐標是需要給出的（約定: CA: CA，同時，同時CBCB）。）。現在要求你計算出卒從現在要求你計算出卒從 A A 點能夠到達點能夠到達 B B 點的路徑的條數。點的路徑的條數

55、。 輸入文件輸入文件5.in5.in，只有一行，共，只有一行，共4 4個正整數，前個正整數，前2 2個數表示個數表示B B點的坐標，后點的坐標，后2 2個數表示對方馬的坐標。個數表示對方馬的坐標。 輸出文件輸出文件5.out5.out，只有一行，一個整數（表示路徑的條數）。，只有一行，一個整數（表示路徑的條數）。 樣例樣例: : 輸入輸入 6 6 3 2 6 6 3 2 輸出輸出 1717分析分析:要到達棋盤上的一個點，只能從左邊過來或是從上面要到達棋盤上的一個點，只能從左邊過來或是從上面下來，所以根據加法原理，到達某一點的路徑數目，等于下來，所以根據加法原理，到達某一點的路徑數目，等于到達其

56、相鄰上、左兩點的路徑數目之和，因此我們可以使到達其相鄰上、左兩點的路徑數目之和，因此我們可以使用逐行遞推的方法來求出從起始頂點到終點的路徑數目，用逐行遞推的方法來求出從起始頂點到終點的路徑數目，如果有障礙，只要將到達該點的路徑數目設置為即可。如果有障礙，只要將到達該點的路徑數目設置為即可。const x1:array1.8of integer=(2,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:

57、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(y+y1i1) do j:=j-1; for i:=j downto 1 do write(an,m,i); end.傳球游戲傳球游戲【問題描述】【問題描述】 上體育課的時候，小蠻的老師經常帶著同學們一起做游戲。這次，上體育課的時候，小蠻

58、的老師經常帶著同學們一起做游戲。這次，老師帶著同學們一起做傳球游戲。游戲規則是這樣的：老師帶著同學們一起做傳球游戲。游戲規則是這樣的：n個同學站成一個個同學站成一個圓圈，其中的一個同學手里拿著一個球，當老師吹哨子時開始傳球，每圓圈，其中的一個同學手里拿著一個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的一個（左右任意），當老個同學可以把球傳給自己左右的兩個同學中的一個（左右任意），當老師再次吹哨子時，傳球停止，此時，拿著球沒有傳出去的那個同學就是師再次吹哨子時，傳球停止，此時，拿著球沒有傳出去的那個同學就是敗者，要給大家表演一個節目。敗者，要給大家表演一個節目。 聰明的

59、小蠻提出了一個有趣的問題：聰明的小蠻提出了一個有趣的問題：有多少種不同的傳球方法可以有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了使得從小蠻手里開始傳的球，傳了m次后，又回到小蠻手里。次后，又回到小蠻手里。兩種傳球兩種傳球方法被視為不同的方法，當且僅當這兩種方法中，接到球的同學按接球方法被視為不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有順序組成的序列是不同的。比如有3個同學個同學1號、號、2號、號、3號，并假設小蠻號，并假設小蠻為一號，球傳了為一號，球傳了3次后回到小蠻手里的方式有次后回到小蠻手里的方式有 1- 2- 3- 1 和和 1- 3-

60、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