信息學（計算機）奧林匹克訓練題 （中級部分）

中級訓練題

信息學（計算機）奧林匹克訓練題（中級部分）

天津師范大學李學武編1997.7.

1.給定等式ABCDE其中每個字母代表一個數(shù)字，且不同數(shù)字對應不

DFG同字母。編程求出這些數(shù)字并且打出這個數(shù)字的

+DFG算術(shù)計算豎式。

XYZDE

2.A、B、C、D、E五名學生有可能參加計算機競賽，根據(jù)下列條件判斷哪些人參加

了競賽：

（1）A參加時，B也參加；

（2）B和C只有一個人參加；

（3）C和D或者都參加，或者都不參加；

（4）D和E中至少有一個人參加；

（5）如果E參加，那么A和D也都參加。

3.打印一個N*N的方陣，N為每邊N=15打印出下面圖形

字符的個數(shù)（3<N<20）,要求最

外一層為“r,第二層為"J”,從第三層TJJJJJJJJJJJJJT

起每層依次打印數(shù)字1,2,3,...TJ11111111U1JT

（右圖以N為15為例）TJ12222222221JT

TJ12333333321JT

TJ12344444321JT

TJ12345554321JT

TJ12345654321JT

TJ12345554321JT

TJ12344444321JT

TJ12333333321JT

TJ12222222221JT

TJ11111111111JT

TJJJJJJJJJJJJJT

4.在N行N列的數(shù)陣中，數(shù)K（1〈=K〈=N）在每行和每列中出現(xiàn)且僅出現(xiàn)一次，

這樣的數(shù)陣叫N階拉丁方陣。例如下圖就是一個五階拉丁方陣。編一程序，從鍵盤輸入N值

后，打印出所有不同的N階拉丁方陣，并統(tǒng)計個數(shù)。

12345

23451

34512

45123

51234

-1-

中級訓練題

5.輸入?個十進數(shù)，將其轉(zhuǎn)換成N進制數(shù)(0<N<=16)o

N*N的矩陣，要求用程序填入下列形式的數(shù):

②蛇形填數(shù)③回轉(zhuǎn)填數(shù)

1???????????

11|3|4|10|11||1|16|15|14|13|

1I11|1I1I1I

1111n111111

|2|5|9|12|19||2|17|24|23|12|

1I1___I1I1III

11111111111

|6|8|13|18|20||3|18|25|22|11|

1|11I1I1I1I

111111111

|7|14|17|21|24||4|19|20|21|10|

1I11I1I1I

1111n111111

|15|16|22|23|25||5|6|7|8|9|

????????????

7.讀入一行文本，包含若干個單詞(以空格間隔，％結(jié)尾)。將其中以A開頭的單詞與

以N結(jié)尾的單詞，用頭尾交換的辦法予以置換。

8.輸入兩個正整數(shù)X,Y,將X,Y化為二進制數(shù)，然后將這兩個二進制數(shù)作二進制加

法運算，再將結(jié)果化為十進制數(shù)輸出。

9.四人玩火柴棍游戲，每一次都是三個人贏，一個人輸。輸?shù)娜艘蹿A者手中的火柴數(shù)

進行賠償，即贏者手中有多少根火柴棍，輸者就賠償多少根?，F(xiàn)知道玩過四次后，每人恰好

輸過一次，而且每人手中都正好有16根火柴。問此四人做游戲前手中各有多少根火柴？編

程解決此問題。

10.如圖1所示，編寫程序計算

IIIIIIIIIII

大大小小正方形共有多少？當最小IIIIIIIIIII

IIIIIIIIIII

正方行邊長為1時，它們的總面積IIIIIIIIIII

共為多少？IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

11.巧排數(shù)字。將1、2......20這20個數(shù)排成一排，使得相鄰的兩個數(shù)之和為一個

素數(shù)，且首尾兩數(shù)字之和也為一個素數(shù)。編程打印出所有的排法。

12.下圖是一個集裝箱倉庫，陰影部分表示有集裝箱存放不能通過，無陰影處為臨時通道。

-2-

中級訓練題

13.有N個硬幣（N為偶數(shù)）正面朝上排成一排，每次將N-1個硬幣翻過來放在原位置，

不斷地重復上述過程，直到最后全部硬幣翻成反面朝上為止。編程讓計算機把翻幣的最簡過

程及翻幣次數(shù)打印出來（用*代表正面，0代表反面）。

