欧美精品一二区,性欧美一级,国产免费一区成人漫画,草久久久久,欧美性猛交ⅹxxx乱大交免费,欧美精品另类,香蕉视频免费播放

2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法

上傳人:xt****7 文檔編號:105037956 上傳時間:2022-06-11 格式:DOC 頁數(shù):4 大?。?2.02KB
收藏 版權(quán)申訴 舉報 下載
2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法_第1頁
第1頁 / 共4頁
2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法_第2頁
第2頁 / 共4頁
2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法_第3頁
第3頁 / 共4頁

下載文檔到電腦,查找使用更方便

9.9 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法》由會員分享,可在線閱讀,更多相關(guān)《2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法(4頁珍藏版)》請在裝配圖網(wǎng)上搜索。

1、2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法 所謂遞推,是指從已知的初始條件出發(fā),依據(jù)某種遞推關(guān)系,逐次推出所要求的各中間結(jié)果及最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定,或是通過對問題的分析與化簡后確定。 可用遞推算法求解的題目一般有以下二個特點: (1) 問題可以劃分成多個狀態(tài); (2) 除初始狀態(tài)外,其它各個狀態(tài)都可以用固定的遞推關(guān)系式來表示。 在我們實際解題中,題目不會直接給出遞推關(guān)系式,而是需要通過分析各種狀態(tài),找出遞推關(guān)系式。 遞推法應(yīng)用 例1騎士游歷:(noip1997tg) 設(shè)有一個n*m的棋盤(2<=n<=50,2<=m<=50),如下圖,在

2、棋盤上任一點有一個中國象棋馬, 馬走的規(guī)則為:1.馬走日字 2.馬只能向右走,即如下圖所示: 任務(wù)1:當(dāng)N,M 輸入之后,找出一條從左下角到右上角的路徑。 例如:輸入 N=4,M=4 輸出:路徑的格式:(1,1)->(2,3)->(4,4) 若不存在路徑,則輸出"no" 任務(wù)2:當(dāng)N,M 給出之后,同時給出馬起始的位置和終點的位置,試找出從起點到終點的所有路徑的數(shù)目。 例如:(N=10,M=10),(1,5)(起點),(3,5)(終點) 輸出:2(即由(1,5)到(3,5)共有2條路徑) 輸入格式:n,m,x1,y1,x2,y2(分別表示n,m,起

3、點坐標(biāo),終點坐標(biāo)) 輸出格式:路徑數(shù)目(若不存在從起點到終點的路徑,輸出0) 算法分析:為了研究的方便,我們先將棋盤的橫坐標(biāo)規(guī)定為i,縱坐標(biāo)規(guī)定為j,對于一個n×m的棋盤,i的值從1到n,j的值從1到m。棋盤上的任意點都可以用坐標(biāo)(i,j)表示。對于馬的移動方法,我們用K來表示四種移動方向(1,2,3,4);而每種移動方法用偏移值來表示,并將這些偏移值分別保存在數(shù)組dx和dy中,如下表 K Dx[k] Dy[k] 1 2 1 2 2 -1 3 1 2 4 1 -2 根據(jù)馬走的規(guī)則,馬可以由(i-dx[k],j-dy[k])走到(i,j)。只要馬能從(1

4、,1)走到(i-dx[k],j-dy[k]),就一定能走到(i,j),馬走的坐標(biāo)必須保證在棋盤上。我們以(n,m)為起點向左遞推,當(dāng)遞推到(i-dx[k],j-dy[k])的位置是(1,1)時,就找到了一條從(1,1)到(n,m)的路徑。 我們用一個二維數(shù)組a表示棋盤,對于任務(wù)一,使用倒推法,從終點(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),表示從這兩個點都可以到達坐標(biāo)(4,4)。從(1,1)可到達(2,3)、(3,2)兩個點,所以a[1,1]存放兩個

5、點中的任意一個即可。遞推結(jié)束以后,如果a[1,1]值為(0,0)說明不存在路徑,否則a[1,1]值就是馬走下一步的坐標(biāo),以此遞推輸出路徑。 -1,-1 4,4 4,4 2,3 ???任務(wù)一的源程序: const dx:array[1..4]of integer=(2,2,1,1); dy:array[1..4]of integer=(1,-1,2,-2); type map=record x,y:integer; end; var i,j,n,m,k:integer;

