練習(xí)三第一題consta:array[1..10,1..10]

of

0..1

=((0,1,0,0,0,0,0,1,1,0),(1,0,0,1,1,0,0,1,1,1),(0,0,0,0,0,0,0,0,1,0),(0,1,0,0,0,0,0,1,1,1),(0,1,0,0,0,0,0,0,1,1),(0,0,0,0,0,0,1,0,1,1),(0,0,0,0,0,1,0,0,1,0),(1,1,0,1,0,0,0,0,1,1),(1,1,1,1,1,1,1,1,0,1),(0,1,0,1,1,1,0,1,1,0));vars:

array

[0..10]of

byte;t:

setof

byte;tot:longint;procedure

make(k

:integer);vari,j:integer;beginif k=10

thenbegininc(tot);for

i:=1

to

10

dowrite(s[i]-1);wri

n;exit;

end;for

i:=1

to

10

doif

((a[s[k],i]=1)

and(i in

t))or

(k=0)thenbegins[k+1]:=i;t:=t-[i];make(k+1);t:=t+[i];end;end;begint:=[1..10];make(0);wri

n('total=',tot);end.第二題求解方法：vara:array[-2..9,-2..9]

of

integer;now:

longint;s:array[0..100]

of

recordfx,

fy,

tx,

ty:byte;end;;{初始化}procedurevari,j:integer;beginfor

i:=-2

to

9

dofor

j:=-2

to

9

doa[i,j]:=-1;for

i:=1

to 7dofor

j:= 1to7

doa[i,j]:=1;a[4,4]:=0;for

i:=1

to

2

dofor

j:=1to

2dobegin{左/右/左下/右下為不能走}a[i,j]:=-1;a[i,j+5]:=-1;a[i+5,j]:=-1;a[i+5,j+5]:=-1;end;end;procedure

make(l:word);vari,j:integer;beginif l=1

then{如果找到了解}beginif(a[4,4]=1)thenbeginfor

i:=1

to

7

dobeginfor

j:=1to

7dowrite(a[i,j]:3);wri

n;end;wri

n;wri

n;for

i:=31

downto

1

dowri

n('(',s[i].fx,',',s[i].fy,')-->(',s[i].tx,',',s[i].ty,')');wri

n;wri

n('Time=',(meml[$40:$6c]-now)/18.2:0:2);halt;end;exit;end;for

i:=1

to

7

dofor

j:=1to

7dobeginif

a[i,j]=1

thenbeginif

(a[i-2,j]=0)

and

(a[i-1,j]=1)

then{考慮上邊吃棋子}begina[i-1,j]:=0;s[l-1].fx:=i;s[l-1].tx:=i-2;a[i-1,j]:=1;a[i-2,j]:=1;a[i,j]:=0;s[l-1].fy:=j;s[l-1].ty:=j;make(l-1);a[i-2,j]:=0;a[i,j]:=1;end;if

(a[i+2,j]=0)

and

(a[i+1,j]=1)

then

{考慮下邊吃棋子}begina[i+2,j]:=1;a[i+1,j]:=0;a[i,j]:=0;s[l-1].fx:=i;s[l-1].fy:=j;s[l-1].tx:=i+2;s[l-1].ty:=j;make(l-1);a[i+2,j]:=0;a[i+1,j]:=1;a[i,j]:=1;end;if

(a[i,j-2]=0)

and

(a[i,j-1]=1)

then

{考慮左邊吃棋子}begina[i,j-2]:=1;a[i,j-1]:=0;a[i,j]:=0;s[l-1].fx:=i;s[l-1].fy:=j;s[l-1].tx:=i;a[i,j-1]:=1;a[i,j]:=1;s[l-1].ty:=j-2;make(l-1);a[i,j-2]:=0;end;if(a[i,j+2]=0)

and

(a[i,j+1]=1)

then

