信息學(xué)（計(jì)算機(jī)）奧林匹克訓(xùn)練題 （中級(jí)部分）

中級(jí)訓(xùn)練題

信息學(xué)（計(jì)算機(jī)）奧林匹克訓(xùn)練題（中級(jí)部分）

天津師范大學(xué)李學(xué)武編1997.7.

1.給定等式ABCDE其中每個(gè)字母代表一個(gè)數(shù)字，且不同數(shù)字對(duì)應(yīng)不

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

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

XYZDE

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

了競(jìng)賽：

（1）A參加時(shí)，B也參加；

（2）B和C只有一個(gè)人參加；

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

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

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

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

字符的個(gè)數(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階拉丁方陣。例如下圖就是一個(gè)五階拉丁方陣。編一程序，從鍵盤(pán)輸入N值

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

12345

23451

34512

45123

51234

-1-

中級(jí)訓(xùn)練題

5.輸入?個(gè)十進(jìn)數(shù)，將其轉(zhuǎn)換成N進(jì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.讀入一行文本，包含若干個(gè)單詞(以空格間隔，％結(jié)尾)。將其中以A開(kāi)頭的單詞與

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

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

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

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

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

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

程解決此問(wèn)題。

10.如圖1所示，編寫(xiě)程序計(jì)算

IIIIIIIIIII

大大小小正方形共有多少？當(dāng)最小IIIIIIIIIII

IIIIIIIIIII

正方行邊長(zhǎng)為1時(shí)，它們的總面積IIIIIIIIIII

共為多少？IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

IIIIIIIIIII

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

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

12.下圖是一個(gè)集裝箱倉(cāng)庫(kù)，陰影部分表示有集裝箱存放不能通過(guò)，無(wú)陰影處為臨時(shí)通道。

-2-

中級(jí)訓(xùn)練題

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

不斷地重復(fù)上述過(guò)程，直到最后全部硬幣翻成反面朝上為止。編程讓計(jì)算機(jī)把翻幣的最簡(jiǎn)過(guò)

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

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

***…***000…000

N個(gè)黑棋N個(gè)白棋

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

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

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

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

車）可以到達(dá)的所有城市。

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

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

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

17.編寫(xiě)一個(gè)程序，當(dāng)輸入不超過(guò)60個(gè)字符組成的英文文字時(shí)，計(jì)算機(jī)將這個(gè)句子中的

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

輸入：

THEPRICE0FBREADIS￥125PERPOUND

輸出：

ABCDDEEEEFHIINO0P￥125PPRRRSTU

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

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

的位置為空。

-3-

中級(jí)訓(xùn)練題

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

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

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

移動(dòng)棋子的條件：

(1)每個(gè)格中只準(zhǔn)放一個(gè)棋子。

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

(3)一方的棋子均可跳過(guò)另一方的一個(gè)棋子進(jìn)入空格。

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

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

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

且中間為空格.

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

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

總重量CTOTAL,并設(shè)法使得背包中物品的價(jià)值盡可能高。

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

能處在棋盤(pán)的同一行，同一列，同一斜線上，試問(wèn)共有多少種擺法？

21.請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序，由計(jì)算機(jī)把I..18的八個(gè)自然數(shù)填入圖中，使得橫、豎、對(duì)角任

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

4II8|

I5||7|

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

TI1I2|

7|??~~?

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

號(hào)。

I*II*I

-4-

中級(jí)訓(xùn)練題

1*1*1

求出所有的基本解。

23.（覆蓋問(wèn)題）有邊長(zhǎng)為N（N為偶數(shù)）的正方形，請(qǐng)你用N-2/2個(gè)長(zhǎng)為2,寬為1

的長(zhǎng)方形，將它全部覆蓋。編程打印出所有覆蓋方法。如：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塊，（見(jiàn)圖）。請(qǐng)?jiān)O(shè)計(jì)個(gè)程序，由計(jì)算機(jī)尋找并打印出所有的上班的路徑。

單位

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

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

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

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

??11

|1|213|

11I

111

|8|014|

11I

111

|7|615|

-5-

中級(jí)訓(xùn)練題

初始狀態(tài)目標(biāo)狀態(tài)

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

體要求：

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

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

例：Entertheinitialstate:283164705

Enterthefinalstate:123804765

b、對(duì)輸入數(shù)據(jù)應(yīng)有查錯(cuò)和示錯(cuò)功能；

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

息)；

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