14.有黑白棋子各有N個（分別用*和。代替），按下圖方式排列

***…***000…000

N個黑棋N個白棋

允許將相鄰兩個棋子互換位置，最后使隊形成黑白交替排列，試編程實現(xiàn)該操作。

15.已知6個城市，用c[i,j]表示從i城市到城市j是否有單向的直達汽車

（1=<i〈=6,1〈=j〈=6）,c[i,j]=l表示城市i到城市j有單向直達汽車；否

則c[i,j]=0.試編制程序，對于給出的城市代號i,打印出從該城市出發(fā)乘車（包括轉(zhuǎn)

車）可以到達的所有城市。

16.設有8枚硬幣a,b,c,d,e,f,g,h,其中有一枚硬幣是偽造的。真?zhèn)斡?/p>

幣的區(qū)別僅是重量不同，可能重，可能輕。今要求以天平為工具，用最少的比較次數(shù)挑出偽

造硬幣，并鑒定它是重還是輕。

17.編寫一個程序，當輸入不超過60個字符組成的英文文字時，計算機將這個句子中的

字母按英文字典字母順序重新排列,排列后的單詞的長度要與原始句子中的長度相同。例如：

輸入：

THEPRICE0FBREADIS￥125PERPOUND

輸出：

ABCDDEEEEFHIINO0P￥125PPRRRSTU

并且要求只對A到Z的字母重新排列，其它字符保持原來的狀態(tài)。

18.在一線性七個格位置的圖上有兩種不同顏色的棋子A,B.排列如下圖所示，中間格

的位置為空。

-3-

中級訓練題

IA|A|A|IB|B|B|

要求將A,B的現(xiàn)行位置交換,形成卜圖中的排列:

IB|B|B||A|A|A|

移動棋子的條件：

(1)每個格中只準放一個棋子。

(2)任意一個棋子均可移動一格放入空格內(nèi)。

(3)一方的棋子均可跳過另一方的一個棋子進入空格。

(4)任何棋子不得跳躍兩個或兩個以上棋子(無論顏色同異)

(5)任何一個顏色棋子只能向前跳，不準向后跳。

編程完成有關(guān)的移動，并且完成具有2N+1個格子的情形.其中兩種顏色各有N個棋子,

且中間為空格.

19.(背包問題)有N件物品dl.....dN,每件物品重量為W1,WN(Wi>0),每

件物品價值為VI.......VN(Vi>0)?用這N件物品的某個子集填空背包，使得所取物品的

總重量CTOTAL,并設法使得背包中物品的價值盡可能高。

20.(N皇后)在國際象棋的棋盤上放置N個皇后，使其不能互相攻擊，即任意兩個皇后不

能處在棋盤的同一行，同一列，同一斜線上，試問共有多少種擺法？

21.請設計一個程序，由計算機把I..18的八個自然數(shù)填入圖中，使得橫、豎、對角任

何兩個相鄰的小方格中的兩個數(shù)是不連續(xù)的。(下圖右側(cè)的4個圖為禁止的情形).

4II8|

I5||7|

6I|-------------1-1

TI1I2|

7|??~~?

22.在??個4*4的小方格(如圖所示)中放置8個*號，使得每行每列放且僅放兩個*

號。

I*II*I

-4-

中級訓練題

1*1*1

求出所有的基本解。

23.（覆蓋問題）有邊長為N（N為偶數(shù)）的正方形，請你用N-2/2個長為2,寬為1

的長方形，將它全部覆蓋。編程打印出所有覆蓋方法。如：N=4

1111111

11111224|||1122

11______11I______I_____I

1111111

11111334|||3344

11______11I______I_____I

1111111

||||5668|||5566

1I______II

1111111

||||5778|||7788

???????

24.某地街道把城市分割成矩形方格，每一方格叫作塊，某人從家中出發(fā)上班，向東要走

M塊，向北要走N塊，（見圖）。請設計個程序，由計算機尋找并打印出所有的上班的路徑。

單位

25.（量水）用存水為M,N升的兩個罐子，量出A升水。

26.（八數(shù)碼問題）8個編有數(shù)碼1-8的滑牌，能在3*3的井字格中滑動。井字格中有

一格是空格，用0表示，因而空格周圍的數(shù)碼滑牌都可能滑到空格中去.

下圖是數(shù)碼滑牌在井字格中的兩種狀態(tài)：

??11

|1|213|

11I