{考慮右邊吃棋子}begina[i,j+2]:=1;a[i,j+1]:=0;a[i,j]:=0;s[l-1].fx:=i;s[l-1].fy:=j;s[l-1].tx:=i;s[l-1].ty:=j+2;make(l-1);a[i,j+2]:=0;a[i,j+1]:=1;a[i,j]:=1;end;end;end;end;beginnow:=meml[$40:$6c];;make(32);end.第三題算法：var

n,m:integer;

x1,y1,x2,y2:integer;a:array[1..100,1..100]

of

0..1;b:array[1..100,1..100]

of

integer;c:array[1..10000,1..2]

of

byte;{

初始化}procedure

init;varf:text;i,j:integer;beginassign(f,'day2_3.in');reset(f);readln(f,n,m);for

i:=1

to

n

dofor

j:=1to

mdoread(f,a[i,j]);readln(f,x1,y1,x2,y2);close(f);

end;procedure

calc;vari,j,k,x,y:integer;open,closed:integer;procedure

evaluate(i,j,l:integer);begininc(k);if

b[i,j]<maxint

thenexit;inc(closed);c[closed,1]:=i;c[closed,2]:=j;b[i,

j]:=b[x,y]+1;end;beginfor

i:=1

to

n

dofor

j:=1to

mdob[i,j]:=maxint;open:=0;closed:=1;b[x1,y1]:=-1;c[1,1]:=x1;c[1,2]:=y1;repeatinc(open);x:=c[open,1];y:=c[open,2];k:=x-1;while

(a[k,y]=1)

and(k>=1)

doevaluate(k,y,-1);k:=x+1;while

(a[k,y]=1)

and(k<=n)

doevaluate(k,y,1);k:=y-1;while

(a[x,k]=1)

and(k>=1)

doevaluate(x,k,-1);k:=y+1;while

(a[x,k]=1)

and

(k<=m)

doevaluate(x,k,1);until

(open>=closed)

or

(b[x2,y2]<maxint);end;procedure

print;varf:text;beginif

b[x2,y2]<maxint

