算法與數(shù)據(jù)結(jié)構(gòu)講義三（搜索算法）

第十三課搜索算法

12.0搜索樹(shù)

12.1搜索算法的基本原理

12.2廣度優(yōu)先搜索

12.3深度優(yōu)先搜索

12.4練習(xí)

12.0搜索樹(shù)

引例：在一個(gè)4*4的棋盤上的左下角有一個(gè)馬，按照國(guó)際象棋的規(guī)則，將這個(gè)馬跳到右

上角。

分析：首先建立棋盤的坐標(biāo)，我們以左下角為(1,1),以右上角、

為(4,4)。按照馬的移動(dòng)規(guī)則，假定當(dāng)前馬的位置坐標(biāo)為

(x,y),則移動(dòng)方法有：

(1)x'=x+l;y'=y+2*

(2)x'=x+l；y'=y-2;

(3)x'=x+2;y'=y+l;

(4)x'=x+2;y'=y-l；

(5)x'=x-l;y'=y+2;

(6)x'=x-l;y'=y-2;

(7)x'=x-2;y'=y+l;

界限制無(wú)法到達(dá))；(2,3漢可以跳到(1,1)、(4,4)、(4,2)、(3,1)四個(gè)點(diǎn)，(3,2)

可以跳達(dá)(1,1)、(1,3)、(2,4)、(4,4)四個(gè)點(diǎn)，……。

搜索樹(shù)：按照數(shù)據(jù)元素的產(chǎn)生式規(guī)則建立起來(lái)的數(shù)據(jù)元素邏輯關(guān)系。

特點(diǎn)：(1)數(shù)據(jù)之間的邏輯關(guān)系為一對(duì)多。

(2)每個(gè)結(jié)點(diǎn)數(shù)據(jù)的下一級(jí)子結(jié)點(diǎn)是由該結(jié)點(diǎn)的產(chǎn)生式規(guī)則生成。

（3）目標(biāo)結(jié)點(diǎn)（答案數(shù)據(jù)）一定在搜索樹(shù)中能夠出現(xiàn)。

（4）對(duì)于數(shù)據(jù)規(guī)模較大的問(wèn)題，搜索樹(shù)的結(jié)點(diǎn)將是海量的。

（5）搜索樹(shù)可能是無(wú)窮無(wú)盡的（因?yàn)楹芏嘟Y(jié)點(diǎn)回重復(fù)出現(xiàn)）。

12.1搜索算法的基本原理：

從搜索樹(shù)中可以看出，一個(gè)問(wèn)題從起始狀態(tài)，通過(guò)窮舉的方式建立起搜索樹(shù)后，目標(biāo)狀態(tài)一定能在

搜索樹(shù)中出現(xiàn)。因此，只要建立起搜索樹(shù)，就可以在其中搜索到目標(biāo)狀態(tài)（數(shù)據(jù)、路徑、位置等）。

搜索算法要解決的問(wèn)題：

產(chǎn)生式規(guī)則：由當(dāng)前狀態(tài)按照問(wèn)題的需求和限制，生成新的狀態(tài)的方法集合。

搜索樹(shù)的生成和存儲(chǔ)：一般采用一邊生成，一邊搜索；存儲(chǔ)方法有：集合、棧。

搜索的方法：按行搜索：即從上到下，逐層搜索

雙向按行搜索：一邊從上往下（起始狀態(tài)到中間狀態(tài)），一邊從下往上逐

層搜索（從目標(biāo)狀態(tài)到中間狀態(tài)），找到相同的中間狀態(tài)

即可。

回朔法搜索：優(yōu)先向更深層結(jié)點(diǎn)查找，走不通則換一條路，無(wú)法換則退回

到上一層。

搜索狀態(tài)的減少：在生成搜索樹(shù)時(shí)，對(duì)于已搜過(guò)的中間狀態(tài)的再次出現(xiàn)，是否需要

再次加入到樹(shù)中重新搜索。

12.2廣度優(yōu)先搜索（bfs）

又稱寬度優(yōu)先搜索，是一種從搜索樹(shù)的根結(jié)點(diǎn)開(kāi)始，沿著樹(shù)的寬度遍歷樹(shù)的結(jié)點(diǎn)。如果所有節(jié)點(diǎn)均

被訪問(wèn)，則算法中止。一般用于求從起始狀態(tài)到目標(biāo)狀態(tài)所需的最少步驟數(shù)。

