基本算法遞推法實例

關(guān)于基本算法遞推法實例第一頁，共八十六頁，2022年，8月28日采用具體化、特殊化的方法尋找規(guī)律

平面上n條直線，任兩條不平行，任三條不共點，問這n條直線把這平面劃分為多少個部分？第二頁，共八十六頁，2022年，8月28日

設(shè)這n條直線把這平面劃分成Fn個部分。先用具體化特殊化的方法尋找規(guī)律，如圖所示，易知的前幾項分別為

這些數(shù)字之間的規(guī)律性不很明顯，較難用不完全歸納法猜出Fn的一般表達式。但我們可以分析前后項之間的遞推關(guān)系，因為這些圖形中，后一個都是由前一個添加一條直線而得到的，添加一條直線便增加若干個區(qū)域。第三頁，共八十六頁，2022年，8月28日

一般地，設(shè)原來的符合題意的n-1條直線把這平面分成個區(qū)域，再增加一條直線l，就變成n條直線，按題設(shè)條件，這l必須與原有的n-1條直線各有一個交點,且這n-1個交點及原有的交點互不重合。這n-1個交點把l劃分成n個區(qū)間，每個區(qū)間把所在的原來區(qū)域一分為二，所以就相應(yīng)比原來另增了n個區(qū)域，即：

這樣，我們就找到了一個從Fn-1到Fn的的遞推式，再加上已知的初始值F1=2，就可以通過n-1步可重復(fù)的簡單運算推導(dǎo)出Fn的值。vara,i,n:longint;beginread(n);

a:=2;fori:=2tondo

a:=a+i;writeln(a);end.第四頁，共八十六頁，2022年，8月28日

在平面內(nèi)畫五條直線和一個圓，最多能把平面分成多少部分？第五頁，共八十六頁，2022年，8月28日平面上有8個圓，最多能把平面分成幾部分？

123456Fn=Fn-1+2×

(n-1)第六頁，共八十六頁，2022年，8月28日

