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

關(guān)于基本算法遞推法實(shí)例第1頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三采用具體化、特殊化的方法尋找規(guī)律

平面上n條直線，任兩條不平行，任三條不共點(diǎn)，問(wèn)這n條直線把這平面劃分為多少個(gè)部分？第2頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

設(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è)，2023年5月2日，星期三

一般地，設(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的值。vara,i,n:longint;beginread(n);

a:=2;fori:=2tondo

a:=a+i;writeln(a);end.第4頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

在平面內(nèi)畫五條直線和一個(gè)圓，最多能把平面分成多少部分？第5頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三平面上有8個(gè)圓，最多能把平面分成幾部分？

123456Fn=Fn-1+2×

(n-1)第6頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

圓周上兩個(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è)，2023年5月2日，星期三分析:先可以采用作圖嘗試尋找規(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=3×An－1第8頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

在

n×n的正方形釘子板上（n是釘子板每邊上的釘子數(shù)），求連接任意兩個(gè)釘子所得到的不同長(zhǎng)度的線段種數(shù).Fn=Fn-1+n第9頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

如圖1，是棱長(zhǎng)為a的小正方體，圖2，圖3由這樣的小正方體擺放而成。按照這樣的方法繼續(xù)擺放，自上而下分別叫第一層、第二層、……、第n層，第n層的小正方體的個(gè)數(shù)記為sn。請(qǐng)寫出求sn的遞推公式。13610…第10頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

如圖，有邊長(zhǎng)為1的等邊三角形卡片若干張，使用這些三角形卡片拼出邊長(zhǎng)分別是2，3，4，…的等邊三角形（如圖所示）．根據(jù)圖形推斷，寫出求每個(gè)等邊三角形所用卡片總數(shù)sn的遞推公式．49162536…第11頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

為慶?！拔濉ひ弧眹?guó)際勞動(dòng)節(jié)，市政府決定在人民廣場(chǎng)上增設(shè)一排燈花，其設(shè)計(jì)由以下圖形逐步演變而成，其中圓圈代表燈花中的燈泡，n代表第n次演變過(guò)程，s代表第n次演變后的燈泡的個(gè)數(shù)。仔細(xì)觀察下列演變過(guò)程，當(dāng)n=6時(shí)，s=_____。94Sn=2×sn-1+2Sn=3×sn-1-2×sn-2第12頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

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

從表中可以看出車上人數(shù)最多是56人，所以車上至少要準(zhǔn)備56個(gè)座位。第13頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三練習(xí)1將一張長(zhǎng)方形的紙對(duì)折，可得到一條折痕，繼續(xù)對(duì)折，對(duì)折時(shí)每次折痕與上次的折痕保持平行，連續(xù)對(duì)折三次后，可得到７條折痕，那么對(duì)折n次，可得到幾條折痕？

第14頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三Fn=2*Fn-1+1vara,i,n:longint;beginread(n);

a:=1;fori:=2tondo

a:=2*a+1;writeln(a);end.第15頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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

第16頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三var{加入高精度運(yùn)算}a,b:array[1..100]ofinteger;i,j,n:integer;beginreadln(n);a[100]:=1;{n=1時(shí)}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.第17頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三練習(xí)2

如圖,第一次把三角形剪去一個(gè)角后,圖中最多有四個(gè)角,第二次再把新產(chǎn)生的角各剪一刀,…,如此下去,每一次都是把新產(chǎn)生的角各剪一刀,則第n次剪好后,圖中最多有多少個(gè)角?46101834…Fn=Fn-1+2n-1第18頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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.第19頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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.第20頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三練習(xí)3

下圖中把大正方形各邊平均分成了5份，此時(shí)有55個(gè)正方形。如果把正方形各邊平均分成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.第21頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三Var{加入高精度運(yùn)算}a:array[1..25]oflongint;i,j,k,x,n:longint;beginreadln(n);a[25]:=1;{n=1時(shí)}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.第22頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三練習(xí)4

如圖，由等圓組成的一組圖中，第1個(gè)圖由1個(gè)圓組成，第2個(gè)圖由7個(gè)圓組成，第3個(gè)圖由19個(gè)圓組成，……，按照這樣的規(guī)律排列下去，則第9個(gè)圖形由__________個(gè)圓組成。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.第23頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三var{加入高精度運(yùn)算}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.第24頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三練習(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è)，2023年5月2日，星期三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.第26頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三Hanoi雙塔問(wèn)題

給定A、B、C三根足夠長(zhǎng)的細(xì)柱，在A柱上放有2n個(gè)中間有孔的圓盤，共有n個(gè)不同的尺寸，每個(gè)尺寸都有兩個(gè)相同的圓盤，注意這兩個(gè)圓盤是不加區(qū)分的（下圖為n=3的情形）?，F(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è)，2023年5月2日，星期三

輸入文件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<=n<=200【提示】

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

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

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

第29頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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;{再在個(gè)位上加2}forj:=1to62doifa[j]>9thenbegin{處理進(jìn)位}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.第30頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

在上面的一些例題中，遞推過(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è)，2023年5月2日，星期三

意大利著名數(shù)學(xué)家斐波那契在研究兔子繁殖問(wèn)題時(shí)，發(fā)現(xiàn)有這樣一組數(shù)：1，1，2，3，5，8，13，…，其中從第三個(gè)數(shù)起，每一個(gè)數(shù)都等于它前面兩上數(shù)的和。現(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è)，2023年5月2日，星期三【問(wèn)題描述】

一只蜜蜂在上圖所示的數(shù)字蜂房上爬動(dòng),已知它只能從標(biāo)號(hào)小的蜂房爬到標(biāo)號(hào)大的相鄰蜂房,現(xiàn)在問(wèn)你：蜜蜂從蜂房M開始爬到蜂房N（M<N），有多少種爬行路線？【輸入格式】輸入M，N的值。(1<=M,N<=1000)【輸出格式】爬行有多少種路線?！据斎霕永縝ee.in114【輸出樣例】bee.out377第33頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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.第34頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三通過(guò)合理分步、恰當(dāng)分類找出遞推關(guān)系第35頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

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

89種

登樓梯第36頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三以某位置劃分求遞推式第37頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

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

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

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

有2×n的一個(gè)長(zhǎng)方形方格，用一個(gè)1×2的骨牌鋪滿方格。例如n=3時(shí)，為2×3方格。此時(shí)用一個(gè)1×2的骨牌鋪滿方格，共有如下3種鋪法：

試對(duì)給出的任意一個(gè)n（n>0），求出鋪法總數(shù)的遞推公式。F(1)=1F(2)=2F(n)=F(n-2)+F(n-1)(n>=3)第40頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

如果有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+2Ａn-2第41頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

有排成一行的ｎ個(gè)方格，用紅、黃、藍(lán)三色涂每個(gè)格子，每格涂一色，要求任何相鄰的格不同色，且首尾兩格也不同色。問(wèn)有多少種涂法？解：設(shè)共有ａn種涂法，易見(jià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種涂色法。綜上，可得ａn＝ａn-1＋２ａn-2（ｎ≥４）按前n-1格首尾關(guān)系討論第42頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三錯(cuò)位排列

五個(gè)人排成一列，重新站隊(duì)時(shí)，各人都不站在原來(lái)的位置上，那么不同的站隊(duì)方式共有()

（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ì)方式。由分步計(jì)數(shù)原理和分類計(jì)數(shù)原理，我們便得到了數(shù)列的遞推關(guān)系式： ，顯然，再由遞推關(guān)系有，第43頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

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

放回去時(shí)只能為：312或231這兩種問(wèn)題：求當(dāng)n=5時(shí)滿足以上條件的放法共有多少種？第44頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三染色問(wèn)題

用4種不同顏色涂四邊形的4個(gè)頂點(diǎn)，要求每點(diǎn)染一種顏色，相鄰的頂點(diǎn)染不同的顏色，則不同的染色方法有()（A）84種 （B）72種 （C）48種 （D）24種A第45頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三第46頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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是頂點(diǎ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)第47頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三如圖，一個(gè)地區(qū)分為5個(gè)行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有四種顏色可供選擇，則不同的著色方法共有

種。第48頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

圖中2、3、4、5四個(gè)區(qū)域圍成一個(gè)四邊形，因此可以把它們看成是一個(gè)四邊形的4個(gè)頂點(diǎn)，而區(qū)域1就是這個(gè)四邊形對(duì)角線的交點(diǎn)。第一步，先涂區(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è)，2023年5月2日，星期三

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

種。1204×30=120第50頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三傳球問(wèn)題

4個(gè)人進(jìn)行籃球訓(xùn)練，互相傳球接球，要求每個(gè)人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問(wèn)有多少種傳球方式？60第51頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三第52頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三分析:設(shè)第n次傳球后，球又回到甲手中的傳球方式有an種。可以想象前n-1次傳球，如果每一次傳球都任選其他三人中的一人進(jìn)行接球，則每次傳球都有3種可能，由乘法原理，共有3×3×……×3=3n-1

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

一類是第n-1次恰好傳到甲手中，這有an-1種傳法，它們不符合要求，因?yàn)檫@樣第n次無(wú)法再把球傳給甲；另一類是第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。這說(shuō)明經(jīng)過(guò)5次傳球后，球仍回到甲手中的傳球方法有60種。第53頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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.第54頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三var{加入高精度運(yùn)算}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.第55頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三凸多邊形劃分在一個(gè)凸多邊形中，通過(guò)若干條互不相交的對(duì)角線，把這個(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è)，2023年5月2日，星期三如圖所示，我們以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到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è)，2023年5月2日，星期三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.第58頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三求路徑總數(shù)下圖是某居民小區(qū)道路圖，小明每天由家（Ａ點(diǎn)）到學(xué)校（Ｂ點(diǎn)），他只沿道路向上或向右行走，那么他最多有（）天走不同線路？ＡＢ４９５１１１１１１１１１１１１２３４５６７８９３６10