thenwri n('Mincross:

',b[x2,y2])elsewri n('No

solution');end;begininit;calc;printend.第四講圖的最小生成樹一、圖的生成樹通圖G中，如果它的全部頂點(diǎn)和部分邊構(gòu)成一個(gè)子圖G’，且邊將圖中的所有頂點(diǎn)連通又不形成回路，則稱子圖G’是原圖G的一棵生成樹。要構(gòu)成這樣的圖，其基本算法如下：從圖“G”的選取一個(gè)頂點(diǎn)放到“G’”中，因只有一個(gè)頂點(diǎn)，因此該圖是連通的；以后每加入一個(gè)頂點(diǎn)，都要加入以該點(diǎn)為頂點(diǎn)以已連通的

頂點(diǎn)之中的一個(gè)頂點(diǎn)為端點(diǎn)的一條邊，使其既連通而不產(chǎn)生回路，進(jìn)行n-1次后，就產(chǎn)生G’，在G’中有n個(gè)頂點(diǎn)，n-1條邊且不產(chǎn)

生回路。如下圖所示：二、圖的最小生成樹對(duì)于

通網(wǎng)（帶權(quán)的圖），生成的樹不同，每棵樹的路徑總長度就可能不同，其中具有最小權(quán)的樹

稱為最小生成樹。研究圖的生成樹的意義：例如：圖的最小生成樹主要有兩種方法：prim算法，kruskal算法。三、prim算法prim算法的要點(diǎn)是：設(shè)有n個(gè)頂點(diǎn)的連通網(wǎng)：G=（V，E），T=（U，TE）是G的最小生成樹，其中U是頂點(diǎn)集，TE是T的邊集，U、TE開始值為空原圖用鄰接矩陣1

2

3

4

5

6

7∞

8

∞

5

∞

∞

∞8

∞

12

3

10

∞

∞∞12∞∞62∞53∞∞∞715∞106∞∞9∞∞∞279∞∞∞

∞

∞

15

∞

∞

∞（3）prim

算法的實(shí)現(xiàn)過程1234567首先任取一個(gè)頂點(diǎn)（V1）進(jìn)入頂點(diǎn)集合，U={V1}，只要U?V，就找這樣的一條邊，它的一個(gè)端點(diǎn)已經(jīng)在樹T(vi)中，而將另一個(gè)端點(diǎn)且仍在T外，且長度最短的邊，假定為(vi,vj),將該邊并入邊的集合（TE），(vj)并入頂點(diǎn)的集合（U）。將該操作重復(fù)執(zhí)行多次，直到所有頂點(diǎn)都并入頂點(diǎn)集合中。問題關(guān)鍵：每次如何從生成樹T中到T外的所有邊中，快速找出一條最短路徑。分析：假設(shè)已經(jīng)生成K個(gè)頂點(diǎn)，K-1條邊的樹，需要搜索K個(gè)頂點(diǎn)與n-k條邊的聯(lián)系，這樣時(shí)間復(fù)雜性為O（k(n-k))。能否降低查找時(shí)間則成為該題關(guān)鍵。解決方法：初始化U={

V1}TE={}LW={

（V1，V2）8，（V1，V3）∞，（V1，V4）5，（V1，V5）∞，（V1，V6）∞

}第一次：U={V1，V4}TE={（V1，V4）5}LW={（V4，V2）3，（V1，V3）∞，（V1，V5）∞，（V4，V6）7，（V4，V7）15

}第二次：U={V1，V4，V2}TE={（V1，V4）5，（V4，V2）3}LW={（V2，V3）12，（V2，V5）10，（V6，V4）7，（V4，V7）15

}第三次U={

V1，V4，V2

，V6

}TE={（V1，V4）5，（V4，V2）3

，（V4，V6）7

}LW={（V6，V3）2，（V6，V5）9，（V4，V7）15

}第四次U={V1，V4，V2

，V6，V3}TE=

{（V1，V4）5，（V4，V2）3

（V4，V6）7，（V6，V3）2

}LW=

{（V3，V5）6，（V4，V7）15

}第五次U={V1，V4，V2

，V6，V3

，V5}TE=

{（V1，V4）5，（V4，V2）3

，（V4，V6）7，（V6，V32

，（V3，V5）6

}LW=

{（V4，V7）15第六次U={V1，V4，V2，V6，V3

，V5，V7}TE=

{（V1，V4）5，（V4，V2）3

，（V4，V6）7，（V6，V3）2

，（V3，V5）6}，（V4，V7）15

}LW=

{

}（4）算法如下：Procedure

Prim(GA,CT);beginfor

I:=1

to

n-1

do