算法過(guò)程：

1、首先將根結(jié)點(diǎn)放入隊(duì)列中。

2、從隊(duì)首取出一個(gè)結(jié)點(diǎn)，按照產(chǎn)生式規(guī)則逐個(gè)生成新的結(jié)點(diǎn)數(shù)據(jù)，對(duì)新數(shù)據(jù)：

如果如果是目標(biāo)結(jié)點(diǎn)，則結(jié)束算法并返回結(jié)果。

如果不是目標(biāo)結(jié)點(diǎn)，則檢查它是否已在搜索樹(shù)中出現(xiàn)過(guò)，未出現(xiàn)就將它作為尚未檢

查過(guò)的子結(jié)點(diǎn)加入到隊(duì)列的隊(duì)尾（特殊情況下，也有已出現(xiàn)過(guò)的結(jié)點(diǎn)重新入隊(duì)的）。

3、重復(fù)步驟2。

4、若隊(duì)列為空，表示整張圖都檢查過(guò)了，即目標(biāo)無(wú)法達(dá)到，結(jié)束算法并返回“找

不到目標(biāo)”的信息。

算法細(xì)化：

1、用哈希數(shù)組判斷新生成的結(jié)點(diǎn)數(shù)據(jù)是否已出現(xiàn)過(guò)。

2、隊(duì)列經(jīng)常要多開(kāi)一行，記錄新結(jié)點(diǎn)的父親（即該結(jié)點(diǎn)由上一層的哪個(gè)結(jié)點(diǎn)擴(kuò)展而來(lái)），

用于最后輸出過(guò)程。

3、如數(shù)據(jù)規(guī)模過(guò)大，需要使用循環(huán)隊(duì)列（后果是無(wú)法記錄父親）。

算法框架：

functioncreat（i）

begin

caseiof

1：creat:=按照第一產(chǎn)生式規(guī)則生成新?tīng)顟B(tài)數(shù)據(jù)；

2:creat:=按照第二產(chǎn)生式規(guī)則生成新?tīng)顟B(tài)數(shù)據(jù)；

end;

end;

////////////////////////////////////////////////////////////////

procedurebfs;

begin

join（起始狀態(tài)）;

whilenot（隊(duì)空）do

begin

當(dāng)前處理狀態(tài):=deq;

for;=第一產(chǎn)生式規(guī)則to最大產(chǎn)生式規(guī)則do

begin

新?tīng)顟B(tài)：=creat（i）;

if新?tīng)顟B(tài)=目標(biāo)狀態(tài)then

begin

print;

exit;

end

elseifnot（haxi［新?tīng)顟B(tài)］）then

begin

join（新?tīng)顟B(tài)）；

haxi［新?tīng)顟B(tài)］:=true;

end;

end;

end;

end;

空間復(fù)雜度：線性隊(duì)列：0（最大可能狀態(tài)數(shù)）

循環(huán)隊(duì)列：0（最大可能狀態(tài)數(shù)/2）

時(shí)間復(fù)雜度：最差情形下，BFS必須尋找所有到可能結(jié)點(diǎn)的所有路徑。

0（最大可能狀態(tài)數(shù)）

完全性：廣度優(yōu)先搜索算法具有完全性。只要目標(biāo)存在，則BFS一定會(huì)找到。但是，若

目標(biāo)不存在，且問(wèn)題規(guī)模為無(wú)限大，則BFS將不收斂（不會(huì)結(jié)束）。

適用范圍：廣度優(yōu)先搜索是找到第一個(gè)解的算法，即距離根結(jié)點(diǎn)的邊數(shù)最少的解。

如果所有邊的權(quán)值都相等（即所有產(chǎn)生新?tīng)顟B(tài)的代價(jià)相同），則這個(gè)解

也是最優(yōu)解。

例一：將一個(gè)馬從M*N的棋盤的左下角跳到右上角，需要的最少步數(shù)是多少？

分析：1、用一個(gè)的數(shù)組作為工作隊(duì)列，用于存儲(chǔ)搜索樹(shù)。

2、使用m*n的二維哈希數(shù)組判重。

3、生成搜索樹(shù)的同時(shí)，記錄父節(jié)點(diǎn)的序號(hào)和新結(jié)點(diǎn)的層數(shù)。