圓周上兩個點將圓周分為兩半，在這兩點上寫上數(shù)1；然后將兩段半圓弧對分，在兩個分點上寫上相鄰兩點上的數(shù)之和；再把4段圓弧等分，在分點上寫上相鄰兩點上的數(shù)之和，如此繼續(xù)下去，問第6步后，圓周上所有點上的數(shù)之和是多少？第七頁，共八十六頁，2022年，8月28日分析:先可以采用作圖嘗試尋找規(guī)律。第一步：圓周上有兩個點，兩個數(shù)的和是1+1=2；第二步：圓周上有四個點，四個數(shù)的和是1+1+2+2=6；增加數(shù)之和恰好是第一步圓周上所有數(shù)之和的2倍。第三步：圓周上有八個點，八個數(shù)的和是1+1+2+2+3+3+3+3=18，增加數(shù)之和恰好是第二步數(shù)圓周上所有數(shù)之和的2倍。第四步：圓周上有十六個點，十六個數(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=3×An－1第八頁，共八十六頁，2022年，8月28日

在

n×n的正方形釘子板上（n是釘子板每邊上的釘子數(shù)），求連接任意兩個釘子所得到的不同長度的線段種數(shù).Fn=Fn-1+n第九頁，共八十六頁，2022年，8月28日

如圖1，是棱長為a的小正方體，圖2，圖3由這樣的小正方體擺放而成。按照這樣的方法繼續(xù)擺放，自上而下分別叫第一層、第二層、……、第n層，第n層的小正方體的個數(shù)記為sn。請寫出求sn的遞推公式。13610…第十頁，共八十六頁，2022年，8月28日

如圖，有邊長為1的等邊三角形卡片若干張，使用這些三角形卡片拼出邊長分別是2，3，4，…的等邊三角形（如圖所示）．根據(jù)圖形推斷，寫出求每個等邊三角形所用卡片總數(shù)sn的遞推公式．49162536…第十一頁，共八十六頁，2022年，8月28日

為慶?！拔濉ひ弧眹H勞動節(jié)，市政府決定在人民廣場上增設(shè)一排燈花，其設(shè)計由以下圖形逐步演變而成，其中圓圈代表燈花中的燈泡，n代表第n次演變過程，s代表第n次演變后的燈泡的個數(shù)。仔細(xì)觀察下列演變過程，當(dāng)n=6時，s=_____。94Sn=2×sn-1+2Sn=3×sn-1-2×sn-2第十二頁，共八十六頁，2022年，8月28日

某公共汽車線路上共有15個車站（包括起點站和終點站）。在每個站上車的人中，恰好在以后各站下去一個。要使行駛過程中每位乘客都有座位，車上至少要備有多少個座位？

從表中可以看出車上人數(shù)最多是56人，所以車上至少要準(zhǔn)備56個座位。第十三頁，共八十六頁，2022年，8月28日練習(xí)1將一張長方形的紙對折，可得到一條折痕，繼續(xù)對折，對折時每次折痕與上次的折痕保持平行，連續(xù)對折三次后，可得到７條折痕，那么對折n次，可得到幾條折痕？

第十四頁，共八十六頁，2022年，8月28日Fn=2*Fn-1+1vara,i,n:longint;beginread(n);

a:=1;fori:=2tondo

a:=2*a+1;writeln(a);end.第十五頁，共八十六頁，2022年，8月28日varf,s,i,n,j:longint;beginread(n);f:=1;fori:=2tondobegin

s:=1;forj:=1toi-1dos:=s*2;f:=f+s;end;writeln(f);end.Fn=Fn-1+2n-1

第十六頁，共八十六頁，2022年，8月28日var{加入高精度運算}a,b:array[1..100]ofinteger;i,j,n:integer;beginreadln(n);a[100]:=1;{n=1時}b[100]:=1;{20=1}fori:=2tondobegin

forj:=100downto1dob[j]:=b[j]*2;{遞推出2i-1}forj:=100downto2doifb[j]>=10thenbeginb[j-1]:=b[j-1]+b[j]div10;b[j]:=b[j]mod10;end;

forj:=100downto1dobegina[j]:=a[j]+b[j];ifa[j]>=10thenbegina[j-1]:=a[j-1]+a[j]div10;a[j]:=a[j]mod10;end;end;end;j:=1;whilea[j]=0doj:=j+1;fori:=jto100dowrite(a[i]);end.第十七頁，共八十六頁，2022年，8月28日練習(xí)2

如圖,第一次把三角形剪去一個角后,圖中最多有四個角,第二次再把新產(chǎn)生的角各剪一刀,…,如此下去,每一次都是把新產(chǎn)生的角各剪一刀,則第n次剪好后,圖中最多有多少個角?46101834…Fn=Fn-1+2n-1第十八頁，共八十六頁，2022年，8月28日varf,s,i,n,j:longint;beginread(n);f:=4;fori:=2tondobegin

s:=1;forj:=1toi-1dos:=s*2;f:=f+s;end;writeln(f);end.第十九頁，共八十六頁，2022年，8月28日vara,b:array[1..100]oflongint;i,j,n:longint;beginreadln(n);

a[100]:=4;b[100]:=1;fori:=2tondobeginforj:=100downto1dob[j]:=b[j]*2;forj:=100downto2doifb[j]>=10thenbeginb[j-1]:=b[j-1]+b[j]div10;b[j]:=b[j]mod10;end;forj:=100downto1dobegina[j]:=a[j]+b[j];ifa[j]>=10thenbegina[j-1]:=a[j-1]+a[j]div10;a[j]:=a[j]mod10;end;end;end;j:=1;whilea[j]=0doj:=j+1;fori:=jto100dowrite(a[i]);end.第二十頁，共八十六頁，2022年，8月28日練習(xí)3

下圖中把大正方形各邊平均分成了5份，此時有55個正方形。如果把正方形各邊平均分成n份，那么得到的正方形總數(shù)為多少？52+42+32+22+12=55n2+(n-1)2+(n-2)2+…+22+1Fn=Fn-1+n2vara,i,n:longint;beginread(n);

a:=1;fori:=2tondo

a:=a+i*i;writeln(a);end.第二十一頁，共八十六頁，2022年，8月28日Var{加入高精度運算}a:array[1..25]oflongint;i,j,k,x,n:longint;beginreadln(n);a[25]:=1;{n=1時}fori:=2tondobeginx:=i*i;

forj:=25downto1dobegina[j]:=a[j]+xmod10;

ifa[j]>=10thenbegina[j]:=a[j]-10;a[j-1]:=a[j-1]+1;end;x:=xdiv10;end;end;j:=1;whilea[j]=0doj:=j+1;fori:=jto25dowrite(a[i]);end.第二十二頁，共八十六頁，2022年，8月28日練習(xí)4

如圖，由等圓組成的一組圖中，第1個圖由1個圓組成，第2個圖由7個圓組成，第3個圖由19個圓組成，……，按照這樣的規(guī)律排列下去，則第9個圖形由__________個圓組成。217可得遞推公式:Fn=Fn-1+6*（n－1）vara,i,n:longint;beginread(n);

a:=1;fori:=2tondo

a:=a+6*(i-1);writeln(a);end.第二十三頁，共八十六頁，2022年，8月28日var{加入高精度運算}a:array[1..50]oflongint;i,j,k,x,n:longint;beginreadln(n);a[50]:=1;fori:=2tondobegin

x:=(i-1)*6;

forj:=50downto1dobeginx:=x+a[j];a[j]:=xmod10;x:=xdiv10;end;end;j:=1;whilea[j]=0doj:=j+1;fori:=jto50dowrite(a[i]);end.第二十四頁，共八十六頁，2022年，8月28日練習(xí)5

已知三角形ABC的面積為10，延長邊BC到點D，使BC=CD，延長邊CA到點E，使CA=AE，延長邊AB到點F，使AB=BF，連結(jié)DE,EF,FD,得到三角形DEF,并記圖中陰影部分面積為S1,此時我們稱三角形ABC向外擴展了一次.求經(jīng)過N次擴展后圖中陰影部分的面積Sn.Fn=7*Fn-1

(Fn為第n次擴展后整個三角形的面積)F0=10Sn=Fn-Fn-1第二十五頁，共八十六頁，2022年，8月28日constmax=100;varf1,f2,s:array[1..max]oflongint;i,j,k,l,n:longint;beginreadln(n);f1[max]:=0;f1[max-1]:=1;{F0=10}fori:=1tondobeginf2:=f1;

k:=0;{×7}forj:=maxdownto1dobegink:=k+f1[j]*7;f1[j]:=kmod10;k:=kdiv10;end;end;

fori:=maxdownto1do{相減}beginiff1[i]<f2[i]thenbeginf1[i]:=f1[i]+10;f1[i-1]:=f1[i-1]-1;end;s[i]:=f1[i]-f2[i];end;j:=1;whiles[j]=0doj:=j+1;fori:=jtomaxdowrite(s[i]);end.第二十六頁，共八十六頁，2022年，8月28日Hanoi雙塔問題

給定A、B、C三根足夠長的細(xì)柱，在A柱上放有2n個中間有孔的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區(qū)分的（下圖為n=3的情形）?，F(xiàn)要將這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求：（1）每次只能移動一個圓盤；（2）A、B、C三根細(xì)柱上的圓盤都要保持上小下大的順序；任務(wù)：設(shè)An為2n個圓盤完成上述任務(wù)所需的最少移動次數(shù)，對于輸入的n，輸出An。第二十七頁，共八十六頁，2022年，8月28日

輸入文件hanoi.in為一個正整數(shù)n，表示在A柱上放有2n個圓盤。輸出文件hanoi.out僅一行，包含一個正整數(shù)，為完成上述任務(wù)所需的最少移動次數(shù)An。

【樣例1】hanoi.inhanoi.out12【樣例2】hanoi.inhanoi.out26【限制】

對于50%的數(shù)據(jù)，1<=n<=25

對于100%的數(shù)據(jù)，1<=n<=200【提示】

設(shè)法建立An與An-1的遞推關(guān)系式。

第二十八頁，共八十六頁，2022年，8月28日解題思路:遞推+高精度1.假設(shè)當(dāng)前要移動A軸的N層，即2N個盤子，則需要將N-1層的2N-2個盤子移動到B軸(輔助軸)上，再將第N層的2個盤子移動到C軸上（目標(biāo)軸），然后再將那N-1層的2N-2個盤子移動到目標(biāo)軸，共需要2*An-1+2次。2.遞推關(guān)系式是：An=2*An-1+2

A0=026143062126254…還可以：An=An-1+2n

第二十九頁，共八十六頁，2022年，8月28日vara:array[1..62]ofinteger;{存放大數(shù)}i,j,n:integer;f:boolean;beginassign(input,'hanoi.in');assign(output,'hanoi.out');reset(input);rewrite(output);readln(n);{層數(shù)}fori:=1to62doa[i]:=0;{初值}fori:=1tondo{遞推n次}begin

forj:=1to62doa[j]:=a[j]*2;{先乘2}a[1]:=a[1]+2;{再在個位上加2}forj:=1to62doifa[j]>9thenbegin{處理進位}a[j+1]:=a[j+1]+1;a[j]:=a[j]mod10;end;end;f:=false;fori:=62downto1dobeginifa[i]<>0thenf:=true;iffthenwrite(a[i]);end;close(input);close(output);end.第三十頁，共八十六頁，2022年，8月28日

在上面的一些例題中，遞推過程中的某個狀態(tài)只與前面的一個狀態(tài)有關(guān)，遞推關(guān)系并不復(fù)雜。如果在遞推中的某個狀態(tài)與前面的幾個狀態(tài)、甚至所有狀態(tài)都有關(guān)，就不容易找出遞推關(guān)系式，這就需要我們對實際問題進行分析與歸納，從中找到突破口，總結(jié)出遞推關(guān)系式。第三十一頁，共八十六頁，2022年，8月28日

意大利著名數(shù)學(xué)家斐波那契在研究兔子繁殖問題時，發(fā)現(xiàn)有這樣一組數(shù)：1，1，2，3，5，8，13，…，其中從第三個數(shù)起，每一個數(shù)都等于它前面兩上數(shù)的和?，F(xiàn)以這組數(shù)中的各個數(shù)作為正方形的邊長構(gòu)造如下正方形：

再分別依次從左到右取2個、3個、4個、5個正方形拼成如下矩形并記為①、②、③、④…若按此規(guī)律繼續(xù)作矩形，則序號為⑩的矩形周長是＿＿＿。466第三十二頁，共八十六頁，2022年，8月28日【問題描述】

一只蜜蜂在上圖所示的數(shù)字蜂房上爬動,已知它只能從標(biāo)號小的蜂房爬到標(biāo)號大的相鄰蜂房,現(xiàn)在問你：蜜蜂從蜂房M開始爬到蜂房N（M<N），有多少種爬行路線？【輸入格式】輸入M，N的值。(1<=M,N<=1000)【輸出格式】爬行有多少種路線?！据斎霕永縝ee.in114【輸出樣例】bee.out377第三十三頁，共八十六頁，2022年，8月28日varm,n,i,j,x:longint;a:array[1..1000,1..64]ofinteger;beginreadln(m,n);a[m+1,64]:=1;a[m+2,64]:=2;fori:=m+3tondobegin

x:=0;forj:=64downto1dobeginx:=x+a[i-2,j]+a[i-1,j];a[i,j]:=xmod10;x:=xdiv10;end;end;j:=1;whilea[n,j]=0doj:=j+1;fori:=jto64dowrite(a[n,i]);writeln;end.第三十四頁，共八十六頁，2022年，8月28日通過合理分步、恰當(dāng)分類找出遞推關(guān)系第三十五頁，共八十六頁，2022年，8月28日

欲登上第10級樓梯，如果規(guī)定每步只能跨上一級或兩級，則不同的走法共有()

89種

登樓梯第三十六頁，共八十六頁，2022年，8月28日以某位置劃分求遞推式第三十七頁，共八十六頁，2022年，8月28日

若用１或２兩數(shù)字寫ｎ位數(shù)，其中任意相鄰兩個位置不全為1。記ｎ位數(shù)的個數(shù)為ｆ(n)，則ｆ(8)=

；用１、２、３三個數(shù)字寫ｎ位數(shù)，要求數(shù)中不出現(xiàn)緊挨著的兩個１。記ｎ位數(shù)的個數(shù)為g(n)，則g(8)=

。符合條件的ｎ位數(shù)可分為兩類：Ⅰ．首位是２，則以下ｎ－１位數(shù)符合條件的個數(shù)為ｆ(n-1)；Ⅱ．首位是１，則第二位應(yīng)是２，以下ｎ－２位的個數(shù)為ｆ(n-2)．于是,ｆ（ｎ）＝ｆ（ｎ－１）＋ｆ（ｎ－２）．故ｆ（ｎ）為斐波那契數(shù)列．∵ｆ（１）＝２，f（２）＝３∴ｆ（８）＝55．第三十八頁，共八十六頁，2022年，8月28日設(shè)符合條件的ｎ位數(shù)共有g(shù)(ｎ)種，按首位劃分可分成：Ⅰ．首位是２或３，則以下ｎ－１位各有g(shù)(ｎ－１)個，共２g(ｎ－１)個；Ⅱ．首位是１，第二位只能為２或３，共有２g(ｎ－２)個，故g(ｎ)＝２g(ｎ－１)＋２g(ｎ－２)個．由初始條件g(1)＝３；g(2)＝８；求得g(8)＝3344.第三十九頁，共八十六頁，2022年，8月28日

有2×n的一個長方形方格，用一個1×2的骨牌鋪滿方格。例如n=3時，為2×3方格。此時用一個1×2的骨牌鋪滿方格，共有如下3種鋪法：

試對給出的任意一個n（n>0），求出鋪法總數(shù)的遞推公式。F(1)=1F(2)=2F(n)=F(n-2)+F(n-1)(n>=3)第四十頁，共八十六頁，2022年，8月28日

如果有n元錢,每天去購買下列三種商品之一:蔬菜要用1元錢,豬肉要用2元錢,雞蛋要用２元錢．用An表示把這n元錢用完的所有可能的用法的總數(shù)．如果第一天買蔬菜，則用去１元錢，還剩n-1元錢，這n-1元錢的用法有Ａn-1種；如果第一天買豬肉，則用去２元錢，還剩n-２元錢，這n-２元錢的用法有Ａn-2種；如果第一天買雞蛋，則用去２元錢，還剩n-２元錢，這n-２元錢的用法有Ａn-2種；所以，Ａn=Ａn-1+2Ａn-2第四十一頁，共八十六頁，2022年，8月28日

有排成一行的ｎ個方格，用紅、黃、藍(lán)三色涂每個格子，每格涂一色，要求任何相鄰的格不同色，且首尾兩格也不同色。問有多少種涂法？解：設(shè)共有ａn種涂法，易見ａ1＝３，ａ2＝６，ａ3＝６，且當(dāng)ｎ≥４時，將ｎ個格子依次編號后，格１與格（n-1）不相鄰。情形１：格（n-1）涂色與格１不同，此時格ｎ只有一色可涂，且前（n-1）格滿足首尾兩格不同色，故有ａn-1種涂色方法。情形２：格（n-1）涂色與格１相同，此時格（n-2）與格１涂色必然不同，不然，格（n-1）與（n-2）相同，于是前（n-2）格有ａn-2種涂色法。因為格ｎ與格１不同色，有兩種涂色法，故共有２ａn-2種涂色法。綜上，可得ａn＝ａn-1＋２ａn-2（ｎ≥４）按前n-1格首尾關(guān)系討論第四十二頁，共八十六頁，2022年，8月28日錯位排列

五個人排成一列，重新站隊時，各人都不站在原來的位置上，那么不同的站隊方式共有()

（A）60種（B）44種（C）36種（D）24種

解：首先我們把人數(shù)推廣到n個人，即n個人排成一列，重新站隊時，各人都不站在原來的位置上。設(shè)滿足這樣的站隊方式有An種，現(xiàn)在我們通過合理分步，恰當(dāng)分類來找出遞推關(guān)系：

第一步：第一個人不站在原來的第一個位置，有n-1種站法。

第二步：假設(shè)第一個人站在第2個位置，則第二個人的站法又可以分為兩類：第一類，第二個人恰好站在第一個位置，則余下的n-2個人有An-2種站隊方式；第二類，第二個人不站在第一個位置，則就是第二個人不站在第一個位置，第三個人不站在第三個位置，第四個人不站在第四個位置，……，第n個人不站在第n個位置，所以有An-1種站隊方式。由分步計數(shù)原理和分類計數(shù)原理，我們便得到了數(shù)列的遞推關(guān)系式： ，顯然，再由遞推關(guān)系有，第四十三頁，共八十六頁，2022年，8月28日

在書架上放有編號為1，2，…，n的n本書?，F(xiàn)將n本書全部取下然后再放回去，當(dāng)放回去時要求每本書都不能放在原來的位置上。例如：n=3時：原來位置為：123

放回去時只能為：312或231這兩種問題：求當(dāng)n=5時滿足以上條件的放法共有多少種？第四十四頁，共八十六頁，2022年，8月28日染色問題

用4種不同顏色涂四邊形的4個頂點，要求每點染一種顏色，相鄰的頂點染不同的顏色，則不同的染色方法有()（A）84種 （B）72種 （C）48種 （D）24種A第四十五頁，共八十六頁，2022年，8月28日第四十六頁，共八十六頁，2022年，8月28日Vari,j,k,m,n:longint;a:array[1..10]oflongint;functionjc(k:integer):longint;{求K!}vari,j:longint;beginj:=1;fori:=2tokdoj:=j*i;jc:=j;end;beginreadln(n,m);{n是頂點數(shù)，m是顏色數(shù)}a[3]:=jc(m)divjc(m-3);{初值

}fori:=4tondobeginj:=1;fork:=1toi-1doj:=j*(m-1);{}a[i]:=m*j-a[i-1];{遞推公式}end;writeln(a[n]);end.a[3]:=m*(m-1)*(m-2)第四十七頁，共八十六頁，2022年，8月28日如圖，一個地區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有四種顏色可供選擇，則不同的著色方法共有

種。第四十八頁，共八十六頁，2022年，8月28日

圖中2、3、4、5四個區(qū)域圍成一個四邊形，因此可以把它們看成是一個四邊形的4個頂點，而區(qū)域1就是這個四邊形對角線的交點。第一步，先涂區(qū)域1，有4種涂法。第二步，由于區(qū)域1跟其余四個區(qū)域都相鄰，因此涂1的顏色不能用來涂其余的四個區(qū)域，因此第二步相當(dāng)于用3種顏色來涂一個四邊形的四個頂點，不難得出

所以，由分步計數(shù)原理，得出共有種涂法。第四十九頁，共八十六頁，2022年，8月28日

某城市在中心廣場建造一個花圃，花圃分成6個部分(如圖)，現(xiàn)要栽種4種不同顏色的花，每部分栽種一種且相鄰部分不能栽種同樣顏色的花，不同的栽種方法共有

種。1204×30=120第五十頁，共八十六頁，2022年，8月28日傳球問題

4個人進行籃球訓(xùn)練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方式？60第五十一頁，共八十六頁，2022年，8月28日第五十二頁，共八十六頁，2022年，8月28日分析:設(shè)第n次傳球后，球又回到甲手中的傳球方式有an種?？梢韵胂笄皀-1次傳球，如果每一次傳球都任選其他三人中的一人進行接球，則每次傳球都有3種可能，由乘法原理，共有3×3×……×3=3n-1

種傳球方法。這些傳球方式可以分為兩類:

一類是第n-1次恰好傳到甲手中，這有an-1種傳法，它們不符合要求，因為這樣第n次無法再把球傳給甲；另一類是第n-1次傳球，球不在甲手中，第n次持球人再將球傳給甲，有an種傳法。根據(jù)加法原理，有an-1+an=3n-1

。由于甲是發(fā)球者，一次傳球后球又回到甲手中的傳球方式是不存在的，所以a1=0。利用遞推關(guān)系可以得到

a2=3-0=3，

a3=3×3-3=6，

a4=3×3×3-6=21，

a5=3×3×3×3-21=60。這說明經(jīng)過5次傳球后，球仍回到甲手中的傳球方法有60種。第五十三頁，共八十六頁，2022年，8月28日vara:array[1..100]oflongint;n,m,i,j:longint;beginreadln(n,m);a[1]:=0;j:=1;fori:=2tomdobeginj:=j*(n-1);{先求出(n-1)i-1}a[i]:=j-a[i-1];end;writeln(a[m]);end.第五十四頁，共八十六頁，2022年，8月28日var{加入高精度運算}a:array[1..100,1..100]ofinteger;s:array[1..100]ofinteger;i,j,t,k,n,m:longint;beginreadln(n,m);a[1,100]:=0;s[100]:=1;fori:=2tomdobeginforj:=100downto1dos[j]:=s[j]*(n-1);forj:=100downto1doifs[j]>9thenbegins[j-1]:=s[j-1]+s[j]div10;s[j]:=s[j]mod10;end;forj:=100downto1doa[i,j]:=s[j]-a[i-1,j];forj:=100downto1doifa[i,j]<0thenbegina[i,j-1]:=a[i,j-1]-1;a[i,j]:=a[i,j]+10;end;end;j:=1;whilea[m,j]=0doj:=j+1;fori:=jto100dowrite(a[m,i]);end.第五十五頁，共八十六頁，2022年，8月28日凸多邊形劃分在一個凸多邊形中，通過若干條互不相交的對角線，把這個凸多邊形剖分成了若干個三角形?，F(xiàn)在的任務(wù)是根據(jù)輸入的凸多邊形的邊數(shù)，求不同剖分的方案數(shù)Cn。比如當(dāng)n=5時，有如下5種不同的方案，所以C5=5。輸入文件14.in：一個正整數(shù)，表示凸多邊形的邊數(shù)。(n<=21)輸出文件14.out：一個正整數(shù)，表示方案總數(shù)。第五十六頁，共八十六頁，2022年，8月28日如圖所示，我們以p1pn這條邊為基準(zhǔn)邊，再找pk來構(gòu)成三角形，則原凸n邊形被剖解成了△p1pkpn和兩個凸多邊形，其中一個是由p1,p2,…,pk構(gòu)成的凸k邊形，另一個是由pk,pk+1,…,pn構(gòu)成的凸n-k+1邊形，根據(jù)乘法原理，選擇pk這個頂點的分解方案為種。而k可以選2到n-1，所以根據(jù)加法原理，得出總的方案數(shù)為

注意，就這個遞推關(guān)系而言，臨界值應(yīng)為C2=1，而不是C3=1，否則遞推關(guān)系就得不到正確解，這與原問題的實際情況可能不符（即兩邊形），其實這只是理解上的差異．P1PnP2P3PkPn-1Pn-2第五十七頁，共八十六頁，2022年，8月28日constmax=21;varc:array[2..max]oflongint;n,i,k:integer;total:longint;beginreadln(n);c[2]:=1;fori:=3tondobeginc[i]:=0;fork:=2toi-1doc[i]:=c[i]+c[k]*c[i-k+1];end;writeln(c[n]);end.第五十八頁，共八十六頁，2022年，8月28日求路徑總數(shù)下圖是某居民小區(qū)道路圖，小明每天由家（Ａ點）到學(xué)校（Ｂ點），他只沿道路向上或向右行走，那么他最多有（）天走不同線路？ＡＢ４９５１１１１１１１１１１１１２３４５６７８９３６10

15

21

28

36

454

10

2035

56

84

120

1655

15

3570

126

210

330495第五十九頁，共八十六頁，2022年，8月28日vari,j,n,m:integer;a:array[1..20,1..20]oflongint;beginread(n,m);fillchar(a,sizeof(a),0);

fori:=1tondoa[I,1]:=1;forj:=1tomdoa[1,j]:=1;fori:=2tondoforj:=2tomdo

a[I,j]:=a[I,j-1]+a[i-1,j];writeln(a[n,m]);end.要想到達坐標(biāo)為（i,j）的頂點的話，必定要經(jīng)過坐標(biāo)為（i-1,j）的頂點或坐標(biāo)為（i,j-1）的頂點，設(shè)a(I,j)表示從點A到頂點(I,j)的路徑總條數(shù)，則a(I,j)=a(I,j-1)+a(i-1,j)輸入：59輸出：495第六十頁，共八十六頁，2022年，8月28日街道路徑

設(shè)有一個N＊M（1<=N<=50，1<=M<=50）的街道，規(guī)定行人從A(1,1)出發(fā)，在街道上只能向東或北行走。若在此街道中，設(shè)置一個矩形障礙區(qū)域（包括圍住該區(qū)域的的街道）不讓行人通行，如上圖中用“＊”表示的部分。此矩形障礙區(qū)域用2對頂點坐標(biāo)給出，如上圖中的2對頂點坐標(biāo)為(2，2),(8，4)，此時從A出發(fā)到達B的路徑有兩條?，F(xiàn)給出N、M，同時再給出此街道中的矩形障礙區(qū)域的2對頂點坐標(biāo)(x1,y1)，（x2,y2），請求出此時所有從A出發(fā)到達B的路徑的條數(shù)。

由于在街上只能向東或北方向行走，因此要想達到坐標(biāo)為（i,j）的頂點的話，必定要經(jīng)過坐標(biāo)為（i-1,j）的頂點或坐標(biāo)為（i,j-1）的頂點，假設(shè)從起始頂點到達坐標(biāo)為（i,j）的頂點的路徑總數(shù)為a[i,j]，則a[i,j]=a[i-1,j]+a[i,j-1]。因此我們可以采用逐行遞推的方法來求出從起始頂點到達任意一個頂點的路徑總數(shù)。第六十一頁，共八十六頁，2022年，8月28日varn,m,i,j,x1,x2,y1,y2:integer;a:array[1..50,1..50]oflongint;b:array[1..50,1..50]ofboolean;beginreadln(n,m);{行列要分清}readln(x1,y1,x2,y2);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),true);fori:=y1toy2doforj:=x1tox2dob[i,j]:=false;