111

|8|014|

11I

111

|7|615|

-5-

中級訓練題

初始狀態(tài)目標狀態(tài)

以左圖為初始狀態(tài)，右圖為目標狀態(tài)，請找出從初始狀態(tài)到目標狀態(tài)的滑牌移步序列，具

體要求：

(1)輸入初始狀態(tài)和目標狀態(tài)的數(shù)據(jù)；

a、分別用兩行輸入上述兩項數(shù)據(jù)：

例：Entertheinitialstate:283164705

Enterthefinalstate:123804765

b、對輸入數(shù)據(jù)應有查錯和示錯功能；

(2)實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)換(如不能實現(xiàn)，程序應輸出不能實現(xiàn)的提示信

息)；

(3)輸出結(jié)果，每移動一步都必須在屏幕上顯示：

a、移動每一步時的序號，最后一步的序號即為移動總步數(shù)：

b、每一步移動后以3*3表格形式顯示狀態(tài)。

(4)要求能使移動步數(shù)盡可能少；

27.給出一個有8個格子的表格，除3個格子外，每個格子中可放入一個數(shù)字，這些數(shù)字

取自自然數(shù)1到5,放入格子中的數(shù)字不得相同，剩余的3個格子是空格(用。表示)。圖

1是?個放數(shù)字與空格的特例?，F(xiàn)要求編程實現(xiàn)從初始表格狀態(tài)變化到目標表格狀態(tài)。初始

狀態(tài)和目標狀態(tài)都是可變的(圖1，圖2所示的狀態(tài)僅是一個特例)，山鍵盤輸入格子中的

數(shù)字(0-5)o

移動規(guī)則：

(1)每一個數(shù)字只可以通過虛線移入相鄰空格。如圖1中，允許“2”左移入空格，而

不能上移進入上面空格。

(2)只允許水平移動或垂直移動，不允許斜移。

(3)移動后，該數(shù)字原先所在的格子變成空格。

實現(xiàn)目標：

(1)輸入初始表格狀態(tài)和目標表格狀態(tài)的數(shù)據(jù)。

①分別在一行內(nèi)輸入上述兩項數(shù)據(jù)；

②對輸入的數(shù)據(jù)應有查錯和報錯功能；

(2)實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)換(如不能實現(xiàn)也應給出必要的說明)。

(3)顯示結(jié)果：每移動?步都應在屏幕上有如下信息：

①顯示每一步移動的序號。所以最后一步的序號就是移動的總步數(shù)。

②顯示每一步移動前后的表格狀態(tài)。

(4)以最少的移動步數(shù)達到目標。

I3|4|0|I0I0I0|

|01025I|12345I

圖10—1圖10—2

初始狀態(tài)A目標狀態(tài)B

-6-

中級訓練題

28.n枚銀幣C1,C2.....Cn,其中有一塊不合格，不合格的銀幣比正常的要重?，F(xiàn)用一天

平找出不合格的一塊，要求在最壞的情況下，用的天平次數(shù)最少。

29.把一段文章按要求排版。文章的輸入方式為：由鍵盤輸入一段以回車符結(jié)束的文章（最

大長度2000個字符）。排版時以單詞為基本單位。單詞由不含空格的任意字符組成，是長

度小于20個字符的串?？崭穹欠指魡卧~的唯一字符，在輸入時連續(xù)的空格符在處理時應

先化簡為單個空格符。在排版前應先輸入，排版后每行的字符數(shù)為N,排版后將整理好的文

章按行輸出。輸出時不能將一個完整的單詞截斷，并要求輸出的總行數(shù)最小。將每個不足N

個字符的行用空格補足，填充空格符的方式有以下三種。

1）將填充的空格符置于每行的末尾，并要求每行的起始為單詞。

2）將填充的空格符置于每行的開始，并要求每行的末尾為單詞。

3）將填充的空格符平均分配在每行中，并保證行的起始和末尾均為單詞。

30.某機要部門安裝了電子鎖。M個工作人員每人發(fā)一張磁卡，卡上有開鎖的密碼特征。

為了確保安全，規(guī)定至少要有N個人同時使用各自的磁卡才能將鎖打開。問電子鎖上至少要

有多少種特征？每個人的磁卡上至少要有多少特征？如果特征的編號以小寫英文字母表示，

將每個人的磁卡的特征編號打印出來，要求輸出的電子鎖

的總特征數(shù)最少。