15

21

28

36

454

10

2035

56

84

120

1655

15

3570

126

210

330495第59頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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.要想到達(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)輸入：59輸出：495第60頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三街道路徑

設(shè)有一個(gè)N＊M（1<=N<=50，1<=M<=50）的街道，規(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的路徑有兩條?，F(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)的路徑總數(shù)為a[i,j]，則a[i,j]=a[i-1,j]+a[i,j-1]。因此我們可以采用逐行遞推的方法來(lái)求出從起始頂點(diǎn)到達(dá)任意一個(gè)頂點(diǎn)的路徑總數(shù)。第61頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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第62頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

Var{加入高精度運(yùn)算}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.第63頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三過(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)是需要給出的（約定:C<>A，同時(shí)C<>B）?，F(xiàn)在要求你計(jì)算出卒從A點(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ù)）。樣例:

輸入6632

輸出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è)，2023年5月2日，星期三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.有些控制點(diǎn)有可能在邊上第65頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三const{加入高精度運(yùn)算}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;第66頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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.第67頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三傳球游戲【問(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í)，拿著球沒(méi)有傳出去的那個(gè)同學(xué)就是敗者，要給大家表演一個(gè)節(jié)目。聰明的小蠻提出了一個(gè)有趣的問(wèn)題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了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è)，2023年5月2日，星期三【輸入】

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

