【正文】 ,k1]+f[1,k1]。 {當球在n號同學時} end。 write(f[1,m])。 end.,第七十一頁，共八十七頁。,傳球問題,4個人進行籃球訓練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方式？,第七十二頁，共八十七頁。,Var n,m,i,j,k,l,g:longint。 a:array[030,130,1100] of longint。 begin read(n,m)。 a[0,1,1]:=1。 for i:=1 to m do begin for j:=1 to n do for k:=1 to n do if jk then begin g:=0。 for l:=1 to 100 do begin g:=a[i,j,l]+a[i1,k,l]+g。 a[i,j,l]:=g mod 10 。 g:=g div 10。 end。 end。 end。 l:=100。 while a[m,1,l]=0 do l:=l1。 for i:=l downto 1 do write(a[m,1,i])。 end.,第七十三頁，共八十七頁。,整數(shù)劃分,把一個正整數(shù)N劃分成一些正整數(shù)的和，例如： N =n1+n2+…+nk 且滿足1=n1=n2=…=nk = N ， 叫做N的一個劃分。求不同的劃分的數(shù)量。 當n=4時，劃分數(shù)為4。 4=1+1+1+1； 4=1+1+2； 4=1+3； 4=2+2；,第七十四頁，共八十七頁。,設(shè) 表示把正整數(shù)a做分劃、其中最大的一份恰好是b的方案總數(shù)。 設(shè) 表示把正整數(shù)a做分劃、其中最大的一份不大于b的方案總數(shù)。 顯然有： 所以： 當ij時，根據(jù) 的含義， 無意義。 當j=1時，對i做任意剖分、其中最大的一份不大于1的方案只有一種。即： i=1+1+1+…+1（共i個1）。所以： =1,,4=1+1+1+1； 4=1+1+2； 4=2+2； 4=1+3；,第七十五頁，共八十七頁。,根據(jù)以上分析可得到如下遞推公式： = =1{初始條件} 我們可以按照i、j遞增的順序來計算 的值，這樣在計算 的時候， 和 都已經(jīng)得到，故我們只用進行一次簡單的加法運算即可. 最后的g(n,n1)即為所求。,,第七十六頁，共八十七頁。,var g:array[0100,0100] of longint。 n,i,j:integer。 begin readln(n)。 fillchar(g,sizeof(g),0)。 for j:=0 to n do g[j,1]:=1。{初始條件} for i:=0 to n do for j:=2 to n do if i=j then g[i,j]:=g[ij,j]+g[i,j1] else g[i,j]:=g[i,j1]。 writeln( g[n,n1] )。 end.,第七十七頁，共八十七頁。,倒推法,我們把由已知初始值為Ｆ1，通過遞推關(guān)系式Ｆn=g(Fn1)求出其最終結(jié)果Fn的遞推方式稱為順推法．同理，把已知最終結(jié)果為Fn，通過遞推關(guān)系式Ｆn1=g(Fn)，求出其初始值Ｆ1的遞推方式稱之為倒推法。,第七十八頁，共八十七頁。,四個人做火柴游戲,每一局三個人贏,一個人輸,輸者要按贏者手中贏得火柴根數(shù)賠償,即贏者手中有多少根火柴,輸者就賠他多少?4次之后,每人恰好輸過一次而且手中都恰好有16根?求四人原有火柴數(shù)?,把第一局輸?shù)娜擞洖椋粒训诙州數(shù)娜擞洖椋?，把第三局輸?shù)娜擞洖椋?，把第四局輸?shù)娜擞洖椋?，用倒退法可知?第七十九頁，共八十七頁。,騎士游歷,設(shè)有一個n*m的棋盤(2(2,3)(4,4)。若不存 在路徑,則輸出‘no’。,第八十頁，共八十七頁。,算法分析：我們先將棋盤的橫坐標規(guī)定為i，縱坐標規(guī)定為j，對于一個nm的棋盤，i的值從1到n，j的值從1到m。棋盤上的任意點都可以用坐標(i,j)表示。對于馬的移動方法，我們用K來表示四種移動方向(1,2,3,4)；而每種移動方法用偏移值來表示，并將這些偏移值分別保存在數(shù)組dx和dy中，如下表 ：,第八十一頁，共八十七頁。,根據(jù)馬走的規(guī)則，馬可以由（idx[k],jdy[k]）走到(i,j)。只要馬能從（1，1）走到（idx[k],jdy[k]），就一定能走到（i,j）,馬走的坐標必須保證在棋盤上。我們以（n,m）為起點向左遞推，當遞推到（idx[k],jdy[k]）的位置是（1，1）時，就找到了一條從（1，1）到（n,m）的路徑。 我們用一個二維數(shù)組a表示棋盤，采用倒推法，從終點(n,m)往左遞推， 設(shè)初始值a[n,m]為（1，1），如果從(i,j)一步能走到(n,m)，就將(n,m)存放在a[i,j]中。如下表，a[3,2]和a[2,3]的值是（4，4），表示從這兩個點都可以到達坐標（4,4）。從（1,1）可到達（2，3）、（3，2）兩個點，所以a[1,1]存放兩個點中的任意一個即可。遞推結(jié)束以后，如果a[1,1]值為(0,0)說明不存在路徑，否則a[1,1]值就是馬走下一步的坐標，以此遞推輸出路徑。,第八十二頁，共八十七頁。,const dx:array[14]of integer=(2,2,1,1)。 dy:array[14]of integer=(1,1,2,2)。 type map=record x,y:integer。 end。 var i,j,n,m,k:integer。 a:array[050,050] of map。 begin read(n,m)。 fillchar(a,sizeof(a),0)。 a[n,m].x:=1 。 a[n,m].y:=1。{標記為終點} for i:=n downto 2 do {倒推} for j:=m downto 1 do if a[i,j].x0 then for k:=1 to 4 do begin a[idx[k],jdy[k]].x:=i。 a[idx[k],jdy[k]].y:=j。 end。,if a[1,1].x=0 then writeln(39。no39。) else begin{存在路徑} i:=1。j:=1。 write(39。(39。,i,39。,39。,j,39。)39。)。 while a[i,j].x1 do begin k:=i。 i:=a[i,j].x 。 j:=a[k,j].y。 write(39。(39。,i,39。,39。,j,39。)39。)。 end。 end。 end.,第八十三頁，共八十七頁。,乘火車,火車從始發(fā)站（稱為第1站）開出，在始發(fā)站上車的人數(shù)為a，然后到達第2站，在第2站有人上、下車，但上、下車的人數(shù)相同，因此在第2站開出時（即在到達第3站之前）車上的人數(shù)保持為a人。從第3站起（包括第3站）上、下車的人數(shù)有一定規(guī)律：上車的人數(shù)都是前兩站上車人數(shù)之和，而下車人數(shù)等于上一站上車人數(shù)，一直到終點站的前一站（第n1站），都滿足此規(guī)律?，F(xiàn)給出的條件是：共有n個車站，始發(fā)站上車的人數(shù)為a，最后一站下車的人數(shù)是m（全部下車）。試問第x站開出時車上的人數(shù)是多少？ 輸入文件chc.in：一行四個整數(shù)a，n，m和x（中間用空格隔開） 輸出文件chc.out：一行一個整數(shù)（從x站開出時車上的人數(shù)） 樣例 : chc.in 4 6 32 4 chc.out 18,第八十四頁，共八十七頁。,分析： 設(shè)up[i]為i站的上車人數(shù)、down[i]為i站的下車人數(shù)、p[i]為i站開出時車上的人數(shù)（1≤i≤n）。初始時up[1]=p[1]=a，down[1]=0。 ①依次枚舉第2站的上車人數(shù)為1，2，…… 設(shè)第2站的上車人數(shù)為k up[2]=down[2]=k ，p[2]=p[1]+up[2]down[2]=a ②按照下式遞推第3站…第n1站的車上人數(shù) up[i]=up[i1]+up[i2] down[i]=up[i1] p[i]=p[i1]+up[i]down[i]=p[i1]+up[i2] (3≤i≤n1) ③計算從x站開出時車上的人數(shù) 若p[n1]=m，則輸出p[x]；否則k←k+1，返回①…，直至p[n1]m為止。因為p相對k是遞增的，因此在當前p[n1]m的情況下，無論k值怎樣增加也不會使得p[n1]=m的。,第八十五頁，共八十七頁。,const maxn=100。 var a，n，m，x ，k，i：integer； p，down，up：array[1maxn] of integer； begin readln(a，n，m，x)； fillchar(p，sizeof(p)，0)； up[1]:=a；down[1] :=0；p[1] :=a； k:=1。 repeat up[2]:=k；down[2]:=k；p[2]:=p[1]；{枚舉第2站的上車人數(shù)、下車人數(shù)和車上人數(shù)} for i:=3 to n1 do begin {遞推第3站…第n1站的車上人數(shù)} up[i] :=up[i1]+up[i2]； down[i] :=up[i1]； p[i] :=p[i1]+up[i2]； end； if p[n1]=m then {若n站下車的人數(shù)為m，則輸出從x站開出時車上的人數(shù)，并退出} begin writeln(p[x])； exit； end； k:=k+1；{第2站上車人數(shù)增加1} until p[n1]m；{直至無法滿足此規(guī)律為止} end.,第八十六頁，共八十七頁。,內(nèi)容總結(jié),遞推法。end.。在平面內(nèi)畫五條直線和一個圓，最多能把平面分成多少部分?，F(xiàn)要將這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。若按此規(guī)律繼續(xù)作矩形，則序號為⑩的矩形周長是＿＿＿。第一步：第一個人不站在原來的第一個位置，有n1種站法?，F(xiàn)將n本書全部取下然后再放回去，當放回去時要求每本書都不能放在原來的位置上。把一個正整數(shù)N劃分成一些正整數(shù)的和，例如：。4次之后,每人恰好輸過一次而且手中都恰好有16根,第八十七頁，共八十七頁