4、最后從目標(biāo)結(jié)點(diǎn)向起始結(jié)點(diǎn)回朔，用一個(gè)棧存儲(chǔ)回朔的中間狀態(tài)。

例二：在一個(gè)2n+l的一維棋盤上，有n個(gè)黑色棋子和n個(gè)白色棋子，初始狀態(tài)如

????OOOO

規(guī)定棋子移動(dòng)規(guī)則如下：

1、如果某棋子的旁邊正好為空，這枚棋子可以移動(dòng)到空位置上。

2、如果某棋子的一側(cè)有棋子，二那枚棋子的另一側(cè)為空位置，這枚棋子可以跳過(guò)那

枚棋子到空位置上。

問(wèn)：最少經(jīng)過(guò)多少步，可以將棋盤狀態(tài)變成

OOOO

分析:?**?

1、用2n+I位三進(jìn)制數(shù)表示狀態(tài)，如初始狀態(tài)為：222201111,目標(biāo)狀態(tài)

為111102222。轉(zhuǎn)化為十進(jìn)制進(jìn)行存儲(chǔ)，另記錄空格位置。

2、產(chǎn)生式規(guī)則：將棋子移動(dòng)轉(zhuǎn)化為空格的移動(dòng)。

(1)空格向左移動(dòng)

(2)空格向右移動(dòng)

(3)空格向左跳動(dòng)

(4)空格向右跳動(dòng)

3、用一個(gè)［1..3八2n+l］的哈希數(shù)組判重。

例三：八數(shù)碼問(wèn)題。在一個(gè)3X3的九宮中有1一8這8個(gè)數(shù)及一個(gè)空格隨機(jī)的擺放在

其中的格子里，如圖1所示?，F(xiàn)在要求實(shí)現(xiàn)這個(gè)問(wèn)題：將該九宮格調(diào)整為如圖2

所示的形式。調(diào)整的規(guī)則是：每次只能將與空格(上、下、或左、右)相鄰的一

個(gè)數(shù)字平移到空格中。試編程實(shí)現(xiàn)這一問(wèn)題的求解。

分析：1、字符串表達(dá)狀態(tài)，另開(kāi)一變量w記錄空格位置。

2、空格移動(dòng)規(guī)則：

(1)向下移動(dòng)：w'=w+3。

(2)向上移動(dòng)：w5=w-3。

(3)向左移動(dòng)：w,=w-lo

(4)向右移動(dòng)：w^w+lo

3、用窮舉法判重。(將來(lái)可以用排序二叉樹(shù)判重)

12.3深度優(yōu)先搜索(dfs)

深度優(yōu)先搜索是從根結(jié)點(diǎn)出發(fā)，沿著樹(shù)的深度遍歷樹(shù)的結(jié)點(diǎn)。如果當(dāng)前新產(chǎn)生的結(jié)點(diǎn)還有以此為根

的下一層結(jié)點(diǎn)，則沿此路繼續(xù)下去，直到無(wú)法再深入訪問(wèn)時(shí)，回朔到上一層的結(jié)點(diǎn)，選另一條路繼續(xù)深

人訪問(wèn)。反復(fù)此過(guò)程，直到所有結(jié)點(diǎn)都被訪問(wèn)到為止。

算法過(guò)程:

1、首先將根結(jié)點(diǎn)放入棧中。

2、取出棧頂結(jié)點(diǎn)，按照產(chǎn)生式規(guī)則生成新的結(jié)點(diǎn)數(shù)據(jù)，每產(chǎn)生一個(gè)：

檢查是否是目標(biāo)結(jié)點(diǎn)，如果是且比保存的數(shù)據(jù)更優(yōu)，刷新所保存的數(shù)據(jù)。

檢查該結(jié)點(diǎn)是否已搜過(guò)，如果是且比已保存的數(shù)據(jù)更優(yōu)，則刷新所保存的數(shù)據(jù)，然后

該結(jié)點(diǎn)進(jìn)棧；如沒(méi)有搜過(guò)，則保存數(shù)據(jù)并進(jìn)棧。

3、轉(zhuǎn)第二步。

4、如果棧空，則算法結(jié)束。

細(xì)化說(shuō)明：

1、一般用回朔法，利用遞歸使用系統(tǒng)棧。

2、哈希數(shù)組不僅用于判斷新結(jié)點(diǎn)是否出現(xiàn)過(guò)，還用于保存到達(dá)該結(jié)點(diǎn)時(shí)的中間數(shù)據(jù)。