a、移動(dòng)每一步時(shí)的序號(hào)，最后一步的序號(hào)即為移動(dòng)總步數(shù)：

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

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

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

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

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

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

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

移動(dòng)規(guī)則：

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

不能上移進(jìn)入上面空格。

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

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

實(shí)現(xiàn)目標(biāo)：

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

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

②對(duì)輸入的數(shù)據(jù)應(yīng)有查錯(cuò)和報(bào)錯(cuò)功能；

(2)實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)換(如不能實(shí)現(xiàn)也應(yīng)給出必要的說(shuō)明)。

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

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

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

(4)以最少的移動(dòng)步數(shù)達(dá)到目標(biāo)。

I3|4|0|I0I0I0|

|01025I|12345I

圖10—1圖10—2

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

-6-

中級(jí)訓(xùn)練題

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

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

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

大長(zhǎng)度2000個(gè)字符）。排版時(shí)以單詞為基本單位。單詞由不含空格的任意字符組成，是長(zhǎng)

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

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

章按行輸出。輸出時(shí)不能將一個(gè)完整的單詞截?cái)?，并要求輸出的總行?shù)最小。將每個(gè)不足N

個(gè)字符的行用空格補(bǔ)足，填充空格符的方式有以下三種。

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

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

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

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

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

有多少種特征？每個(gè)人的磁卡上至少要有多少特征？如果特征的編號(hào)以小寫(xiě)英文字母表示，

將每個(gè)人的磁卡的特征編號(hào)打印出來(lái)，要求輸出的電子鎖

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

設(shè)3〈=M<=7,1<=N<=4,M與N由鍵盤(pán)輸入，工作人員編號(hào)用表示.

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

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

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

所有棋子都取走。

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

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

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

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

不能走動(dòng)，走至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è)有三個(gè)傳教士和三個(gè)野人來(lái)到河邊，打算乘一只船從右

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

-7-

中級(jí)訓(xùn)練題

人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)

河去呢？

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

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

序使計(jì)算機(jī)有較多的獲勝機(jī)會(huì)。

屏幕輸入提示：

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

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

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

(3)一次最多取幾顆？

(4)誰(shuí)先??？

(5)每個(gè)回合都應(yīng)顯示：A.你取兒顆？

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

(6)競(jìng)賽過(guò)程中發(fā)生違例時(shí)，打印出：競(jìng)賽無(wú)法進(jìn)行下去！

(7)競(jìng)賽結(jié)束后打?。?/p>

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

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

等的兩堆。然后每個(gè)選手輪流地這樣做，即當(dāng)輪到某一方分時(shí)，他把已被分開(kāi)的任

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

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

36.猴子選大王：

①N只猴子站成一行，每隔M只從頭到尾報(bào)數(shù)，反復(fù)進(jìn)行，報(bào)過(guò)數(shù)的退出，打

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

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

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

③N只猴子圍成一圈，從第P個(gè)開(kāi)始，每隔M只報(bào)數(shù)，打印每次過(guò)程，只剩下

一個(gè)時(shí)為大王。

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

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

例如:N=2時(shí),給定Kl+K2=6,當(dāng)Kl=3,K2=3時(shí),K1*K2=9為最大

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

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

39.一個(gè)集合滿足如下條件：

(1)1是集合的元素；

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

求：此集合中最小的K個(gè)元素。

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

-8-

中級(jí)訓(xùn)練題

40.一個(gè)整型變量只能用來(lái)存貯較小的N!的值，當(dāng)N較大時(shí)，可將階乘值中的

每一個(gè)數(shù)字放在一個(gè)一維數(shù)組的一個(gè)元素中。使用這方法，打?。?/p>

①N!的值；

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

③N!+M!

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

為一個(gè)鏈表CN={al,bl,a2,b2,...}

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

求其值。