輸出文件ball.out共一行，有一個(gè)整數(shù)，表示符合題意的方法數(shù)?！据斎胼敵鰳永縝all.in3ball.out32【限制】40%的數(shù)據(jù)滿足：3<=n<=30，1<=m<=20100%的數(shù)據(jù)滿足：3<=n<=30，1<=m<=30第69頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三分析：設(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é)開始傳球，可確定初始條件：f(1,0)=1

可根據(jù)傳球次數(shù)進(jìn)行遞推，結(jié)果在f(1,m)中。第70頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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號(hào)同學(xué)時(shí)}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號(hào)同學(xué)時(shí)}end;write(f[1,m]);end.第71頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三傳球問(wèn)題

4個(gè)人進(jìn)行籃球訓(xùn)練，互相傳球接球，要求每個(gè)人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問(wèn)有多少種傳球方式？第72頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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.第73頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三整數(shù)劃分

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

=n1+n2+…+nk

且滿足1<=n1<=n2<=…<=nk<=N，叫做N的一個(gè)劃分。求不同的劃分的數(shù)量。當(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è)，2023年5月2日，星期三設(shè)表示把正整數(shù)a做分劃、其中最大的一份恰好是b的方案總數(shù)。設(shè)表示把正整數(shù)a做分劃、其中最大的一份不大于b的方案總數(shù)。顯然有：所以：當(dāng)i<j時(shí)，根據(jù)的含義，無(wú)意義。當(dāng)j=1時(shí)，對(duì)i做任意剖分、其中最大的一份不大于1的方案只有一種。即：i=1+1+1+…+1（共i個(gè)1）;所以：=14=1+1+1+1；

4=1+1+2；

4=2+2；

4=1+3；第75頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三根據(jù)以上分析可得到如下遞推公式：

=

=1{初始條件}

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

最后的g(n,n-1)即為所求。第76頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三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.第77頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三倒推法

我們把由已知初始值為Ｆ1，通過(guò)遞推關(guān)系式Ｆn=g(Fn-1)求出其最終結(jié)果Fn的遞推方式稱為順推法．同理，把已知最終結(jié)果為Fn，通過(guò)遞推關(guān)系式Ｆn-1=g(Fn)，求出其初始值Ｆ1的遞推方式稱之為倒推法。第78頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三

四個(gè)人做火柴游戲,每一局三個(gè)人贏,一個(gè)人輸,輸者要按贏者手中贏得火柴根數(shù)賠償,即贏者手中有多少根火柴,輸者就賠他多少?4次之后,每人恰好輸過(guò)一次而且手中都恰好有16根?求四人原有火柴數(shù)?把第一局輸?shù)娜擞洖椋?，把第二局輸?shù)娜擞洖椋?，把第三局輸?shù)娜擞洖椋?，把第四局輸?shù)娜擞洖椋?，用倒退法可知：ＡＢＣＤ４１６１６１６１６３８８８４０２４４３６２０１２３４１８１０開始３３１７９５第79頁(yè)，講稿共86頁(yè)，2023年5月2日，星期三騎士游歷

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