算法框架：

proceduredfs（結(jié)點(diǎn)數(shù)據(jù)）；

vari:integer;

begin

fori:=產(chǎn)生式規(guī)則一to最大產(chǎn)生式規(guī)則do

begin

新結(jié)點(diǎn)數(shù)據(jù):=creaKi）;

if（新結(jié)點(diǎn)數(shù)據(jù)沒(méi)有搜到過(guò)）or（新結(jié)點(diǎn)數(shù)據(jù)雖已搜過(guò)但本次搜索結(jié)果更優(yōu)）

then

begin

更新新結(jié)點(diǎn)搜索結(jié)果；

dfs（新結(jié)點(diǎn)數(shù)據(jù)）；

end;

end;

proceduredfs（結(jié)點(diǎn)數(shù)據(jù)）；

vari:longint;

begin

fori:=Ito最大產(chǎn)生式規(guī)則do

begin

新結(jié)點(diǎn):=creat⑴；

if新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then

begin

傳回新結(jié)點(diǎn)；

t:=true;

exit;

end;

if新結(jié)點(diǎn)更優(yōu)then

begin

更新新結(jié)點(diǎn)數(shù)據(jù);

dfs（新結(jié)點(diǎn)）；

iftthenexit;

end;

end;

end;

空間復(fù)雜度：0（最大狀態(tài)數(shù)）（主要用于存儲(chǔ)各結(jié)點(diǎn)搜索結(jié)果）

時(shí)間復(fù)雜度：0（最大產(chǎn)生式規(guī)則數(shù)人最大狀態(tài)數(shù)）

深度優(yōu)先搜索的理論依據(jù)是建立在窮舉基礎(chǔ)上的，所以時(shí)間是幾何級(jí)數(shù)級(jí)的，其優(yōu)化

剪枝是非常必要的，因此，深搜的主要算法設(shè)計(jì)是在于如何剪枝，如何既高效地拋棄

不必要的子樹(shù)，又不至于將最優(yōu)解剪掉，將是深搜的最大難點(diǎn)。

適用范圍：在缺乏有效的數(shù)學(xué)方法、遞推算法，不符合動(dòng)態(tài)規(guī)劃要求，也沒(méi)有專用算法

可以應(yīng)對(duì)，一般考慮使用深搜；得分情況將取決于優(yōu)化剪枝的技巧（30-100

分）。

例一：有A、B、C、D、E5本書(shū)，要分給張、王、劉、趙、錢5位同學(xué)，每人只能選1本。每個(gè)

人都將自己喜愛(ài)的書(shū)填寫(xiě)在下表中。請(qǐng)你設(shè)計(jì)一個(gè)程序，打印出讓每個(gè)人都滿意的所有分書(shū)

方案。

111\??

|AIBICD|E|

111

張i11111

111V1VI|00110

1111

111

王iJ11

1|V|1|V111001

1111_1_______1

劉i11111

1|V|V1||01100

111_1________1

趙i11111

1111V||00010

111_1________1

錢it1111

1|V|1|V101001

1111111

分析：

1、樸素的窮舉法：產(chǎn)生5本書(shū)的所有全排列，共有5!=120個(gè),逐個(gè)檢查各種排列是否

符合所有人的要求，符合則輸出，否則丟棄。

窮舉法的改進(jìn)：例如產(chǎn)生一個(gè)全排列12345時(shí)，第一個(gè)數(shù)1表示將第一本書(shū)給小張。

但從表中可以看出，這是不可能的，因?yàn)樾堉幌矚g第三、第四本書(shū)。也就是說(shuō)，1

XXXX這一類分法是不符合條件的。由此使我們想到，如果選定第一本書(shū)后，就立

即檢查一下是否符合條件，當(dāng)發(fā)現(xiàn)第一個(gè)數(shù)的選擇不符合條件時(shí)，就不必再產(chǎn)生后面

的4個(gè)數(shù)了，這樣做可以減少很多的運(yùn)算量。換句話說(shuō)，第一個(gè)數(shù)只在3和4中選擇,

這樣就可以減少3/5的運(yùn)算量。同理，在選定了第一個(gè)數(shù)后，其他4個(gè)數(shù)字的選擇

也可以用類似的方法處理，即選擇第二個(gè)數(shù)后，立即檢查是否符合條件。例如，第一

