2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索.doc
《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索.doc(16頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索 從一個(gè)簡(jiǎn)單題目開始。 例1.輸出n個(gè)元素的無(wú)重復(fù)的全排列。(1<=n<=9) 在這里我們可以對(duì)每一個(gè)元素編號(hào),形成1,2,…,8,9個(gè)數(shù)字的全排列。我們用一個(gè)一維數(shù)組來(lái)處理,相當(dāng)于有9個(gè)位置,每個(gè)位置可以放1到9,再進(jìn)行重復(fù)性判斷,即在每個(gè)位置放一個(gè)數(shù)字時(shí)判斷它前面是否已經(jīng)使用該數(shù)字。通過(guò)數(shù)組中元素值的變化,產(chǎn)生全排列。 下面給出非遞歸例程,其中,變量k是表示位置指針,數(shù)組x用來(lái)裝每個(gè)位置的值。 const n=5; var x:array[1..10] of integer; k:integer; {位置指針} function try:boolean; {判重函數(shù)} var i:integer; begin for i:=1 to k-1 do if x[i]=x[k] then begin try:=false;exit;end; try:=true; end; procedure out; {輸出過(guò)程} var i:integer; begin for i:=1 to n do write(x[i]); writeln; end; begin k:=1; x[1]:=0; while k>0 do begin inc(x[k]); {當(dāng)前第k個(gè)位置中增加1} if x[k]>n then {判斷當(dāng)前第k個(gè)位置中是否超界,超界指針后移一位} dec(k) else if try then {判重} begin inc(k);x[k]:=0; {前進(jìn)1位} if k>n then{判斷指針是否超界,決定一個(gè)排列是否完成,完成指針后移一位} begin out;dec(k);end; end; end; end. 下面是遞歸例程: const n=5; var x:array[1..10] of integer; function try(v1,k:integer):boolean; {判重函數(shù),v1表示位置,k表示所放的值} var i:integer; begin for i:=1 to v1-1 do if x[i]=k then begin try:=false;exit;end; try:=true; end; procedure out; {輸出過(guò)程} var i:integer; begin for i:=1 to n do write(x[i]); writeln; end; procedure search(v:integer); {v表示第v個(gè)位置} var i:integer; begin if v>n then begin out;exit;end; {若v超界,一個(gè)排列完成} for i:=1 to n do {在第v個(gè)位置上分別放1到n} if try(v,i) then {如果不重復(fù),處理第v+1個(gè)位置} begin x[v]:=i;search(v+1);end; end; begin search(1); end. 說(shuō)明:使用非遞歸的好處是節(jié)約內(nèi)存,當(dāng)一些題目對(duì)內(nèi)存消耗較大時(shí),建議使用非遞歸方式;但使用遞歸方式在程序運(yùn)行時(shí)間上要好一些,因?yàn)樵诿總€(gè)節(jié)點(diǎn)擴(kuò)展時(shí),遞歸方式少一個(gè)范圍超界判斷。 例題一 簡(jiǎn)單的背包問(wèn)題。 設(shè)有一個(gè)背包,可以放入的重量為s?,F(xiàn)有n件物品,重量分別為 均為正整數(shù),從n件物品中挑選若干件,使得放入背包的重量之和正好為s。 分析:可以設(shè)定n個(gè)位置,每個(gè)位置只能放0和1,這樣形成一個(gè)0和1可重復(fù)的排列,或者是產(chǎn)生一個(gè)n位的2進(jìn)制數(shù)。 例程: var w:array[1..20] of integer; x:array[1..20] of integer; n:integer; s:longint; procedure init; var i:integer; begin readln(n,s); for i:=1 to n do read(w[i]); end; function try(v1,k:integer):boolean; {判斷目標(biāo)函數(shù),v1表示位置,k表示所放的值} var i:integer; s1:longint; begin s1:=w[k]; for i:=1 to v1-1 do s1:=s1+x[i]*w[i]; if s1=s then begin for i:=1 to v1-1 do if x[i]=0 then write(w[i], ); writeln(w[k]); end; if s1>=s then begin try:=false;exit;end; else try:=true; end; procedure search(v:integer); {v表示第v個(gè)位置} var i:integer; begin if v>n then exit;{若v超界,一個(gè)排列完成,本次選擇物品方案不成功,退出} for i:=0 to 1 do{在第v個(gè)位置上分別放0到1} if try(v,i) then{判斷所選物品之和是否大于等于s,否則處理第v+1個(gè)位置} begin x[v]:=i;search(v+1);end; end; begin init;search(1); end. 說(shuō)明:本文用全排列進(jìn)行引入DFS搜索,目的是表明DFS有一定的模式,如下: procedure search(v:integer;相關(guān)形參); {v表示當(dāng)前擴(kuò)展節(jié)點(diǎn)層數(shù)(或者叫深度)} {過(guò)程定義的變量表} begin if <超界條件> then begin out;exit;end; {若v超界,out來(lái)作超界處理} 形成某種節(jié)點(diǎn)擴(kuò)展程序段(例如:for i:=1 to n do) if 〈判斷所到節(jié)點(diǎn)的算法函數(shù)或條件〉 then {例如判重} begin 當(dāng)前節(jié)點(diǎn)處理; search(v+1); {處理下一個(gè)層數(shù)} end; end; 例題二 給出一個(gè)自然數(shù)n( ),把n分解為若干個(gè)大于1的自然數(shù)之乘積。請(qǐng)編寫程序找出所有的分解方案。 分析:此題目的關(guān)鍵是怎樣產(chǎn)生需要擴(kuò)展的各個(gè)節(jié)點(diǎn)。不難看出乘積為n的若干自然數(shù),剛好都是n的約數(shù)。因此其分解方案變成了求這些約數(shù)的不同組合(元素可重復(fù)),問(wèn)題得到解決。 例程: var y:array[1..50] of longint; {用來(lái)存放n的所有約數(shù)} x:array[0..50] of integer; {用來(lái)存放組合數(shù)的對(duì)應(yīng)n的約數(shù)所在位置值} n:longint; xlen:integer; procedure init; var i,j,t:longint; k:integer; begin fillchar(x,sizeof(x),0); x[0]:=1; xlen:=0; for i:=2 to trunc(sqrt(n)) do {找出n的所有約數(shù)} if n mod i=0 then begin inc(xlen);y[xlen]:=i;inc(xlen);y[xlen]:=n div i; if i=n div i then {對(duì)完全平方數(shù)的處理} dec(xlen); end; for i:=1 to xlen-1 do {為保證輸出方案由小到大的順序,進(jìn)行排序處理} begin k:=i; for j:=i+1 to xlen do if y[k]>y[j] then k:=j; t:=y[i];y[i]:=y[k];y[k]:=t; end; end; function try(v1,k:integer):boolean; {判定所選約數(shù)之乘積與n的關(guān)系} var i:integer; t:longint; begin t:=y[k]; for i:=1 to v1-1 do t:=t*y[x[i]]; if t=n then {與n剛好相等,輸出一種方案} begin for i:=1 to v1-1 do write(y[x[i]], ); writeln(y[k]); end; if t- 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)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索 2019 2020 年高 信息技術(shù) 全國(guó)青少年 奧林匹克 聯(lián)賽 教案 深度 優(yōu)先 搜索 廣度
鏈接地址:http://www.hcyjhs8.com/p-2595527.html