歡迎來(lái)到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁(yè) 裝配圖網(wǎng) > 資源分類 > DOC文檔下載  

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

  • 資源ID:105037956       資源大小:42.02KB        全文頁(yè)數(shù):4頁(yè)
  • 資源格式: DOC        下載積分:9.9積分
快捷下載 游客一鍵下載
會(huì)員登錄下載
微信登錄下載
三方登錄下載: 微信開(kāi)放平臺(tái)登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要9.9積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號(hào),方便查詢和重復(fù)下載(系統(tǒng)自動(dòng)生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號(hào):
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開(kāi),此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁(yè)到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無(wú)水印,預(yù)覽文檔經(jīng)過(guò)壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒(méi)有明確說(shuō)明有答案則都視為沒(méi)有答案,請(qǐng)知曉。

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

2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法所謂遞推,是指從已知的初始條件出發(fā),依據(jù)某種遞推關(guān)系,逐次推出所要求的各中間結(jié)果及最后結(jié)果。其中初始條件或是問(wèn)題本身已經(jīng)給定,或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)后確定。可用遞推算法求解的題目一般有以下二個(gè)特點(diǎn):(1) 問(wèn)題可以劃分成多個(gè)狀態(tài);(2) 除初始狀態(tài)外,其它各個(gè)狀態(tài)都可以用固定的遞推關(guān)系式來(lái)表示。在我們實(shí)際解題中,題目不會(huì)直接給出遞推關(guān)系式,而是需要通過(guò)分析各種狀態(tài),找出遞推關(guān)系式。遞推法應(yīng)用例1騎士游歷:(noip1997tg)設(shè)有一個(gè)n*m的棋盤(2<=n<=50,2<=m<=50),如下圖,在棋盤上任一點(diǎn)有一個(gè)中國(guó)象棋馬,馬走的規(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í)給出馬起始的位置和終點(diǎn)的位置,試找出從起點(diǎn)到終點(diǎn)的所有路徑的數(shù)目。例如:(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è)n×m的棋盤,i的值從1到n,j的值從1到m。棋盤上的任意點(diǎn)都可以用坐標(biāo)(i,j)表示。對(duì)于馬的移動(dòng)方法,我們用K來(lái)表示四種移動(dòng)方向(1,2,3,4);而每種移動(dòng)方法用偏移值來(lái)表示,并將這些偏移值分別保存在數(shù)組dx和dy中,如下表 KDxkDyk12122-131241-2 根據(jù)馬走的規(guī)則,馬可以由(i-dxk,j-dyk)走到(i,j)。只要馬能從(1,1)走到(i-dxk,j-dyk),就一定能走到(i,j),馬走的坐標(biāo)必須保證在棋盤上。我們以(n,m)為起點(diǎn)向左遞推,當(dāng)遞推到(i-dxk,j-dyk)的位置是(1,1)時(shí),就找到了一條從(1,1)到(n,m)的路徑。我們用一個(gè)二維數(shù)組a表示棋盤,對(duì)于任務(wù)一,使用倒推法,從終點(diǎn)(n,m)往左遞推, 設(shè)初始值an,m為(-1,-1),如果從(i,j)一步能走到(n,m),就將(n,m)存放在ai,j中。如下表,a3,2和a2,3的值是(4,4),表示從這兩個(gè)點(diǎn)都可以到達(dá)坐標(biāo)(4,4)。從(1,1)可到達(dá)(2,3)、(3,2)兩個(gè)點(diǎn),所以a1,1存放兩個(gè)點(diǎn)中的任意一個(gè)即可。遞推結(jié)束以后,如果a1,1值為(0,0)說(shuō)明不存在路徑,否則a1,1值就是馬走下一步的坐標(biāo),以此遞推輸出路徑。-1,-14,44,42,3   任務(wù)一的源程序:const dx:array1.4of integer=(2,2,1,1); dy:array1.4of integer=(1,-1,2,-2);type map=record x,y:integer; end;var i,j,n,m,k:integer; a:array0.50,0.50of map;begin read(n,m); fillchar(a,sizeof(a),0); an,m.x:=-1;an,m.y:=-1;標(biāo)記為終點(diǎn) for i:=n downto 2 do 倒推 for j:=1 to m do if ai,j.x<>0 then for k:=1 to 4 do begin ai-dxk,j-dyk.x:=i; ai-dxk,j-dyk.y:=j; end; if a1,1.x=0 then writeln('no') else begin存在路徑 i:=1;j:=1; write('(',i,',',j,')'); while ai,j.x<>-1 dobegin k:=i;i:=ai,j.x;j:=ak,j.y; write('->(',i,',',j,')'); end; end;end.對(duì)于任務(wù)二,也可以使用遞推法,用數(shù)組Ai,j存放從起點(diǎn)(x1,y1)到(i,j)的路徑總數(shù),按同樣的方法從左向右遞推,一直遞推到(x2,y2),ax2,y2即為所求的解。源程序(略)在上面的例題中,遞推過(guò)程中的某個(gè)狀態(tài)只與前面的一個(gè)狀態(tài)有關(guān),遞推關(guān)系并不復(fù)雜,如果在遞推中的某個(gè)狀態(tài)與前面的所有狀態(tài)都有關(guān),就不容易找出遞推關(guān)系式,這就需要我們對(duì)實(shí)際問(wèn)題進(jìn)行分析與歸納,從中找到突破口,總結(jié)出遞推關(guān)系式。我們可以按以下四個(gè)步驟去分析:(1)細(xì)心的觀察;(2)豐富的聯(lián)想;(3)不斷地嘗試;(4)總結(jié)出遞推關(guān)系式。下面我們?cè)倏匆粋€(gè)復(fù)雜點(diǎn)的例子。例2、棧(noipxxpj)題目大意:求n個(gè)數(shù)通過(guò)棧后的排列總數(shù)。(1n18)如輸入 3 輸出 5算法分析:先模擬入棧、出棧操作,看看能否找出規(guī)律,我們用f(n)表示n個(gè)數(shù)通過(guò)棧操作后的排列總數(shù),當(dāng)n很小時(shí),很容易模擬出f(1)=1;f(2)=2;f(3)=5,通過(guò)觀察,看不出它們之間的遞推關(guān)系,我們?cè)俜治鯪=4的情況,假設(shè)入棧前的排列為“4321”,按第一個(gè)數(shù)“4”在出棧后的位置進(jìn)行分情況討論:(1) 若“4”最先輸出,剛好與N=3相同,總數(shù)為f(3);(2) 若“4”第二個(gè)輸出,則在“4”的前只能是“1”,“23”在“4”的后面,這時(shí)可以分別看作是N=1和N=2時(shí)的二種情況,排列數(shù)分別為f(1)和f(2),所以此時(shí)的總數(shù)為f(1)*f(2);(3) 若“4”第三個(gè)輸出,則“4”的前面二個(gè)數(shù)為“12”,后面一個(gè)數(shù)為“3”,組成的排列總數(shù)為f(2)*f(1);(4) 若“4”第四個(gè)輸出,與情況(1)相同,總數(shù)為f(3);所以有:f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3);若設(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);再進(jìn)一步推導(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:array0.18of longint; n,i,j:integer;begin readln(n); fillchar(a,sizeof(a),0); a0:=1; for i:=1 to n do for j:=0 to i-1 do ai:=ai+aj*ai-j-1; writeln(an);end.遞推算法最主要的優(yōu)點(diǎn)是算法結(jié)構(gòu)簡(jiǎn)單,程序易于實(shí)現(xiàn),難點(diǎn)是從問(wèn)題的分析中找出解決問(wèn)題的遞推關(guān)系式。對(duì)于以上兩個(gè)例子,如果在比賽中找不出遞推關(guān)系式,也可以用回溯法求解。

注意事項(xiàng)

本文(2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法)為本站會(huì)員(xt****7)主動(dòng)上傳,裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請(qǐng)重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

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

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


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