fori:=1tomdobeginifnot(b[i,1])thenbreak;a[i,1]:=1;end;forj:=1tondobeginifnot(b[1,j])thenbreak;a[1,j]:=1;end;fori:=2tomdoforj:=2tondoifb[i,j]thena[i,j]:=a[i-1,j]+a[i,j-1];write(a[m,n]);end.有可能障礙區(qū)域靠邊如輸入95284應(yīng)輸出1第六十二頁，共八十六頁，2022年，8月28日

Var{加入高精度運算}n,m,i,j,x1,x2,y1,y2,k,g:integer;a:array[1..50,1..50,1..30]oflongint;b:array[1..50,1..50]ofboolean;beginreadln(n,m);readln(x1,y1,x2,y2);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),true);fori:=y1toy2doforj:=x1tox2dob[i,j]:=false;fori:=1tomdobeginifnot(b[i,1])thenbreak;a[i,1,1]:=1;end;forj:=1tondobeginifnot(b[1,j])thenbreak;a[1,j,1]:=1;end;fori:=2tomdoforj:=2tondoifb[i,j]thenbegin

g:=0;fork:=1to30dobegin

a[i,j,k]:=a[i-1,j,k]+a[i,j-1,k]+g;g:=a[i,j,k]div10;a[i,j,k]:=a[i,j,k]mod10;end;end;