{給CT賦初值，對(duì)應(yīng)第0次的LW值}[

CT[I].from

:=1

; ct[I].end:=I+1

; ct[I].w:=GA[i,

i+1

];for

k:=1

to

n-1

do

{進(jìn)行n-1次循環(huán)，求出最小生成樹的第K條邊}①

[min:=maxint

;m:=k;for

j:=k

to

n-1

doif ct[I].w<min

thenmin:=ct[j].wrgite

m::=j;

]②

if m<>k

then ct[k]

與ct[m]

的交換{將最短邊調(diào)到第K單元}③

j:=ct[k].end;

{

將新的并入T中頂點(diǎn)給J

}for

I:=k+1

to

n-1

do

{

修改LW中的有關(guān)邊

}[

d:=ct[I].end

; w:=GA[j,

d

]

;IF

W<CT[I].W

then [

CT[i].

w:=w;CT[i].from:=j

;]End;四、

Kruskal

算法Kruskal

算法的關(guān)鍵在于如何判斷是否構(gòu)成回路。判斷最小生成樹在構(gòu)成過程中，是否構(gòu)成回路的方法：方法：將各個(gè)頂點(diǎn)劃分所屬集合的方法解決。每個(gè)集合的頂點(diǎn)表示一個(gè)無回路的連通分量。(1)初始化：{V1},{V2},{V3},{V4},{V5},{V6}當(dāng)從邊集數(shù)組中按次序選擇一條邊時(shí)，若它的兩個(gè)端點(diǎn)分別屬于兩個(gè)不同的集合，則表明該邊連接了兩個(gè)不同的連通分量，無回路，該邊作為樹的一條邊，將端點(diǎn)所在的兩個(gè)集合合并為一個(gè)集合，此時(shí)它們成為

通分量。若選擇的邊的兩個(gè)端點(diǎn)在一個(gè)集合中，則放棄該邊，否則造成回路。{V1,V5},

{V2,V3,V4},

{V6}{V1,V5},

{V2,V3,V4,V6}{V1,V5,V2,V3,V4,V6}算法的實(shí)現(xiàn)：用邊集數(shù)組存放圖的結(jié)構(gòu)：GE，記錄數(shù)組實(shí)現(xiàn)邊的排序：按邊的權(quán)值進(jìn)行用集合數(shù)組S存放連通的頂點(diǎn)集合用C數(shù)組存放生成的第i條邊屬于GE邊集數(shù)組的第X條邊下標(biāo)序號(hào)。kruskal (GE,C);算法：Procedurebeginfor

i:=1

to

n

do s[i]:=

[i

]

;

{

初始化頂點(diǎn)集合

}i:=1

;

j:=1

{ i

表示邊數(shù)，j

表示數(shù)組GE的下標(biāo)

}while

i<=n-1

do[(1)

for

k:=1

to

n

dobeginif

GE[J].fr

in

s[k]

then m1:=k;if

GE[J].ed

in

s[k]

then m2:=k;end;{記錄第j條邊的兩個(gè)端點(diǎn)的集合序號(hào)}(2)

if

m1<>

m2

then

{

生成樹的一條邊}beingc[i]:=j

;

{保存生成樹的第i條邊,因?yàn)閖

是GE數(shù)組的下標(biāo)}i:=i+1;s[m1]:=s[m1]+s[m2];s[m2]:=[

]

;end;(3) j:=j+1;end;運(yùn)行該程序后，C數(shù)組的值為：1

2

3

4

5所以最小生成樹由GE數(shù)組中的1，2，3，5，7

邊組成。12357五、應(yīng)用舉例（高級(jí)本P

206）例題1

設(shè)有一堆沙子排成一排，其為1，2，3，4…,n,每堆沙子重量如下：13，7，8，16，21，4，18現(xiàn)在將n堆沙子歸并,使歸并的總代價(jià)和最少。歸并方法：每次只能將相鄰的兩堆沙子堆成一堆，經(jīng)過n-1次后最后成一堆。沙子歸并重量的和稱為代價(jià)，全部代價(jià)稱為總代價(jià)。例如，當(dāng)n=2

時(shí)，僅有一種歸并方法當(dāng)n=3時(shí)總代價(jià)（1）

20+24=44，總代價(jià)（2）11+24=35當(dāng)n=4時(shí)總代價(jià)

（1）S=20+34+40=94（2）21+34+40=95總代價(jià)是

S=20+20+40=80

，

S=21+27+40=88，S=20+27+40=87當(dāng)n=4時(shí)，有五種方法，總結(jié)歸并的幾種形式：前歸并，兩兩歸并、后歸并歸納為一般形式：設(shè)F（I，J）表示從I

堆沙子到J

堆沙子歸并的最小代價(jià)數(shù)。F（1，4）=min{ f(1,3),f(1,2)+f(3,4),f(2,4)

}

+40而f(1,3)=min{f(1,2),f(2,3)}+34f(1,2)=20,

f(3,4)=20 f(2,3)=21f(2,4)=min

{

f(2,3),f(3,4)}

+27任意堆沙子（n）：F(1,n)=mi