設3〈=M<=7,1<=N<=4,M與N由鍵盤輸入，工作人員編號用表示.

31.甲乙兩人從24枚棋子中輪流取子，甲先取，規(guī)定每次所取的枚數(shù)不能多于上

一個人所取的枚數(shù)，也不可不取。

（1）甲第一次取多少枚才能保證中取得最后一枚，當然，他也不能第一次就把

所有棋子都取走。

（2）討論棋子總數(shù)N（一定是偶數(shù)）從6到30的各種情況。討論內(nèi)容包括：

對各個N,是否存在一個小于N的枚數(shù)M,甲第一次取M枚后就能保證甲如果策略

正確,一定能取到最后一枚棋子。

32.（走棋）一個4*4的方陣如圖。有一個小卒從上往下走。走至格子1后就

不能走動，走至0后，若下方為1,則向左或向右走，下方為0,則向下走。求所

有走法。

11111

1110|0|0|

11111

11111

|01011|0|

11111

11111

|0|1|0|0|

11111

11111

1110|0|0|

11111

33.（野人與傳教士）設有三個傳教士和三個野人來到河邊，打算乘一只船從右

岸渡到左岸去。該船最大負載能力為兩人，在任何時候，如果野人人數(shù)超過傳教士

-7-

中級訓練題

人數(shù)，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡過

河去呢？

34.(取棋子)設有N顆棋子，由人和計算機輪流從中取走若干顆。每方每次最

多取K顆，最少取1顆(K值不能超過總數(shù)的一半，也不能小于1)。試編寫一程

序使計算機有較多的獲勝機會。

屏幕輸入提示：

(1)輸入競賽規(guī)則：A.取最后一顆棋子的那一方為敗.

B.取最后一顆棋子的那?方為勝.

(2)總共有多少顆棋子？

(3)一次最多取幾顆？

(4)誰先取？

(5)每個回合都應顯示：A.你取兒顆？

B.我取走.....顆，還剩......顆.

(6)競賽過程中發(fā)生違例時，打印出：競賽無法進行下去！

(7)競賽結(jié)束后打印：

Iwin!(我勝！)或Youwin!(你勝！)。

35.(Grundy博弈)在兩位選手面前放著一堆銅幣。第一位選手把原堆分成不相

等的兩堆。然后每個選手輪流地這樣做，即當輪到某一方分時，他把已被分開的任

一堆再分成不相等的兩堆。博弈這樣一直進行下去，直到每一堆都只剩下一個或兩

個銅幣為止，這時博弈結(jié)束。規(guī)定首先遇到這種情況的選手為輸。

36.猴子選大王：

①N只猴子站成一行，每隔M只從頭到尾報數(shù)，反復進行，報過數(shù)的退出，打

印每次退出的猴子的編號,直到剩下一只為止。

②N只猴子站成一行，每M只報數(shù)。先從頭到尾，報到尾后，再返回從尾到頭

報數(shù)，打印每次方向及過程，直到剩下二只時，以排到后面的(指報數(shù)方向)為大王.

③N只猴子圍成一圈，從第P個開始，每隔M只報數(shù)，打印每次過程，只剩下

一個時為大王。

37.已知N個正整數(shù)滿足K1+K2+...+Kn=M?求一組最佳的分解，使得

K1*K2*....*Kn為最大。

例如:N=2時,給定Kl+K2=6,當Kl=3,K2=3時,K1*K2=9為最大

38.有一集合中有N個元素，每個元素均為自然數(shù)。給定一個total(假設每個

元素值均小于total),求滿足條件的所有子集，子集中各元素之和應等于total。

39.一個集合滿足如下條件：

(1)1是集合的元素；

(2)若P是集合的元素，則2*P+1,4*P+5也是集合的元素。

求：此集合中最小的K個元素。

③對ABC作全排列而得的六個三位數(shù)之和為2886。

-8-

中級訓練題

40.一個整型變量只能用來存貯較小的N!的值，當N較大時，可將階乘值中的

每一個數(shù)字放在一個一維數(shù)組的一個元素中。使用這方法，打印：

①N!的值；

②N!-M!(M>N)；

③N!+M!

41.(合并鏈表)已知兩個鏈表AN={al,a2,...an},BN={bl,b2,...bm),將其合并

為一個鏈表CN={al,bl,a2,b2,...}

42.(算術(shù)表達式求值)輸入一個由數(shù)字、+,*，/及括號組成的算術(shù)表達式，