43.對(duì)于次數(shù)很高，但項(xiàng)目很少的多項(xiàng)式，可用鏈表來(lái)表示。

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

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

在此方式下，編程完成兩個(gè)多項(xiàng)式的加法與乘法。

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

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

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

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

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

項(xiàng)要合并(指數(shù)最大不超過(guò)30)。

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

4,3

-7,4

1,0

0,0

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

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

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

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

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

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

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

46.設(shè)有一個(gè)字符串，長(zhǎng)度小于100,且全部以英文字母組成。對(duì)字串中的每個(gè)字

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

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

-9-

中級(jí)訓(xùn)練題

(2)輸出對(duì)應(yīng)的編碼表及碼長(zhǎng)，要求字串的編碼總長(zhǎng)度為最短;

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

例如：輸入的字符為：ABCBAAADDEF

其對(duì)應(yīng)的編碼表為：

A:2B:10

C:11D:12

E:00F:01

對(duì)應(yīng)的編碼為:210111022212120001總碼長(zhǎng)為：18

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

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

,Wn,要求編程完成下列任務(wù)：

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

②鍵入N個(gè)英文字母的使用頻率；

③用二進(jìn)制數(shù)對(duì)該N個(gè)英文字母進(jìn)行編碼(最短，無(wú)二義性)；

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

⑤鍵入二進(jìn)制編碼短文，輸出譯文。

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

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

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

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

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

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

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

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

過(guò)程的總數(shù).

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

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

可計(jì)算一個(gè)面積:若同號(hào),則面積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(詳見(jiàn)下圖)，數(shù)

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

編程要求如下：

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

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

出一個(gè)錯(cuò)位相加的方案，使A3的面積最大.

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

(1)(2)

A1372372

-10-

中級(jí)訓(xùn)練題

A2-57-4-57-4

A33720-57-4372-57-4

(3)(9)

A1372372

A2-57-4-57-4

A337-37-4-57-40372

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

件,且只完成一件，每人完成不同工作的時(shí)間不同.試設(shè)計(jì)一種分配工作方案，使

完成N件工作所需的總時(shí)間最少.

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

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

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

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

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

形式為a-b,其中a為工作人員編號(hào)，b為他應(yīng)完成的工作序號(hào).

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

4

215134

1041415

9141613

78119

對(duì)此，一個(gè)正確的輸出可以是

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

T0TAL=28

54.求N個(gè)字符串的最長(zhǎng)公共子串，N<=20,字符串長(zhǎng)度不超過(guò)255。

例如：N=3,由鍵盤(pán)依次輸入三個(gè)字符串為

Whatislocalbus?

Namesomelocalbuses.

localbusisahighspeedI/Obusclosetotheprocesser.

則最長(zhǎng)公共子串為"localbus”。

（參看程序9）

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

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

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

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

如：4107395682。

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

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

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

-11-

中級(jí)訓(xùn)練題

(參看程序3)

57.某一印刷廠有六項(xiàng)加工任務(wù)，對(duì)印刷車間和裝訂車間所需時(shí)間見(jiàn)下表(時(shí)間單

位：天)

任務(wù)|J1J2J3J4J5J6

印刷車間|31252911

裝訂車間|8109631

如何安排加工順序，使加工時(shí)間最少。

58.將7萬(wàn)元投資到A,B,C三項(xiàng)目上，其利潤(rùn)見(jiàn)下表：

投資額(萬(wàn)元)|1234567

項(xiàng)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

如何分配投資額，使獲得的利潤(rùn)最大。

59.無(wú)根樹(shù)與通常所說(shuō)的樹(shù)(有根樹(shù))很相似，它包含有節(jié)點(diǎn)和枝，但不含有根。

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

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

無(wú)根樹(shù)的角度看，圖-、二、三是結(jié)構(gòu)相同的無(wú)根樹(shù)，同時(shí)無(wú)根樹(shù)的結(jié)構(gòu)與節(jié)點(diǎn)的

名稱無(wú)關(guān)。

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

根節(jié)點(diǎn)(子樹(shù)1子樹(shù)2子樹(shù)3...)

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

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