j:=30;fori:=30downto1doifa[m,n,i]=0thenj:=j-1;fori:=jdownto1dowrite(a[m,n,i]);end.第六十三頁，共八十六頁，2022年，8月28日過河卒

如圖，A點有一個過河卒，需要走到目標(biāo)B點。卒行走規(guī)則：可以向下、或者向右。同時在棋盤上的任一點有一個對方的馬（如上圖的C點），該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。例如上圖C點上的馬可以控制9個點（圖中的P1，P2…P8和C）。卒不能通過對方馬的控制點。棋盤用坐標(biāo)表示，A點（0，0）、B點（n,m）(n,m為不超過20的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的（約定:C<>A，同時C<>B）?，F(xiàn)在要求你計算出卒從A點能夠到達B點的路徑的條數(shù)。輸入文件5.in，只有一行，共4個正整數(shù)，前2個數(shù)表示B點的坐標(biāo)，后2個數(shù)表示對方馬的坐標(biāo)。輸出文件5.out，只有一行，一個整數(shù)（表示路徑的條數(shù)）。樣例:

輸入6632

輸出17分析:要到達棋盤上的一個點，只能從左邊過來或是從上面下來，所以根據(jù)加法原理，到達某一點的路徑數(shù)目，等于到達其相鄰上、左兩點的路徑數(shù)目之和，因此我們可以使用逐行遞推的方法來求出從起始頂點到終點的路徑數(shù)目，如果有障礙，只要將到達該點的路徑數(shù)目設(shè)置為０即可。第六十四頁，共八十六頁，2022年，8月28日constx1:array[1..8]ofinteger=(2,2,1,-1,-2,-2,-1,1);y1:array[1..8]ofinteger=(1,-1,-2,-2,-1,1,2,2);varb:array[0..20,0..20]ofboolean;i,j,x,y,k,p,n,m:integer;a:array[0..20,0..20]ofinteger;begin

readln(n,m,x,y);fillchar(b,sizeof(b),true);fillchar(a,sizeof(a),0);

b[x,y]:=false;

fori:=1to8doif(x+x1[i]>=0)and(x+x1[i]<=n)and(y+y1[i]>=0)and(y+y1[i]<=m)thenb[x+x1[i],y+y1[i]]:=false;

fori:=0tondobegin

ifnot(b[i,0])thenbreak;

a[i,0]:=1;

end;fori:=0tomdobegin

ifnot(b[0,i])thenbreak;

a[0,i]:=1;

end;(2,1)(2,-1)(1,-2)(-1,-2)(-2,-1)(-2,1)(-1,2)(1,2)fori:=1tondoforj:=1tomdoifb[i,j]then

a[i,j]:=a[i-1,j]+a[i,j-1];write(a[n,m]);end.有些控制點有可能在邊上第六十五頁，共八十六頁，2022年，8月28日const{加入高精度運算}L=30;x1:array[1..8]ofinteger=(2,2,1,-1,-2,-2,-1,1);y1:array[1..8]ofinteger=(1,-1,-2,-2,-1,1,2,2);varb:array[0..20,0..20]ofboolean;i,j,x,y,k,p,n,m:integer;a:array[0..20,0..20,1..L]ofinteger;begin

readln(n,m,x,y);fillchar(b,sizeof(b),true);fillchar(a,sizeof(a),0);

b[x,y]:=false;

fori:=1to8doif(x+x1[i]>=0)and(x+x1[i]<=n)and(y+y1[i]>=0)and(y+y1[i]<=m)thenb[x+x1[i],y+y1[i]]:=false;

fori:=0tondobegin

ifnot(b[i,0])thenbreak;

a[i,0,1]:=1;

end;fori:=0tomdobegin

ifnot(b[0,i])thenbreak;

a[0,i,1]:=1;

end;第六十六頁，共八十六頁，2022年，8月28日fori:=1tondoforj:=1tomdoifb[i,j]thenbegin

k:=0;

forp:=1toLdobegina[i,j,p]:=a[i-1,j,p]+a[i,j-1,p]+k;k:=a[i,j,p]div10;a[i,j,p]:=a[i,j,p]mod10;end;end;j:=L;while(a[n,m,j]=0)and(j>1)doj:=j-1;fori:=jdownto1dowrite(a[n,m,i]);end.第六十七頁，共八十六頁，2022年，8月28日傳球游戲【問題描述】

上體育課的時候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著同學(xué)們一起做傳球游戲。游戲規(guī)則是這樣的：n個同學(xué)站成一個圓圈，其中的一個同學(xué)手里拿著一個球，當(dāng)老師吹哨子時開始傳球，每個同學(xué)可以把球傳給自己左右的兩個同學(xué)中的一個（左右任意），當(dāng)老師再次吹哨子時，傳球停止，此時，拿著球沒有傳出去的那個同學(xué)就是敗者，要給大家表演一個節(jié)目。聰明的小蠻提出了一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m次后，又回到小蠻手里。兩種傳球方法被視為不同的方法，當(dāng)且僅當(dāng)這兩種方法中，接到球的同學(xué)按接球順序組成的序列是不同的。比如有3個同學(xué)1號、2號、3號，并假設(shè)小蠻為一號，球傳了3次后回到小蠻手里的方式有1->2->3->1和1->3->2->1，共2種。第六十八頁，共八十六頁，2022年，8月28日【輸入】

輸入文件ball.in共一行，有兩個用空格隔開的整數(shù)n，m（3<=n<=30，1<=m<=30）?！据敵觥?/p>

輸出文件ball.out共一行，有一個整數(shù)，表示符合題意的方法數(shù)。【輸入輸出樣例】ball.in3ball.out32【限制】40%的數(shù)據(jù)滿足：3<=n<=30，1<=m<=20100%的數(shù)據(jù)滿足：3<=n<=30，1<=m<=30第六十九頁，共八十六頁，2022年，8月28日分析：設(shè)f(i,k)表示經(jīng)過k次傳球到編號為i的人手中的方案數(shù)?？梢园l(fā)現(xiàn)，傳到i號同學(xué)的球只能來自于i的左邊一個同學(xué)或者右邊一個同學(xué)，這兩個同學(xué)的編號分別是i-1、i+1，所以可以得到以下的遞推公式：f(i,k)=f(i-1,k-1)+f(i+1,k-1)

當(dāng)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號同學(xué)開始傳球，可確定初始條件：f(1,0)=1

可根據(jù)傳球次數(shù)進行遞推，結(jié)果在f(1,m)中。第七十頁，共八十六頁，2022年，8月28日vari,j,k,n,m:longint;f:array[0..30,0..30]oflongint;beginreadln(n,m);fillchar(f,sizeof(f),0);f[1,0]:=1;fork:=1tomdobeginf[1,k]:=f[2,k-1]+f[n,k-1];{當(dāng)球在1號同學(xué)時}fori:=2ton-1dof[i,k]:=f[i-1,k-1]+f[i+1,k-1];f[n,k]:=f[n-1,k-1]+f[1,k-1];{當(dāng)球在n號同學(xué)時}end;write(f[1,m]);end.第七十一頁，共八十六頁，2022年，8月28日傳球問題

4個人進行籃球訓(xùn)練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方式？第七十二頁，共八十六頁，2022年，8月28日Varn,m,i,j,k,l,g:longint;a:array[0..30,1..30,1..100]oflongint;beginread(n,m);a[0,1,1]:=1;fori:=1tomdobeginforj:=1tondofork:=1tondoifj<>kthenbeging:=0;forl:=1to100dobeging:=a[i,j,l]+a[i-1,k,l]+g;a[i,j,l]:=gmod10;g:=gdiv10;end;end;end;l:=100;whilea[m,1,l]=0dol:=l-1;fori:=ldownto1dowrite(a[m,1,i]);end.第七十三頁，共八十六頁，2022年，8月28日整數(shù)劃分

把一個正整數(shù)N劃分成一些正整數(shù)的和，例如：N

=n1+n2+…+nk

且滿足1<=n1<=n2<=…<=nk<=N，叫做N的一個劃分。求不同的劃分的數(shù)量。當(dāng)n=4時，劃分?jǐn)?shù)為4。