個(gè)數(shù)選3,第二個(gè)數(shù)選4后，立即進(jìn)行檢查，發(fā)現(xiàn)不符合條件，就另選第二個(gè)數(shù)。這

樣就又把34XXX一類的分法刪去了，從而又減少了一部分運(yùn)算量。

3、

建立如上搜索樹(shù)，每一層分發(fā)一本書(shū)，未向下擴(kuò)展的結(jié)點(diǎn)為當(dāng)前層已不合理，故剪去。

參考程序：

programdfs1;

consta:array[1..5,1..5]ofboolean=((false,false,true,true,false),

(true,true,false,false,true),

(false,true,true,false,false),

(false,false,false,true,false),

(false,true,false,false,true));

varoutf:text;

c:arrayl1..5Jofinteger;

hx:array[1..5]ofboolean;

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH

procedureprint;

vari:integer;

begin

fori:=lto5do

casec[i]of

l:write(outf,‘張')；

2:write(outf/3E');

3:write(outf,墳『)；

4:write(outf,‘趙')；

5:write（outf,'錢'）;

end;

end;

〃/〃〃〃〃//〃/〃/〃////〃//〃〃//〃〃〃〃/〃/////〃/〃/〃/〃〃/

proceduredfs(n:integer);

vari:integer;

begin

fori:=lto5do

if(a[i,n])and(not(hx[i]))then

begin

c[n]:=i;

ifn=5thenprint;

hx[i]:=true;

dfs(n+l);

hxlij:=false;

end;

end;

〃〃〃〃///〃〃/〃〃///〃〃〃〃〃///〃/〃〃〃///〃///〃〃////〃〃

begin

assign^utf/dfs-l.out);rewrite(outf)；

dfs(l);

close(outf);

end.

例二：跳馬問(wèn)題:在半張中國(guó)象棋盤上(5*9),有一匹馬自左下角往右上角跳，今規(guī)定只許往右

跳，不許往左跳。編程計(jì)算共有多少種不同的跳行路線，并將路線打印出來(lái)。

例三：01000

01010

00000

OHIO

00010

表示一個(gè)迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著

走，要求編程序找出從左上角到右下角的路線。

例四：有一個(gè)m*n的滑雪場(chǎng)，請(qǐng)找出最長(zhǎng)的滑雪道。

比如：244020302844

333520183040

403522151320

303525201218

284030101120

153012152012

從第一排開(kāi)始下滑，只能向上、下、左、右四個(gè)方向，且下一個(gè)區(qū)域的高度必須低于當(dāng)前

區(qū)域的高度，找出一條滑動(dòng)距離最長(zhǎng)的路徑，可以在任何區(qū)域停止。

12.4習(xí)題:

1、營(yíng)求(save)

【問(wèn)題描述】鐵達(dá)尼號(hào)發(fā)出了求救信號(hào)。距離最近的哥倫比亞號(hào)收到了信號(hào)，必須盡快趕到那

里。通過(guò)偵測(cè)，哥倫比亞號(hào)獲取了一張海洋圖。這張圖將海洋部分分化成nXn個(gè)比較小的單位,

其中用1標(biāo)明的是陸地，用。標(biāo)明的是海洋。船只能從一個(gè)格子移到相鄰的四個(gè)格子。為了盡

快趕到出事地點(diǎn)，哥倫比亞號(hào)最少需要走多遠(yuǎn)的距離。

【輸入格式】第一行為n,下面是一個(gè)nXn的0,1矩陣，表示海洋地圖。最后一行為四個(gè)小

于等于n的整數(shù)，分別表示哥倫比亞和鐵達(dá)尼號(hào)的位置。

【輸出格式】哥倫比亞號(hào)到達(dá)鐵達(dá)尼號(hào)的最短距離，答案精確到整數(shù)。

【輸入樣例】save,in

3

001

101

100

1133

【輸出樣例】save,out

4

【數(shù)據(jù)范圍［n<=1000

2^硬幣翻轉(zhuǎn)（coin）

【問(wèn)題描述】在桌面上有一排硬幣，共n枚，每一枚硬幣均為正面向上?，F(xiàn)在要把所有的硬幣

翻轉(zhuǎn)成反面向上，規(guī)則是每次可翻轉(zhuǎn)任意n—1枚硬幣（正面向上的翻轉(zhuǎn)成向下，向下的翻轉(zhuǎn)成

向上）。求一個(gè)最短的操作序列（將每次翻轉(zhuǎn)n—1枚硬幣定為一次操作）。

【輸入格式】只有一行，包含一個(gè)自然數(shù)n（n為不大于100的偶數(shù)）

【輸出格式】第一行包含一個(gè)整數(shù)s,表示最少需要的操作次數(shù)。接下來(lái)s行每行分別表示每

次操作后桌上硬幣的狀態(tài)（一行包含n個(gè)整數(shù)（0或1）,表示每個(gè)硬幣的狀態(tài)，0正面向上，

1反面向上，不允許出現(xiàn)多余的空格）。對(duì)于有多種操作方案的情況，則只需輸出一種。

【輸入樣例】coin,in

4

【輸出樣例】coin,out

4

0111

1100

0000010010

0010001010

0101010010

0100110110

0010000100

0001111100

0000000000

【輸出樣例】area.out

15

4、細(xì)胞(cell)

【問(wèn)題描述】一矩形陣列由數(shù)字0?9組成，數(shù)字廣9代表細(xì)胞，細(xì)胞的定義是沿細(xì)胞數(shù)字上下

左右如果還是細(xì)胞數(shù)字則為同一細(xì)胞，求給定矩形陣列的細(xì)胞個(gè)數(shù)。

如陣列：

0234500067

1034560500

2045600671

0000000089

有4個(gè)細(xì)胞。

【輸入格式】第一行為整數(shù)mn,接著m行，每行n個(gè)數(shù)字

【輸出格式】細(xì)胞的個(gè)數(shù)

【輸入樣例】cell,in

410

0234500067

1034560500

2045600671

0000000089

【輸出樣例】cell,out

4

5、最少轉(zhuǎn)彎問(wèn)題(turn)

【問(wèn)題描述】給出一張地圖，這張地圖被分為nXm(n,水=100)個(gè)方塊，任何一個(gè)方塊不是

平地就是高山。平地可以通過(guò)，高山則不能?，F(xiàn)在你處在地圖(xl,yl)這塊平地，問(wèn)：你至

少需要拐幾個(gè)彎才能到達(dá)目的地(x2,y2)?你只能沿著水平和垂直方向的平地上行進(jìn)，拐彎

次數(shù)就等于行進(jìn)方向的改變(從水平到垂直從垂直到水平)次數(shù)。如右圖，最少拐彎5次。

【輸入格式】第一行nm

第2到n+1行：整個(gè)地圖的描述(0：平地，1：高山)。

1000010

第n+2行：xlylx2y2

【輸出格式】S

【輸入輸出樣例】

Turn,inTurn,out

575

1000010

0010100

0000101

0110000

0000110

1317

6、騎士周游世界。在國(guó)際象棋的棋盤上，有一位騎士按照國(guó)際象棋中馬的行走規(guī)則從棋盤上的某

一方格出發(fā)，開(kāi)始在棋盤上周游。若能不重復(fù)地走遍棋盤上的每一個(gè)方格，這樣的一條周游路線在

數(shù)學(xué)上被稱之為國(guó)際象棋盤上馬的哈密爾頓鏈。請(qǐng)你設(shè)計(jì)一個(gè)程序，對(duì)于從鍵盤輸入的任意一個(gè)起

始方格的坐標(biāo)，由計(jì)算機(jī)自動(dòng)尋找并按如下格式打印出國(guó)際象棋盤上馬的哈密爾頓鏈。例如，當(dāng)馬

從坐標(biāo)點(diǎn)(5,8)出發(fā)時(shí)，相應(yīng)的哈密爾頓鏈如下圖所示：

11??

60|11262954|1324|21|

1111

1111

27|30|611225I22|5114

11

1111

10|59|285550|53|20|23|

1111

111

3161|57624348|1552

11111

1111

58|932|4956|19|42|11

11111

11111

33|663|4447|36|39|16I

1I111

111411|1

8|45|4I35|181237|

I111

1111

5|34|7I46|3|38|17|40|

?????

7、有兩個(gè)無(wú)刻度的量杯A和B,其容積分別為m升和n升(m>n),現(xiàn)在允許用量杯從水缸里取水或?qū)⑺?/p>

倒回水缸里，而且兩個(gè)量杯中的水也可以相互傾倒，試設(shè)計(jì)計(jì)算機(jī)程序求出在m升的量杯中準(zhǔn)確量

得k