6、a:array[0..50,0..50]of map; begin read(n,m); fillchar(a,sizeof(a),0); a[n,m].x:=-1;a[n,m].y:=-1;{標(biāo)記為終點} for i:=n downto 2 do {倒推} for j:=1 to m do if a[i,j].x<>0 then for k:=1 to 4 do begin a[i-dx[k],j-dy[k]].x:=i; a[i-dx[k],j-dy[k]].y

7、:=j; end; if a[1,1].x=0 then writeln('no') else begin{存在路徑} i:=1;j:=1; write('(',i,',',j,')'); while a[i,j].x<>-1 do begin k:=i; i:=a[i,j].x;j:=a[k,j].y; write('->(',i,',',j,')'); end; end; end. 對于任務(wù)二,也可以使用遞推法,用數(shù)組A[i,j]存放從起點(x1,y1)到(i,j)的路徑總數(shù),按同樣的方法

8、從左向右遞推,一直遞推到(x2,y2),a[x2,y2]即為所求的解。源程序(略) 在上面的例題中,遞推過程中的某個狀態(tài)只與前面的一個狀態(tài)有關(guān),遞推關(guān)系并不復(fù)雜,如果在遞推中的某個狀態(tài)與前面的所有狀態(tài)都有關(guān),就不容易找出遞推關(guān)系式,這就需要我們對實際問題進行分析與歸納,從中找到突破口,總結(jié)出遞推關(guān)系式。我們可以按以下四個步驟去分析:(1)細(xì)心的觀察;(2)豐富的聯(lián)想;(3)不斷地嘗試;(4)總結(jié)出遞推關(guān)系式。 下面我們再看一個復(fù)雜點的例子。 例2、棧(noipxxpj) 題目大意:求n個數(shù)通過棧后的排列總數(shù)。(1≤n≤18) 如輸入 3 輸出 5 算法分析:先模擬入棧、出棧操作

9、,看看能否找出規(guī)律,我們用f(n)表示n個數(shù)通過棧操作后的排列總數(shù),當(dāng)n很小時,很容易模擬出f(1)=1;f(2)=2;f(3)=5,通過觀察,看不出它們之間的遞推關(guān)系,我們再分析N=4的情況,假設(shè)入棧前的排列為“4321”,按第一個數(shù)“4”在出棧后的位置進行分情況討論: (1) 若“4”最先輸出,剛好與N=3相同,總數(shù)為f(3); (2) 若“4”第二個輸出,則在“4”的前只能是“1”,“23”在“4”的后面,這時可以分別看作是N=1和N=2時的二種情況,排列數(shù)分別為f(1)和f(2),所以此時的總數(shù)為f(1)*f(2); (3) 若“4”第三個輸出,則“4”的前面二個數(shù)為“12”,后

10、面一個數(shù)為“3”,組成的排列總數(shù)為f(2)*f(1); (4) 若“4”第四個輸出,與情況(1)相同,總數(shù)為f(3); 所以有:f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3); 若設(shè)0個數(shù)通過棧后的排列總數(shù)為:f(0)=1; 上式可變?yōu)椋篺(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0); 再進一步推導(dǎo),不難推出遞推式: f(n)=f(0)*f(n-1)+f(1)*f(n-2)+…+f(n-1)*f(0); 即f(n)= (n>=1) 初始值:f(0)=1; 有了以上遞推式,就很容易用遞推法寫出程序。 var a:array[0..18]of longint; n,i,j:integer; begin readln(n); fillchar(a,sizeof(a),0); a[0]:=1; for i:=1 to n do for j:=0 to i-1 do a[i]:=a[i]+a[j]*a[i-j-1]; writeln(a[n]); end. 遞推算法最主要的優(yōu)點是算法結(jié)構(gòu)簡單,程序易于實現(xiàn),難點是從問題的分析中找出解決問題的遞推關(guān)系式。對于以上兩個例子,如果在比賽中找不出遞推關(guān)系式,也可以用回溯法求解。

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!