求其值。

43.對于次數(shù)很高，但項目很少的多項式，可用鏈表來表示。

例如：X"1000-76*X'76+3*X'3-7可表示為

|1|1000|十一|-76|78|+一|3|3|十-|-7|0|NIL|

在此方式下，編程完成兩個多項式的加法與乘法。

44.(一元多項式加法)實現(xiàn)兩個整系數(shù)一元多項式的加法。例如，對于多項式

5*X-6+4*X"3-7*X"4+1與多項式50*X-2+4*X,運算結(jié)果為：

5*X*6-7*X*4+4*X-3+50*X-2+4*X+1。

程序要求：鍵盤輸入多項式的各項系數(shù)及指數(shù)，每項系數(shù)及指數(shù)為?組數(shù)據(jù)(系

數(shù)及指數(shù)之一可為零)，以'0,0'結(jié)束一個多項式的輸入，結(jié)果按降幕排列，同類

項要合并(指數(shù)最大不超過30)。

上例第一式的輸入為：5,6

4,3

-7,4

1,0

0,0

輸出結(jié)果應為：5*x*6-7*x*4+4*x*3+50*x-2+4*x+l.

45.(數(shù)列的最小代價)給定一個正整數(shù)序列，例如：4,1,2,3,不改變數(shù)的位置把

它們相加，并且由括號來標記每一次加法所得到的和。例如：((4+1)+(2+3))=

((5)+(5))=10.除去原數(shù)4、1、2、3之外,其余都為中間結(jié)果，如:5,5,10,將中

間結(jié)果相加，得到：5+5+10=20,數(shù)20稱為此數(shù)列的一個代價。對于另一種算法：

