【文章內(nèi)容簡(jiǎn)介】 4種,解：首先我們把人數(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è)位置，有n1種站法。 第二步：假設(shè)第一個(gè)人站在第2個(gè)位置，則第二個(gè)人的站法又可以分為兩類：第一類，第二個(gè)人恰好站在第一個(gè)位置，則余下的 n2個(gè)人有An2種站隊(duì)方式；第二類，第二個(gè)人不站在第一個(gè)位置，則就是第二個(gè)人不站在第一個(gè)位置，第三個(gè)人不站在第三個(gè)位置，第四個(gè)人不站在第四個(gè)位置，……，第n個(gè)人不站在第n個(gè)位置，所以有An1種站隊(duì)方式。 由分步計(jì)數(shù)原理和分類計(jì)數(shù)原理，我們便得到了數(shù)列 的遞推關(guān)系式： ，顯然 ，再由遞推關(guān)系有，,第四十三頁(yè)，共八十七頁(yè)。,在書架上放有編號(hào)為1 ，2 ，…，n的n本書。現(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í)滿足以上條件的放法共有多少種？,第四十四頁(yè)，共八十七頁(yè)。,染色問(wèn)題,用4種不同顏色涂四邊形的4個(gè)頂點(diǎn)，要求每點(diǎn)染一種顏色，相鄰的頂點(diǎn)染不同的顏色，則不同的染色方法有( ) （A）84種 （B）72種 （C）48種 （D）24種,A,第四十五頁(yè)，共八十七頁(yè)。,第四十六頁(yè)，共八十七頁(yè)。,Var i,j,k,m,n:longint。 a:array[110] 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ù)} a[3]:=jc(m) div jc(m3)。{初值 } for i:= 4 to n do begin j:=1。 for k:= 1 to i1 do j:=j*(m1)。 { } a[i]:=m*ja[i1] 。 {遞推公式} end。 writeln(a[n])。 end.,a[3]:=m*(m1)*(m2),第四十七頁(yè)，共八十七頁(yè)。,如圖，一個(gè)地區(qū)分為5個(gè)行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有四種顏色可供選擇，則不同的著色方法共有 種。,第四十八頁(yè)，共八十七頁(yè)。,圖中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ù)原理，得出共有 種涂法。,,第四十九頁(yè)，共八十七頁(yè)。,某城市在中心廣場(chǎng)建造一個(gè)花圃，花圃分成6個(gè)部分(如圖)，現(xiàn)要栽種4種不同顏色的花，每部分栽種一種且相鄰部分不能栽種同樣顏色的花，不同的栽種方法共有 種。,120,430=120,第五十頁(yè)，共八十七頁(yè)。,傳球問(wèn)題,4個(gè)人進(jìn)行籃球訓(xùn)練，互相傳球接球，要求每個(gè)人接球后馬上傳給別人，開(kāi)始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問(wèn)有多少種傳球方式？,60,第五十一頁(yè)，共八十七頁(yè)。,第五十二頁(yè)，共八十七頁(yè)。,分析 :設(shè)第n次傳球后，球又回到甲手中的傳球方式有an種。可以想象前n1次傳球，如果每一次傳球都任選其他三人中的一人進(jìn)行接球，則每次傳球都有3種可能，由乘法原理，共有 33……3=3 n1 種傳球方法。這些傳球方式可以分為兩類: 一類是第n1次恰好傳到甲手中，這有an1種傳法，它們不符合要求，因?yàn)檫@樣第n次無(wú)法再把球傳給甲； 另一類是第n1次傳球，球不在甲手中，第n次持球人再將球傳給甲，有an種傳法。 根據(jù)加法原理，有an1+an=3 n1 。 由于甲是發(fā)球者，一次傳球后球又回到甲手中的傳球方式是不存在的，所以a1=0。 利用遞推關(guān)系可以得到 a2=30=3， a3=333=6， a4=3336=21， a5=333321=60。 這說(shuō)明經(jīng)過(guò)5次傳球后，球仍回到甲手中的傳球方法有60種。,第五十三頁(yè)，共八十七頁(yè)。,var a:array[1100] of longint。 n,m,i,j:longint。 begin readln(n,m)。 a[1]:=0。 j:=1。 for i:= 2 to m do begin j:=j*(n1)。 {先求出(n1)i1} a[i]:=ja[i1]。 end。 writeln(a[m])。 end.,第五十四頁(yè)，共八十七頁(yè)。,var {加入高精度運(yùn)算} a:array[1100,1100] of integer。 s:array[1100] of integer。 i,j,t,k,n,m:longint。 begin readln(n,m)。 a[1,100]:=0 。 s[100]:=1。 for i:= 2 to m do begin for j:= 100 downto 1 do s[j]:=s[j]*(n1)。 for j:= 100 downto 1 do if s[j]9 then begin s[j1]:=s[j1]+s[j] div 10。 s[j]:= s[j] mod 10。 end。,for j:= 100 downto 1 do a[i,j]:=s[j]a[i1,j]。 for j:= 100 downto 1 do if a[i,j]0 then begin a[i,j1]:=a[i,j1]1。 a[i,j]:=a[i,j]+10。 end。 end。 j:=1。 while a[m,j]=0 do j:=j+1。 for i:= j to 100 do write(a[m,i])。 end.,第五十五頁(yè)，共八十七頁(yè)。,凸多邊形劃分,在一個(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ù)。,第五十六頁(yè)，共八十七頁(yè)。,如圖所示，我們以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)成的凸nk+1邊形，根據(jù)乘法原理，選擇pk這個(gè)頂點(diǎn)的分解方案為 種。而k可以選2到n1，所以根據(jù)加法原理，得出總的方案數(shù)為 注意，就這個(gè)遞推關(guān)系而言，臨界值應(yīng)為C2=1，而不是C3=1，否則遞推關(guān)系就得不到正確解，這與原問(wèn)題的實(shí)際情況可能不符（即兩邊形），其實(shí)這只是理解上的差異．,第五十七頁(yè)，共八十七頁(yè)。,const max=21。 var c:array[2max] of longint。 n,i,k:integer。 total:longint。 begin readln(n)。 c[2]:=1。 for i:=3 to n do begin c[i]:=0。 for k:=2 to i1 do c[i]:=c[i]+c[k]*c[ik+1]。 end。 writeln(c[n])。 end.,第五十八頁(yè)，共八十七頁(yè)。,求路徑總數(shù),下圖是某居民小區(qū)道路圖，小明每天由家（Ａ點(diǎn)）到學(xué)校（Ｂ點(diǎn)），他只沿道路向上或向右行走，那么他最多有（ ）天走不同線路？,Ａ,Ｂ,４９５,１ １ １ １,１ １ １ １ １ １ １ １,２ ３ ４ ５ ６ ７ ８ ９,３ ６ 10 15 21 28 36 45,4 10 20 35 56 84 120 165,5 15 35 70 126 210 330 495,第五十九頁(yè)，共八十七頁(yè)。,var i,j,n,m:integer。 a:array[120,120] of longint。 begin read(n,m)。 fillchar(a,sizeof(a),0)。 for i:=1 to n do a[I,1]:=1。 for j:=1 to m do a[1,j]:=1。 for i:=2 to n do for j:=2 to m do a[I,j]:=a[I,j1]+a[i1,j]。 writeln(a[n,m])。 end.,要想到達(dá)坐標(biāo)為（i,j）的頂點(diǎn)的話，必定要經(jīng)過(guò)坐標(biāo)為（i1,j）的頂點(diǎn)或坐標(biāo)為（i,j1）的頂點(diǎn)，設(shè)a(I,j)表示從點(diǎn)A到頂點(diǎn)(I,j)的路徑總條數(shù)，則a(I,j)=a(I,j1)+a(i1,j),輸入：5 9 輸出：495,第六十頁(yè)，共八十七頁(yè)。,街道路徑,設(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的路徑有兩條。 現(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)為（i1,j）的頂點(diǎn)或坐標(biāo)為（i,j1）的頂點(diǎn)，假設(shè)從起始頂點(diǎn)到達(dá)坐標(biāo)為（i,j）的頂點(diǎn)的路徑總數(shù)為a[i,j]，則a[i,j]= a[i1,j] +a[i,j1]。因此我們可以采用逐行遞推的方法來(lái)求出從起始頂點(diǎn)到達(dá)任意一個(gè)頂點(diǎn)的路徑總數(shù)。,第六十一頁(yè)，共八十七頁(yè)。,