4=1+1+1+1；

4=1+1+2；

4=1+3；

4=2+2；

第七十四頁，共八十六頁，2022年，8月28日設(shè)表示把正整數(shù)a做分劃、其中最大的一份恰好是b的方案總數(shù)。設(shè)表示把正整數(shù)a做分劃、其中最大的一份不大于b的方案總數(shù)。顯然有：所以：當(dāng)i<j時，根據(jù)的含義，無意義。當(dāng)j=1時，對i做任意剖分、其中最大的一份不大于1的方案只有一種。即：i=1+1+1+…+1（共i個1）;所以：=14=1+1+1+1；

4=1+1+2；

4=2+2；

4=1+3；第七十五頁，共八十六頁，2022年，8月28日根據(jù)以上分析可得到如下遞推公式：

=

=1{初始條件}

我們可以按照i、j遞增的順序來計算的值，這樣在計算的時候，和都已經(jīng)得到，故我們只用進行一次簡單的加法運算即可.

最后的g(n,n-1)即為所求。第七十六頁，共八十六頁，2022年，8月28日varg:array[0..100,0..100]oflongint;n,i,j:integer;beginreadln(n);fillchar(g,sizeof(g),0);forj:=0tondog[j,1]:=1;{初始條件}

fori:=0tondoforj:=2tondoifi>=jtheng[i,j]:=g[i-j,j]+g[i,j-1]elseg[i,j]:=g[i,j-1];writeln(g[n,n-1]);end.第七十七頁，共八十六頁，2022年，8月28日倒推法

我們把由已知初始值為Ｆ1，通過遞推關(guān)系式Ｆn=g(Fn-1)求出其最終結(jié)果Fn的遞推方式稱為順推法．同理，把已知最終結(jié)果為Fn，通過遞推關(guān)系式Ｆn-1=g(Fn)，求出其初始值Ｆ1的遞推方式稱之為倒推法。第七十八頁，共八十六頁，2022年，8月28日

四個人做火柴游戲,每一局三個人贏,一個人輸,輸者要按贏者手中贏得火柴根數(shù)賠償,即贏者手中有多少根火柴,輸者就賠他多少?4次之后,每人恰好輸過一次而且手中都恰好有16根?求四人原有火柴數(shù)?把第一局輸?shù)娜擞洖椋?，把第二局輸?shù)娜擞洖椋拢训谌州數(shù)娜擞洖椋?，把第四局輸?shù)娜擞洖椋模玫雇朔芍海粒拢茫模矗保叮保叮保叮保叮常福福福矗埃玻矗矗常叮玻埃保玻常矗保福保伴_始３３１７９５第七十九頁，共八十六頁，2022年，8月28日騎士游歷

設(shè)有一個n*m的棋盤(2<=n<=50，2<=m<=50)，如上圖，在棋盤上左下角有一個