【正文】 1221312412 根據(jù)馬走的規(guī)則，馬可以由（idx[k],jdy[k]）走到(i,j)。begin read(n,m)。no39。)39。,39。我們可以按以下四個(gè)步驟去分析：（1）細(xì)心的觀察；（2）豐富的聯(lián)想；（3）不斷地嘗試；（4）總結(jié)出遞推關(guān)系式。若設(shè)0個(gè)數(shù)通過(guò)棧后的排列總數(shù)為：f(0)=1；上式可變?yōu)椋篺(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0)。 a[0]:=1。分治法應(yīng)用例 比賽安排(noip1996)設(shè)有2^n(n=6)個(gè)球隊(duì)進(jìn)行單循環(huán)比賽,計(jì)劃在2^n1天內(nèi)完成,每個(gè)隊(duì)每天進(jìn)行一場(chǎng)比賽。 34變量h表示當(dāng)前方陣的大小,也就是要生成的下一個(gè)方陣的一半。 repeat for i:=1 to h do for j:=1 to h do begin a[i,j+h]:=a[i,j]+h。 end。⑶f(x1)*f(x2)0，則確定根x不在區(qū)間[x1，x2]內(nèi)，設(shè)定[x2，x2+1]為下一個(gè)搜索區(qū)間；若確定根x在區(qū)間[x1，x2]內(nèi)，采用二分法，將區(qū)間[x1，x2]分成左右兩個(gè)子區(qū)間：左子區(qū)間[x1，x]和右子區(qū)間[x，x2]（其中x=（x1+x2）/2）。begin read(a,b,c,d)。{while} write(x1:0:2,39。每堆上有若干張，但紙牌總數(shù)必為 N 的倍數(shù)。[輸入輸出樣例]：　4　9 8 17 6屏慕顯示：3算法分析：設(shè)a[i]為第i堆紙牌的張數(shù)（0=i=n），v為均分后每堆紙牌的張數(shù)，s為最小移到次數(shù)。 f:text。 inc(v,a[i])。我們看一個(gè)找?guī)诺睦?如果一個(gè)貨幣系統(tǒng)有3種幣值,面值分別為一角、五分和一分，求最小找?guī)艛?shù)時(shí)，可以用貪心法求解；如果將這三種幣值改為一角一分、五分和一分，就不能使用貪心法求解。源程序：var s:array[1..20] of string。 s[i]:=s[j]。為了減少存儲(chǔ)空間，在深度優(yōu)先搜索中，用標(biāo)志的方法記錄訪問(wèn)過(guò)的狀態(tài)，這種處理方法使得深度優(yōu)先搜索法與回溯法沒(méi)什么區(qū)別了。搜索算法應(yīng)用例1騎士游歷:設(shè)有一個(gè)n*m的棋盤，在棋盤上任一點(diǎn)有一個(gè)中國(guó)象棋馬,馬走的規(guī)則為: 。 end。(39。,a[j].x,39。{搜索下一步} a[i].x:=0。 writeln(39。從n 個(gè)整數(shù)中任選 k 個(gè)整數(shù)相加，可分別得到一系列的和。為了避免不必要的搜索，程序?qū)λ阉鬟^(guò)程進(jìn)行了優(yōu)化，限制搜索范圍，在搜索過(guò)程dfs(i,m)中，參數(shù)m為第i個(gè)數(shù)的上限，下限為nk+i。 if sqr(i)s then inc(ans){若為素?cái)?shù)則總數(shù)加1}end。 ans:=0。廣度優(yōu)先搜索基本算法：program bfs。{隊(duì)列為空}使用廣度優(yōu)先搜索時(shí)，離根結(jié)點(diǎn)最近的結(jié)點(diǎn)先擴(kuò)展，所以廣度優(yōu)先搜索法比較適合求步數(shù)最少的解，由于深度優(yōu)先使用了標(biāo)志法，使得存儲(chǔ)空間大大減少，而廣度優(yōu)先要保留所有搜索過(guò)的節(jié)點(diǎn)，隨著搜索程度的加深，所需的存儲(chǔ)空間成指數(shù)增加。[輸入]:鍵盤輸人文件名。源程序：const mid=12000。 d,fil:string。i:=0。 inc(i)。 end。 {擴(kuò)展產(chǎn)生新節(jié)點(diǎn)}procedure expand(be,st:integer)。 new(a[cl[st]])。{for}end。 a[cl[st]]^.x:=0。writeln(39。動(dòng)態(tài)規(guī)劃法的定義：在求解問(wèn)題中，對(duì)于每一步?jīng)Q策，列出各種可能的局部解，再依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解，在每一步都經(jīng)過(guò)篩選，以每一步都是最優(yōu)解來(lái)保證全局是最優(yōu)解，這種求解方法稱為動(dòng)態(tài)規(guī)劃法。確定狀態(tài)：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處的各種客觀情況用不同的狀態(tài)表示出來(lái)?！据斎胛募浚? = N = 100），表示同學(xué)的總數(shù)。這樣就得到狀態(tài)轉(zhuǎn)移方程：f1(i)=max{f1(j)+1} (ji,TjTi)邊界條件：f1(1)=1。 reset(input)。 for i:=2 to n do for j:=1 to i1 do begin if (t[i]t[j])and(f1[j]=f1[i]) then f1[i]:=f1[j]+1。 writeln(nmax+1)。)。{for} close(input)。39。我們先考慮如何求最大上升子序列的長(zhǎng)度，設(shè)f1(i)為前i個(gè)同學(xué)的最大上升子序列長(zhǎng)度。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1, 2, …, K，他們的身高分別為T1, T2, …, TK，則他們的身高滿足T1 T2 … Ti , Ti Ti+1 … TK (1 = i = K)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線。 決策：從某階段的一個(gè)狀態(tài)演變到下一個(gè)階段某狀態(tài)的選擇。BEGIN init。 new(a[cl[st]])。{if} end。 for i:=1 to mark do begin lx:=length(x[i,st])。 bool(be,st)。begin for i:=midbe+1 to cl[1st] do if a[cl[st]]^.s=a[i]^.s then begin writeln(a[cl[st]]^.x+a[i]^.x)。 39。 assign(f,fil)。 a:array [1..max]of ^node。采用雙向搜索，存儲(chǔ)的結(jié)點(diǎn)數(shù)還有可能超限，我們?cè)谇跋蛩阉麝?duì)列中存儲(chǔ)5步內(nèi)變換的結(jié)點(diǎn)，在后向搜索隊(duì)列中，由于第5步產(chǎn)生的結(jié)點(diǎn)只是用來(lái)與前向隊(duì)列中的結(jié)點(diǎn)比較，所以可以不存儲(chǔ)在隊(duì)列中，后向搜索隊(duì)列只需存儲(chǔ)4步內(nèi)的結(jié)點(diǎn)，這樣就解決了存儲(chǔ)空間問(wèn)題。xyz39。 end{for}。在下一篇中將繼續(xù)介紹另一種搜索方法——廣度優(yōu)先搜索法。begin readln(n,k)。begin i:=2。求解此題時(shí)，先用深度優(yōu)先搜索法生成k個(gè)數(shù)的組合，再判斷k個(gè)數(shù)的和是否為素?cái)?shù)，若為素?cái)?shù)則總數(shù)加1。我們?cè)倏纯戳硪粋€(gè)例子。 readln(n,m)。{輸出結(jié)果并退出程序} end。 for j:=2 to i do write(39。 a[i].y:=a[i1].y+dy[j]。 dy:array[1..4]of integer=(1,1,2,2)。endfor。算法在信息學(xué)奧賽中的應(yīng)用（搜索法一） 在這里介紹兩種基本的搜索算法：深度優(yōu)先搜索和廣度優(yōu)先搜索法，以樹的搜索為例，深度優(yōu)先搜索法是優(yōu)先擴(kuò)展尚未擴(kuò)展的且具有最大深度的結(jié)點(diǎn)；廣度優(yōu)先搜索法是在擴(kuò)展完第K層的結(jié)點(diǎn)以后才擴(kuò)展K+1層的結(jié)點(diǎn)。 end。按這種貪心標(biāo)準(zhǔn)，我們很容易找到反例：12，121 應(yīng)該組成12121而非12112,那么是不是相互包含的時(shí)候就從小到大呢？也不一定，如：12，123 就是12312而非12112,這樣情況就有很多種了。{then} writeln(s)。v:=0。v:longint。文件格式：N（N 堆紙牌，1 = N = 100）　　A1 A2 … An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000）[輸 出]：輸出至屏幕。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問(wèn)題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問(wèn)題自身的特性決定了該題運(yùn)用貪心算法可以得到最優(yōu)解。 if f(x1)*f(xx)=0 then x2:=xx else x1:=xx。begin f:=((a*x+b)*x+c)*x+d。由題意知（i,i+1）中若有根，則只有一個(gè)根，我們枚舉根的值域中的每一個(gè)整數(shù)x(100≤x≤100),設(shè)定搜索區(qū)間[x1，x2]，其中x1=x，x2=x+1。 for i:=1 to m do begin for j:=1 to m do write(a[i,j]:4)。h:=1。因此我們也可以把這個(gè)方陣看作是由M=1的方陣所成生的，同理可得M=4的方陣：1234214334124321同理可由M=4方陣生成M=8的方陣：1234567821436587341278564321876556781234658721437856341287654321這樣就構(gòu)成了整個(gè)比賽的安排表。 3 4比賽求出子問(wèn)題的解，就可得到原問(wèn)題的解。begin readln(n)。（4） 若“4”第四個(gè)輸出，與情況（1）相同，總數(shù)為f(3)。end.對(duì)于任務(wù)二，也可以使用遞推法，用數(shù)組A[i,j]存放從起點(diǎn)(x1,y1)到（i,j）的路徑總數(shù)，按同樣的方法從左向右遞推，一直遞推到（x2,y2），a[x2,y2]即為所求的解。(39。,39。 end。var i,j,n,m,k:integer。遞推結(jié)束以后，如果a[1,1]值為(0,0)說(shuō)明不存在路徑，否則a[1,1]值就是馬走下一步的坐標(biāo)，以此遞推輸出路徑。例如:(N=10,M=10),(1,5)(起點(diǎn)),(3,5)(終點(diǎn))輸出:2(即由(1,5)到(3,5)共有2條路徑)輸入格式:n,m,x1,y1,x2,y2(分別表示n,m,起點(diǎn)坐標(biāo),終點(diǎn)坐標(biāo))輸出格式:路徑數(shù)目(若不存在從起點(diǎn)到終點(diǎn)的路徑,輸出0)算法分析：為了研究的方便，我們先將棋盤的橫坐標(biāo)規(guī)定為i，縱坐標(biāo)規(guī)定為j，對(duì)于一個(gè)nm的棋盤，i的值從1到n，j的值從1到m。我們?cè)诰帉懗绦驎r(shí)是否使用遞歸算法，關(guān)鍵是看問(wèn)題是否適合用遞歸算法來(lái)求解。End。begin readln(n,k)。 　make(z,h)。 begin m:=length(h)。[樣例] 輸入：BADC BDCA遞歸過(guò)程：procedure Hanoi(N,A,B,C:integer。 writeln(t)。a[i]:=a[i1]。 i:=1。 sum:=sum+a[i+1]1。 sum:=n1。輸入：n，k (6n=200，2=k=6)輸出：一個(gè)整數(shù)，即不同的分法。 until a[1]=r1。 repeat if a[i]ri then {符合條件 } if i=r then {輸出}beginfor j:=1 to r do write(a[j]:3)。 i:=i+1。否則返回到上一個(gè)數(shù)，改變上一個(gè)數(shù)的值再判斷是否符合要求，如果符合要求，則繼續(xù)添加下一個(gè)數(shù)，否則返回到上一個(gè)數(shù)，改變上一個(gè)數(shù)的值……按此規(guī)則不斷循環(huán)搜索，直到找出r個(gè)數(shù)的組合，這種求解方法就是回溯法。信息學(xué)奧賽中的基本算法(回溯法)如果上期的“百錢買百雞”中雞的種類數(shù)是變化的，用枚舉法就無(wú)能為力了，這里介紹另一種算法——回溯法。begin read(a,b,c,d)。我們換一個(gè)角度來(lái)思考問(wèn)題，設(shè)f(x)=ax3+bx2+cx+d，若x為方程的根，則根據(jù)提示可知，必有f()*(x+)0，如果我們以此為枚舉判定條件，問(wèn)題就逆刃而解。 if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,39。提示：記方程f(x)=0，若存在2個(gè)數(shù)x1和x2，且x1x2，f(x1)*(x2)0，則在(x1，x2)之間一定有一個(gè)根。 39。 for c:=39。 s,st:string。,z)。 {驗(yàn)證可能的解，并輸出符合題目要求的解}end.上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉二種雞（x,y），第三種雞就可以根據(jù)約束條件求得（z=100xy），這樣就縮小了枚舉范圍，請(qǐng)看下面的程序：var x,y,z:integer。下面是解這個(gè)百雞問(wèn)題的程序var x,y,z:integer。如果僅僅學(xué)會(huì)一種程序設(shè)計(jì)語(yǔ)言，而沒(méi)學(xué)過(guò)算法的選手在比賽中是不會(huì)取得好的成績(jī)的，選手水平的高低在于能否設(shè)計(jì)出好的算法。begin 　readln(n)?！? while sum mod 10=0 do　 begin　 sum:=sum div 10。例：求N！所產(chǎn)生的數(shù)后面有多少個(gè)0（中間的0不計(jì)）。在算法時(shí)間復(fù)雜度的表示中，還有可能出現(xiàn)的有：對(duì)數(shù)階O(log n)，指數(shù)階O(2n)等。 輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以描述運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定義了初始條件。我們?cè)诰帉懗绦虻倪^(guò)程就是在實(shí)施某種算法，因此程序設(shè)計(jì)的實(shí)質(zhì)就是用計(jì)算機(jī)語(yǔ)言構(gòu)造解決問(wèn)題的算法。它們是同輸入有著某種特定關(guān)系的量。由于當(dāng)今計(jì)算機(jī)硬件技術(shù)發(fā)展很快，程序所能支配的自由空間一般比較充分，所以空間復(fù)雜度就不如時(shí)間復(fù)雜度那么重要了，有許多問(wèn)題人們主要是研究其算法的時(shí)間復(fù)雜度，而很少討論它的空間耗費(fèi)。（pascal程序如下）var　i,t,n,sum:longint?！? sum:=sum mod 1000?！? inc(t,n)。能使命題成立者，即為問(wèn)題的解。,x,39。x=39。從上面的對(duì)比可以看出，對(duì)于枚舉算法，