(4+((1+2)+3))=(4+((3+3))=(4+(6))=10,得到數(shù)列的另一個代價為：3+6+10=19.

若給出N個數(shù)的數(shù)列，求出此數(shù)列的最小代價。

46.設有一個字符串，長度小于100,且全部以英文字母組成。對字串中的每個字

母可用0,1,2三個數(shù)字進行編碼，且數(shù)字可以重復使用。

程序要求：(1)輸入字符串，并能判斷輸入是否有錯；

-9-

中級訓練題

(2)輸出對應的編碼表及碼長，要求字串的編碼總長度為最短;

(3)根據(jù)上述編碼表，給出一些編碼，然后求出其原字符串。

例如：輸入的字符為：ABCBAAADDEF

其對應的編碼表為：

A:2B:10

C:11D:12

E:00F:01

對應的編碼為:210111022212120001總碼長為：18

根據(jù)該編碼，給出編碼:010001121110222則輸出字串：FEFDCBAAAA.

47.某些密碼山N個英文字母組成(N<26),每個字母的平均使用率為:町”2,...

,Wn,要求編程完成下列任務：

①鍵入英文字母及個數(shù)；

②鍵入N個英文字母的使用頻率；

③用二進制數(shù)對該N個英文字母進行編碼(最短，無二義性)；

④鍵入字母短文(單詞用空格區(qū)分)，輸出相應編碼：

⑤鍵入二進制編碼短文，輸出譯文。

48.將4個紅球，3個白球與3個黃球排成一排，共有多少種排法？

49.有面值為M..N的郵票各一枚，共能拼出多少不同的面額。

50.有一個四階方陣，隨機產(chǎn)生1..16這16個自然數(shù)(不重復)，依次填入每

個方格中。要求用最少的對調(diào)次數(shù)，使每?行、每一列以及對角線上的四個數(shù)之和

均相等。打印每一次對調(diào)的過程。

51.微型藍球賽.甲，乙兩隊進行藍球比賽，結(jié)果甲隊以S:T獲勝.(T<S<=10,S.T

由鍵盤輸入).比賽中，甲隊得分始終領(lǐng)先(嚴格大于乙隊).規(guī)定以任何方式進一

球都只得一分.編程序打印該比賽的每一種可能的不同的得分過程，以及所有不同

過程的總數(shù).

52.求兩整型數(shù)組錯位相加的最大面積.

設整型數(shù)組C具有N個分量：C=(C1,C2....CN),兩相連分量

可計算一個面積:若同號,則面積SI=abs(C[l]+C[I+l])/2,否則，面

積等于(abs(a*C[I])+abs(b*C[1+1]))/2,其中，a>0,b>0,a+b=l(詳見下圖)，數(shù)

組C的面積A=S[l]+S[2]+...+S[N-l].

編程要求如下：

從鍵盤輸入N,再輸入兩個具有N個分量的數(shù)組：A1,A2：ARRAY[1..N]OF

INTEGER;將A1,A2錯位相加(詳見后面的例子)得數(shù)組A3,求A3的面積.編程給

出一個錯位相加的方案，使A3的面積最大.

例：設N=3,Al=(3,7,2),A2=(-5,7,-4),則應考慮9種情況：

(1)(2)

A1372372

-10-

中級訓練題

A2-57-4-57-4

A33720-57-4372-57-4

(3)(9)

A1372372

A2-57-4-57-4

A337-37-4-57-40372

53.（工作安排問題）現(xiàn)有N（NW8）件工作，分別由N個人完成，每人都完成一

件,且只完成一件，每人完成不同工作的時間不同.試設計一種分配工作方案，使

完成N件工作所需的總時間最少.

原始數(shù)據(jù)由文本文件EXAMI.TXT給出，其格式如下：

第1行：工作任務數(shù)（N）

第2—N+1行：第i+1行為第i個人完成各件工作所需的時間.以上各數(shù)

均為不超過1000的正整數(shù).

計算結(jié)果可直接在屏幕上輸出：第一行為工作分配方案，共N組，每組數(shù)據(jù)的

形式為a-b,其中a為工作人員編號，b為他應完成的工作序號.

例：設EXAMI.TXT的數(shù)據(jù)為:

4

215134

1041415

9141613

78119

對此，一個正確的輸出可以是

1-4,2-2,3~1,4-3

T0TAL=28

54.求N個字符串的最長公共子串，N<=20,字符串長度不超過255。

例如：N=3,由鍵盤依次輸入三個字符串為

Whatislocalbus?

Namesomelocalbuses.

localbusisahighspeedI/Obusclosetotheprocesser.

則最長公共子串為"localbus”。

（參看程序9）

55.（液晶顯示）下圖是用液晶七筆阿拉數(shù)字表示的十個數(shù)字，我們把橫和豎的一

個短劃都稱為一筆，即7有3筆，8有7筆等。請把這十個數(shù)字重新排列，要做到

兩相鄰數(shù)字都可以由另一個數(shù)字加上幾筆或減去幾筆組成，但不能又加又減。比如

7-3是允許的，7f2不允許。編程打印出所有可能的排列。

如：4107395682。

56.（N階梵塔）有K根棒，第一根上放N片大小不等的圓盤，并保持上小下大的

順序?，F(xiàn)將N片圓盤從第1根移至第K根，移動中均保持上小下大的順序，問最少

移幾次方得結(jié)果，求出移動方案。

-11-

中級訓練題

(參看程序3)

57.某一印刷廠有六項加工任務，對印刷車間和裝訂車間所需時間見下表(時間單

位：天)

任務|J1J2J3J4J5J6

印刷車間|31252911

裝訂車間|8109631

如何安排加工順序，使加工時間最少。

58.將7萬元投資到A,B,C三項目上，其利潤見下表：

投資額(萬元)|1234567

項A|0.110.130.150.240.240.300.35

B|0.120.160.210.250.250.290.34

目C|0.080.120.200.260.260.300.35

如何分配投資額，使獲得的利潤最大。

59.無根樹與通常所說的樹(有根樹)很相似，它包含有節(jié)點和枝，但不含有根。

無根樹節(jié)點之間只有相鄰關(guān)系。如圖一所示，是一棵有七個節(jié)點的無根樹，以圖一

的A為根節(jié)點得到圖二所示的有根樹，以B為根節(jié)點得到圖三所示的有根樹，但從

無根樹的角度看，圖-、二、三是結(jié)構(gòu)相同的無根樹，同時無根樹的結(jié)構(gòu)與節(jié)點的

名稱無關(guān)。

有根樹可以用字符串的形式表示，其遞歸表示方法是：

根節(jié)點(子樹1子樹2子樹3...)

圖一，圖二的有根樹可表示為A(B(CF(EGD)))和B(ACF(EGD))o由于子樹的表示

順序可以不同，所以一棵有根樹可以有多種表示方法，如圖三又可表示成

B(F(EGD)CA)或B(ACF(DE(G))等。表示無根樹時，可以以它任一節(jié)點為根節(jié)點,

將其看作有根樹，從而可以利用有根樹的字符串表示形式來表示無根樹。

任務一：由鍵盤讀入一個字符串表示的無根樹，無根樹的各節(jié)點的名稱用互不

相同的大寫英文字母表示。由用戶輸入一個節(jié)點的名稱，程序應能夠輸出一種以該

節(jié)點為根節(jié)點的字符串形式。程序輸出無根樹的字符串形式時.，各個節(jié)點的名稱無

關(guān)緊要，所有節(jié)點都以P表示，以后的各種輸出也采用這種形式。例如：輸入無根

樹的字符串形式：A(B(CD(EF))),指定根節(jié)點為D,程序應能輸出

P(P(PP)PP),P(PP(PP)P),P(PPP(PP))中的任意

一種即可。

任務二：輸入兩個串表示的無根樹，判斷其結(jié)構(gòu)是否一樣。注意它與節(jié)點名稱

無關(guān)，只考慮結(jié)構(gòu)。

任務三：輸入無根樹的總枝數(shù)N(1<=N<=11),輸出所有枝數(shù)為N的互不相同

的無根樹，并記錄總數(shù)。以字符串形式輸出，例如：N=5時共有6種不同結(jié)構(gòu)的無

根樹。

注意：各種樹結(jié)構(gòu)的字符串表達形式不唯-O

-12-

中級訓練題

60.用N*N（1<=N<=8）的格點陣代表海，其中*號代表島。給你一組編

碼信息，讓你重構(gòu)一張地圖。這組信息是按垂直方向，水平方向島的情況摘取的。

下例中，每行右邊的數(shù)字按順序表示該行中“島組”的大小，如第一行數(shù)字為

“12”，表示該行第一“島組”由一個島組成，第二“島組”由兩個島組成，而

第四列下面的“23”則表示本列山兩個“島組”組成，第一個“島組”由兩個島

組成，第二個“島組”由三個島組成。

任務：編程執(zhí)行以下步驟，直到給定的輸入（ASCH）文件中的信息組全部讀完

為止，步驟如下：

（1）從輸入文件（ASCII文件）中讀入下一個信息塊，并將它顯示在屏幕上。

每個信息塊組成為：

格點陣大?。∟）,以后是行的約束條件（N行的），列的約束條件（N列的），

每行（或每列）的約束條件是

一行數(shù)字，數(shù)字間有空格，最后用0結(jié)束。上面的例子如圖所示。

（2）重構(gòu)這張地圖（若有多個解，要逐個構(gòu)成地圖），并顯示。

（3）將重構(gòu)的地圖以ASCII文件形式輸出。每島以*后加一個空格表示；

空白處用連續(xù)的兩個空格表示。若同一已知條件可畫出多張地圖，相互間用空行隔

開；若一組已知條件畫不出地圖，用“NOMAP（占一行）表示。由不同的信

息組求得的解用“NEXTPROBLEM”（占一行表示）1V=N<=8.

61.一個餐廳在相繼的N天里，第i天需要Ri塊餐巾（i=l,2,N）?餐廳

可以從三種途徑得到餐巾：

（1）購買新的餐巾，每塊需P分；

（2）把用過的餐巾送到快洗部，洗一塊需M天，費用需F分（FVP）；

（3）把餐巾送到慢洗部，洗一塊需N天（N>M）,費用需S分（SVF）。

在每天結(jié)束時，餐廳必須決定將多少塊用過的餐巾送到快洗部，多少塊送慢洗部，

多少塊保存起來延期送洗。在每天開始時，餐廳必須決定是否購買新餐巾及購買多

少，使洗好的和新購的餐巾之和滿足當天的需求量Ri,并使N天總的費用最小。請

編程輸入總天數(shù)，每天所需的餐巾塊數(shù)以及每塊餐巾的新購費用P,快，慢洗費用

F,S,和所需天數(shù)M,N,輸出每天開始時需購新餐巾數(shù)，結(jié)束時送快，慢洗部

和延期送洗的餐巾數(shù)。

62.（旅行商）一個推銷員計劃做一次旅行，他必須訪問如圖所示每個城市。每

兩個城市的路徑旁標有路徑。要求從城市A出發(fā)，訪問每個城市?次，且只訪問一

次，最后返回城市A,求一條距離最短的路線。

63.（tic_tac_toe游戲）tic_tac_toe游戲的規(guī)則是：從一個空的（N*N）的

棋盤（例如N=3）開始，甲乙二人輪流將棋子放置在棋盤上未被占據(jù)的方格中，

例如甲第一個放，他把棋子放在中央的方格里，然后輪到乙放，他把棋子放在第

一行中間的方格里。于是又輪到甲放，.....如此進行下去。判定勝負的方法是：

若某一游戲者有N枚棋子占據(jù)了一橫行，或一豎列，或一對角線，則此人獲勝；若

直至整個棋盤被占滿還沒有一方獲勝，則為平局。

II0||

-13-

中級訓練題

IIXII

I~~I―I-I

64.以字符串形式由鍵盤輸入兩個高精度的8進制正整數(shù)，串長小于255,以

第一個數(shù)為被除數(shù)，第二個數(shù)為除數(shù)，進行高精度除法運算，并顯示按8進制表

示的商和余數(shù)。

(參看程序8)

65.(NOI>94.1_1)鍵盤輸入一個僅由小寫字母組成的字符串，輸出以該串中任

取M個字母的所有排列及排列總數(shù)。

66.(NOI>94.1_2)編程實現(xiàn)兩個高精度實數(shù)減法，兩數(shù)分別由鍵盤輸入，均不

超過240位。

(參看程序5)

67.(NOP94.1_3)一個實數(shù)數(shù)列共有N項,已知a(i)=(a(iT)-a(i+l))/2+d,

(1〈i〈N)(N<60),鍵盤輸入N,d,a(l),a(n),m,輸出a(m)?

68.(NOI'94.1_4)鍵盤輸入?個高精度的正整數(shù)N,去掉其中任意S個數(shù)字后

剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的N和S,尋找一種

方案使得剩下的數(shù)字組成的新數(shù)最小。輸出應包括所去掉的數(shù)字的位置和組成的新

的正整數(shù)。(N不超過240位)

69.在兩個文本文件中各存有?個以西文制表符制成的未填入任何表項的表結(jié)構(gòu)，

分別稱之為表1和表2,要求編程將表1和表2下述規(guī)則合并成表3：

規(guī)則：表1在表2之上，表1和表2的左邊框?qū)R，將表1的最低行與表2的

最頂行合并。例：在你的C盤根目錄下有兩個文件tO.1和tO.2,分別存放上述

的表1和表2,經(jīng)上述規(guī)則合并后得到表3,放在文件中。三張表見下圖：

表1表2表3

編程要求：

(1)程序應能自給定的文件中讀入兩個源表并顯示。

(2)若源表有錯，應能指出其錯。

(3)將表1和表2規(guī)則合并成表3,并顯示之。

-14-

中級訓練題

（4）所有制表符的ASCII碼應由選手自己從給出的示例文件中截取。

70.（圓盤問題）從左向右依次安放4根細柱A,B,C,D.在A上套有N（NW20）

個直徑相同的圓盤，從下到上依次用連續(xù)的小寫字母a,b,c,...編號，將這些圓盤

經(jīng)過B,C單向地移入D（即不允許從右向左移動）.圓盤可在B.C中暫存.從鍵

盤輸入N,及前N個小寫字母的一個排列，它表示最后在D盤上形成的?個從下

到上的圓盤序列.請用文本文件ANS2.TXT輸出形成這一排列的操作過程.

該文件的每一行為一個形如"kML”的字母序列，其中k為圓盤編號，M為k

盤原先的柱號，L為新柱號.或者直接在屏幕上輸出"No”,表示不能生成這種排列.

例：111

鍵盤輸入：111

3d-4—11

acbc—1—11

則一個正確的輸出文件b-4—11

可以是：a-4—11

cAB1111

bACABcD

aAD

bCD

cBD

71.（最長連線）設有一個NXN的方格圖形，且N為3的倍數(shù)。要求在圖形中

存放0或1,相鄰的1可以連成一條連線，連接的方法可以是行，也可以是列;

同時約定一條連線只能有一個起點和一個終點，圖形上的點最多只能訪問一次。

編程求最長連線.例如N=6時，有下圖：

123456

iiiio；o；I

1|1|1|1|1|

1111

1I____1L.1111

2|1|1|0|11111|

I111

1I____1L.1111

3|0|0|0|110|1|

I____L.1111

111111

4|1|1|0|11111|

1111

1I____1L_1111

5|0|1|01010101

1111

I1____L11111

6|1|1|11110101

11i1111

在該圖中，包含有如下的一些連