2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法一.doc
《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法一.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法一.doc(4頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法一 在這里介紹兩種基本的搜索算法:深度優(yōu)先搜索和廣度優(yōu)先搜索法,以樹(shù)的搜索為例,深度優(yōu)先搜索法是優(yōu)先擴(kuò)展尚未擴(kuò)展的且具有最大深度的結(jié)點(diǎn);廣度優(yōu)先搜索法是在擴(kuò)展完第K層的結(jié)點(diǎn)以后才擴(kuò)展K+1層的結(jié)點(diǎn)。 深度優(yōu)先搜索法與前面講的回溯法差不多,主要的區(qū)別是回溯法在求解過(guò)程中不保留完整的樹(shù)結(jié)構(gòu),而深度優(yōu)先搜索則記下完整的搜索樹(shù),搜索樹(shù)起記錄解路徑和狀態(tài)判重的作用。為了減少存儲(chǔ)空間,在深度優(yōu)先搜索中,用標(biāo)志的方法記錄訪問(wèn)過(guò)的狀態(tài),這種處理方法使得深度優(yōu)先搜索法與回溯法沒(méi)什么區(qū)別了。在回溯法中,我們己分析了非遞歸的實(shí)現(xiàn)過(guò)程,在這里就只討論深度優(yōu)先的遞歸實(shí)現(xiàn)方法。 深度優(yōu)先搜索的遞歸實(shí)現(xiàn)過(guò)程: procedure dfs(i); for i:=1 to r do if 子結(jié)點(diǎn)mr符合條件then 產(chǎn)生的子結(jié)點(diǎn)mr入棧; if 子結(jié)點(diǎn) mr 是目標(biāo)結(jié)點(diǎn) then 輸出 else dfs(i+1); 棧頂元素出棧(即刪去mr); endif; endfor; 在講解遞推法時(shí),我們討論了用遞推法解騎土游歷問(wèn)題,在這里我們?cè)倏纯慈绾斡蒙疃葍?yōu)先搜索法求解此題。 搜索算法應(yīng)用 例1騎士游歷:設(shè)有一個(gè)n*m的棋盤(pán),在棋盤(pán)上任一點(diǎn)有一個(gè)中國(guó)象棋馬,馬走的規(guī)則為:1.馬走日字 2.馬只能向右走。當(dāng)N,M 輸入之后,找出一條從左下角到右上角的路徑。例如:輸入 N=4,M=4,輸出:路徑的格式:(1,1)->(2,3)->(4,4),若不存在路徑,則輸出"no" 算法分析:我們以44的棋盤(pán)為例進(jìn)行分析,用樹(shù)形結(jié)構(gòu)表示馬走的所有過(guò)程(如下圖),求從起點(diǎn)到終點(diǎn)的路徑,實(shí)際上就是從根結(jié)點(diǎn)開(kāi)始深度優(yōu)先搜索這棵樹(shù)。 馬從(1,1)開(kāi)始,按深度優(yōu)先搜索法,走一步到達(dá)(2,3),判斷是否到達(dá)終點(diǎn),若沒(méi)有,則繼續(xù)往前走,再走一步到達(dá)(4,4),然后判斷是否到達(dá)終點(diǎn),若到達(dá)則退出,搜索過(guò)程結(jié)束。為了減少搜索次數(shù),在馬走的過(guò)程中,判斷下一步所走的位置是否在棋盤(pán)上,如果不在棋盤(pán)上,則另選一條路徑再走。 程序如下: 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,n,m:integer; a:array[0..50]of map; procedure dfs(i:integer); var j:integer; begin for j:=1 to 4 do if (a[i-1].x+dx[j]>0)and(a[i-1].x+dx[j]<=n) and(a[i-1].y+dy[j]>0)and(a[i-1].y+dy[j]<=n) then{判斷是否在棋盤(pán)上} begin a[i].x:=a[i-1].x+dx[j]; a[i].y:=a[i-1].y+dy[j];{入棧} if (a[i].x=n)and(a[i].y=m)then begin write((,1,,,1,)); for j:=2 to i do write(->(,a[j].x,,,a[j].y,)); halt;{輸出結(jié)果并退出程序} end; dfs(i+1);{搜索下一步} a[i].x:=0;a[i].y:=0;{出棧} end; end; begin a[1].x:=1;a[1].y:=1; readln(n,m); dfs(2); writeln(no); end. 從上面的例子我們可以看出,深度優(yōu)先搜索算法有兩個(gè)特點(diǎn): 1、 己產(chǎn)生的結(jié)點(diǎn)按深度排序,深度大的結(jié)點(diǎn)先得到擴(kuò)展,即先產(chǎn)生它的子結(jié)點(diǎn)。 2、 深度大的結(jié)點(diǎn)是后產(chǎn)生的,但先得到擴(kuò)展,即“后產(chǎn)生先擴(kuò)展”,與棧的工作原理相同,因此用堆棧作為該算法的主要數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)產(chǎn)生的結(jié)點(diǎn)。 對(duì)于不同的問(wèn)題,深度優(yōu)先搜索算法基本上是一樣的,但在具體處理方法和編程技巧上又都不相同,甚至?xí)泻艽蟮牟顒e。我們?cè)倏纯戳硪粋€(gè)例子。 題二 選數(shù)(存盤(pán)名:NOIPxxpj) [問(wèn)題描述]:已知 n 個(gè)整數(shù) x1,x2,…,xn,以及一個(gè)整數(shù) k(k<n)。從n 個(gè)整數(shù)中任選 k 個(gè)整數(shù)相加,可分別得到一系列的和。例如當(dāng) n=4,k=3,4 個(gè)整數(shù)分別為 3,7,12,19 時(shí),可得全部的組合與它們的和為:3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34?,F(xiàn)在,要求你計(jì)算出和為素?cái)?shù)共有多少種。例如上例,只有一種的和為素?cái)?shù):3+7+19=29。 [輸入]:鍵盤(pán)輸入,格式為: n , k (1<=n<=20,k<n) x1,x2,…,xn (1<=xi<=5000000) [輸出]:屏幕輸出,格式為: 一個(gè)整數(shù)(滿足條件的種數(shù))。 [輸入輸出樣例]: 輸入:4 3 3 7 12 19 輸出:1 算法分析:本題是求從n個(gè)數(shù)中選k個(gè)數(shù)的組合,并使其和為素?cái)?shù)。求解此題時(shí),先用深度優(yōu)先搜索法生成k個(gè)數(shù)的組合,再判斷k個(gè)數(shù)的和是否為素?cái)?shù),若為素?cái)?shù)則總數(shù)加1。 在程序?qū)崿F(xiàn)過(guò)程中,用數(shù)組a存放輸入的n個(gè)數(shù),用s表示k個(gè)數(shù)的和,ans表示和為素?cái)?shù)的個(gè)數(shù)。為了避免不必要的搜索,程序?qū)λ阉鬟^(guò)程進(jìn)行了優(yōu)化,限制搜索范圍,在搜索過(guò)程dfs(i,m)中,參數(shù)m為第i個(gè)數(shù)的上限,下限為n-k+i。 源程序: var n,k,i: byte; ans,s:longint; a: array[1 .. 20] of Longint; procedure prime(s:longint);{判斷K個(gè)數(shù)的和是否為素?cái)?shù)} var i:integer; begin i:=2; while (sqr(i)<=s)and(s mod i<>0) do inc(i); if sqr(i)>s then inc(ans){若為素?cái)?shù)則總數(shù)加1} end; procedure dfs(i,m:byte);{搜索第i個(gè)數(shù), } var j:byte;{j表示第i個(gè)數(shù)的位置 begin for j:=m to n-k+i do{枚舉第i個(gè)數(shù)} begin inc(s,a[j]);{入棧} if i=k then prime(s) else dfs(i+1,j+1);{繼續(xù)搜第i+1個(gè)數(shù)} dec(s,a[j]){出棧} end end; begin readln(n,k); for i:=1 to n do read(a[i]); ans:=0; s:=0; dfs(1,1); writeln(ans); end. 從上面的兩個(gè)例子我們可以看出,用遞歸實(shí)現(xiàn)深度優(yōu)先搜索比非遞歸更加方便。 在使用深度搜索法解題時(shí),搜索的效率并不高,所以要重視對(duì)算法的優(yōu)化,盡可能的減少搜索范圍,提高程序的速度。 在下一篇中將繼續(xù)介紹另一種搜索方法——廣度優(yōu)先搜索法。- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法一 2019 2020 年高 信息技術(shù) 全國(guó)青少年 奧林匹克 聯(lián)賽 教案 搜索
鏈接地址:http://italysoccerbets.com/p-2577036.html