B(F(EGD)CA)或B(ACF(DE(G))等。表示無(wú)根樹(shù)時(shí)，可以以它任一節(jié)點(diǎn)為根節(jié)點(diǎn),

將其看作有根樹(shù)，從而可以利用有根樹(shù)的字符串表示形式來(lái)表示無(wú)根樹(shù)。

任務(wù)一：由鍵盤(pán)讀入一個(gè)字符串表示的無(wú)根樹(shù)，無(wú)根樹(shù)的各節(jié)點(diǎn)的名稱用互不

相同的大寫(xiě)英文字母表示。由用戶輸入一個(gè)節(jié)點(diǎn)的名稱，程序應(yīng)能夠輸出一種以該

節(jié)點(diǎn)為根節(jié)點(diǎn)的字符串形式。程序輸出無(wú)根樹(shù)的字符串形式時(shí).，各個(gè)節(jié)點(diǎn)的名稱無(wú)

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

樹(shù)的字符串形式：A(B(CD(EF))),指定根節(jié)點(diǎn)為D,程序應(yīng)能輸出

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

一種即可。

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

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

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

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

根樹(shù)。

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

-12-

中級(jí)訓(xùn)練題

60.用N*N（1<=N<=8）的格點(diǎn)陣代表海，其中*號(hào)代表島。給你一組編

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

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

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

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

組成，第二個(gè)“島組”由三個(gè)島組成。

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

為止，步驟如下：

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

每個(gè)信息塊組成為：

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

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

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

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

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

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

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

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

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

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

（1）購(gòu)買新的餐巾，每塊需P分；

（2）把用過(guò)的餐巾送到快洗部，洗一塊需M天，費(fèi)用需F分（FVP）；

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

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

多少塊保存起來(lái)延期送洗。在每天開(kāi)始時(shí)，餐廳必須決定是否購(gòu)買新餐巾及購(gòu)買多

少，使洗好的和新購(gòu)的餐巾之和滿足當(dāng)天的需求量Ri,并使N天總的費(fèi)用最小。請(qǐng)

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

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

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

62.（旅行商）一個(gè)推銷員計(jì)劃做一次旅行，他必須訪問(wèn)如圖所示每個(gè)城市。每

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

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

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

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

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

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

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

直至整個(gè)棋盤(pán)被占滿還沒(méi)有一方獲勝，則為平局。

II0||

-13-

中級(jí)訓(xùn)練題

IIXII

I~~I―I-I

64.以字符串形式由鍵盤(pán)輸入兩個(gè)高精度的8進(jìn)制正整數(shù)，串長(zhǎng)小于255,以

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

示的商和余數(shù)。

(參看程序8)

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

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

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

超過(guò)240位。

(參看程序5)

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

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

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

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

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

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

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

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

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

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

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

表1表2表3

編程要求：

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

(2)若源表有錯(cuò)，應(yīng)能指出其錯(cuò)。

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

-14-

中級(jí)訓(xùn)練題

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

70.（圓盤(pán)問(wèn)題）從左向右依次安放4根細(xì)柱A,B,C,D.在A上套有N（NW20）

個(gè)直徑相同的圓盤(pán)，從下到上依次用連續(xù)的小寫(xiě)字母a,b,c,...編號(hào)，將這些圓盤(pán)

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

盤(pán)輸入N,及前N個(gè)小寫(xiě)字母的一個(gè)排列，它表示最后在D盤(pán)上形成的?個(gè)從下

到上的圓盤(pán)序列.請(qǐng)用文本文件ANS2.TXT輸出形成這一排列的操作過(guò)程.

該文件的每一行為一個(gè)形如"kML”的字母序列，其中k為圓盤(pán)編號(hào)，M為k

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

例：111

鍵盤(pán)輸入：111

3d-4—11

acbc—1—11

則一個(gè)正確的輸出文件b-4—11

可以是：a-4—11

cAB1111

bACABcD

aAD

bCD

cBD

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

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

同時(shí)約定一條連線只能有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，圖形上的點(diǎn)最多只能訪問(wèn)一次。

編程求最長(zhǎng)連線.例如N=6時(shí)，有下圖：

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

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