C++入門必做題 題目 共76道題

以下是C++入門必做題所有題目猖毫，共76道題

關于字體顯示的說明：

由于字體格式限制，部分題目的英文部分有偏移現(xiàn)象须喂。

解決辦法：將題目拷貝到記事本吁断，字體設置為‘Fixedsys’即可。

1.給定等式? A B C D E???? 其中每個字母代表一個數(shù)字坞生，且不同數(shù)字對應不

D F G同字母仔役。編程求出這些數(shù)字并且打出這個數(shù)字的

+????? D F G算術(shù)計算豎式。

???????????? ───────

??????????????? X Y Z D E

2.Ａ是己、Ｂ又兵、Ｃ、Ｄ卒废、Ｅ五名學生有可能參加計算機競賽沛厨，根據(jù)下列條件判斷哪些

人參加了競賽：

（１）Ａ參加時，Ｂ也參加摔认；

（２）Ｂ和Ｃ只有一個人參加逆皮；

（３）Ｃ和Ｄ或者都參加，或者都不參加参袱；

（４）Ｄ和Ｅ中至少有一個人參加电谣；

（５）如果Ｅ參加，那么Ａ和Ｄ也都參加抹蚀。

3.打印一個 N*N 的方陣剿牺，Ｎ為每邊?????????? Ｎ＝１５? 打印出下面圖形

字符的個數(shù)（３＜Ｎ＜２０）, 要求最?????????????? TTTTTTTTTTTTTTT

外一層為"T", 第二層為"J", 從第三層?????????????? TJJJJJJJJJJJJJT

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

（右圖以Ｎ為１５為例）?????????????????????????? TJ12222222221JT

????????????????????????????????????????????????? TJ12333333321JT

????????????????????????????????????????????????? TJ12344444321JT

????????????????????????????????????????????????? TJ12345554321JT

????????????????????????????????????????????????? TJ12345654321JT

????????????????????????????????????????????????? TJ12345554321JT

????????????????????????????????????????????????? TJ12344444321JT

????????????????????????????????????????????????? TJ12333333321JT

????????????????????????????????????????????????? TJ12222222221JT

????????????????????????????????????????????????? TJ11111111111JT

????????????????????????????????????????????????? TJJJJJJJJJJJJJT

????????????????????????????????????????????????? TTTTTTTTTTTTTTT

4.在Ｎ行Ｎ列的數(shù)陣中, 數(shù)Ｋ（１〈＝Ｋ〈＝Ｎ）在每行和每列中出現(xiàn)且僅

出現(xiàn)一次，這樣的數(shù)陣叫Ｎ階拉丁方陣环壤。例如下圖就是一個五階拉丁方陣晒来。

編一程序，從鍵盤輸入Ｎ值后郑现，打印出所有不同的Ｎ階拉丁方陣湃崩，并統(tǒng)計個數(shù)。

??????? 1? 2? 3? 4? 5

??????? 2? 3? 4? 5? 1

??????? 3? 4? 5? 1? 2

??????? 4? 5? 1? 2? 3

??????? 5? 1? 2? 3? 4

5.輸入一個十進數(shù)懂酱，將其轉(zhuǎn)換成 N 進制數(shù)（0<N<=16)竹习。

6.矩陣中填數(shù). 當給出 N*N 的矩陣，要求用程序填入下列形式的數(shù)：

①倒填列牺，例如N=5???????????? ② 蛇形填數(shù)????????????? ③ 回轉(zhuǎn)填數(shù)

?┌─┬─┬─┬─┬─┐?? ┌─┬─┬─┬─┬─┐?? ┌─┬─┬─┬─┬─┐

?│25│24│23│22│21│?? │ 1│ 3│ 4│10│11│?? │ 1│16│15│14│13│

?├─┼─┼─┼─┼─┤?? ├─┼─┼─┼─┼─┤?? ├─┼─┼─┼─┼─┤

?│20│19│18│17│16│?? │ 2│ 5│ 9│12│19│?? │ 2│17│24│23│12│

?├─┼─┼─┼─┼─┤?? ├─┼─┼─┼─┼─┤?? ├─┼─┼─┼─┼─┤

?│15│14│13│12│11│?? │ 6│ 8│13│18│20│?? │ 3│18│25│22│11│

?├─┼─┼─┼─┼─┤?? ├─┼─┼─┼─┼─┤?? ├─┼─┼─┼─┼─┤

?│10│ 9│ 8│ 7│ 6│?? │ 7│14│17│21│24│?? │ 4│19│20│21│10│

?├─┼─┼─┼─┼─┤?? ├─┼─┼─┼─┼─┤?? ├─┼─┼─┼─┼─┤

?│ 5│ 4│ 3│ 2│ 1│?? │15│16│22│23│25│?? │ 5│ 6│ 7│ 8│ 9│

?└─┴─┴─┴─┴─┘?? └─┴─┴─┴─┴─┘?? └─┴─┴─┴─┴─┘

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

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

8.輸入兩個正整數(shù)Ｘ九默，Ｙ震放，將Ｘ，Ｙ化為二進制數(shù)驼修，然后將這兩個二進制數(shù)作二進

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

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

數(shù)進行賠償，即贏者手中有多少根火柴棍恩静，輸者就賠償多少根』篮粒現(xiàn)知道玩過四次后，

每人恰好輸過一次驶乾， 而且每人手中都正好有１６根火柴邑飒。問此四人做游戲前手中各有

多少根火柴? 編程解決此問題。

10.如圖１所示级乐，編寫程序計算?????????????? ┎┰┰┰┰┰┰┰┰┰┒

大大小小正方形共有多少疙咸？當最小????????? ┠╂╂╂╂╂╂╂╂╂┨

正方行邊長為１時，它們的總面積????????? ┠╂╂╂╂╂╂╂╂╂┨

共為多少唇牧？????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨

??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨

??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨

??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨

??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨

??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨

??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨

??????????????????????????????????????????? ┖┸┸┸┸┸┸┸┸┸┚

11.巧排數(shù)字罕扎。將１、２丐重、．．．腔召、２０這２０個數(shù)排成一排，使得相鄰的兩個數(shù)之

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

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

道。當有人要從入口處到達出口處時豫领，必須尋找可通過路線抡柿，請你找出可完成這個過程

的最方便（即用最短路線）到達出口處的路徑。

┎┰┰┰入口┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┒

????????? ┠╂╂╂──╂╂╂╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂╂┸┸╂╂╂┨

????????? ┠╂╂╂──╂┸┸╂──╂┰┰╂┰┰╂──╂╂╂╂──╂╂╂┨

????????? ┠╂╂╂──╂┰┰╂┰┰╂╂╂╂╂╂╂──╂┸┸╂──╂╂╂┨

????????? ┠╂╂╂──╂╂╂╂╂╂╂╂╂╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂┨

????????? ┠╂╂╂──╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂┨

????????? ┠╂╂╂──╂┰┰╂┰┰╂┰┰╂──╂┰┰╂──╂┰┰╂╂╂┨

????????? ┠╂╂╂──╂╂╂╂╂╂╂╂╂╂──╂╂╂╂──╂╂╂╂╂╂┨

????????? ┠╂╂╂──╂╂╂╂┸┸╂┸┸╂──╂╂╂╂──╂┸┸╂╂╂┨

????????? ┠╂╂╂──╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂╂┰┰╂──╂╂╂┨

┖┸┸┸──┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸出口┸┸┸┚

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

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

翻幣的最簡過程及翻幣次數(shù)打印出來（用＊代表正面囱稽，O 代表反面）窍侧。

14.有黑白棋子各有Ｎ個（分別用＊和Ｏ代替）毕源，按下圖方式排列

＊＊＊．．．＊＊＊ＯＯＯ．．．ＯＯＯ

Ｎ個黑棋??????????? Ｎ個白棋

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

15.已知６個城市宏胯，用ｃ[i,j]表示從ｉ城市到城市ｊ是否有單向的直達汽車

（１=<ｉ〈＝６渔嚷，１〈＝ｊ〈＝６）, c[i,j]=1 表示城市ｉ到城市ｊ有單向直達汽

車谨湘； 否則 ｃ[i,j]＝0.? 試編制程序，對于給出的城市代號ｉ衫哥，打印出從該城市出

發(fā)乘車（包括轉(zhuǎn)車）可以到達的所有城市茎刚。

16.設有８枚硬幣ａ，ｂ撤逢，ｃ，ｄ粮坞，ｅ蚊荣，ｆ，ｇ莫杈，ｈ互例，其中有一枚硬幣是偽造的。

真?zhèn)斡矌诺膮^(qū)別僅是重量不同筝闹，可能重媳叨，可能輕。今要求以天平為工具关顷，用最少的

比較次數(shù)挑出偽造硬幣糊秆，并鑒定它是重還是輕。

17.編寫一個程序议双，當輸入不超過６０個字符組成的英文文字時痘番，計算機將這個句子

中的字母按英文字典字母順序重新排列，排列后的單詞的長度要與原始句子中的長度

相同平痰。例如：

輸入：

ＴＨＥ ＰＲＩＣＥ ＯＦＢＲＥＡＤ ＩＳ ￥１ ２５ ＰＥＲ ＰＯＵＮＤ

輸出：

ＡＢＣ ＤＤＥＥＥ ＥＦＨＩＩＮＯ ＯＰ ￥１ ２５ ＰＰＲ ＲＲＳＴＵ

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

18.在一線性七個格位置的圖上有兩種不同顏色的棋子Ａ宗雇，Ｂ. 排列如下圖所示昂芜，中間

格的位置為空。

????????? ┎─┰─┰─┰─┰─┰─┰─┒

┃Ａ┃Ａ┃Ａ┃? ┃Ｂ┃Ｂ┃Ｂ┃

????????? ┖─┸─┸─┸─┸─┸─┸─┚

要求將Ａ赔蒲，Ｂ的現(xiàn)行位置交換,形成下圖中的排列：

????????? ┎─┰─┰─┰─┰─┰─┰─┒

┃Ｂ┃Ｂ┃Ｂ┃? ┃Ａ┃Ａ┃Ａ┃

????????? ┖─┸─┸─┸─┸─┸─┸─┚

移動棋子的條件：

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

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

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

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

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

編程完成有關的移動砾嫉，并且完成具有２Ｎ＋１個格子的情形. 其中兩種顏色各有

Ｎ個棋子,且中間為空格.

19. (背包問題) 有 N 件物品 d1幼苛，......dN，每件物品重量為 W1焕刮，..., WN

(Wi > 0)舶沿， 每件物品價值為 V1墙杯，......VN (Vi>0)。用這N件物品的某個子集

填空背包括荡，使得所取物品的總重量<=TOTAL高镐，并設法使得背包中物品的價值盡可

能高。

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

兩個皇后不能處在棋盤的同一行，同一列邑闲，同一斜線上算行，試問共有多少種擺法？

21.請設計一個程序苫耸，由計算機把１..￣.８的八個自然數(shù)填入圖中州邢，使得橫、

豎褪子、對角任何兩個相鄰的小方格中的兩個數(shù)是不連續(xù)的量淌。(下圖右側(cè)的 4 個圖

為禁止的情形).

??????????? ┌─┐????????? ┌─┐?????????????? ┌─┐

│? │????????? │４│?????????????? │８│

??????? ┌─┼─┼─┐????? └─┼─┐?????? ┌─┼─┘

│? │? │? │????????? │５│?????? │７│

??????? ├─┼─┼─┤????????? └─┘?????? └─┘

??????? │? │? │? │????? ┌─┐

└─┼─┼─┘????? │６│?????????? ┌─┬─┐

│? │????????? ├─┤?????????? │１│２│

└─┘????????? │７│?????????? └─┴─┘

??????????????????????????? └─┘

22.在一個４＊４的小方格（如圖所示）中放置８個＊號，使得每行每列放且

僅放兩個＊號嫌褪。

????????? ┌─┬─┬─┬─┐

│＊│＊│? │? │

????????? ├─┼─┼─┼─┤

│＊│? │＊│? │

????????? ├─┼─┼─┼─┤

│? │＊│? │＊│

????????? ├─┼─┼─┼─┤

│? │? │＊│＊│

????????? └─┴─┴─┴─┘

求出所有的基本解呀枢。

23. (覆蓋問題) 有邊長為Ｎ（Ｎ為偶數(shù)）的正方形，請你用Ｎ＾２／２個長為２,

寬為１的長方形渔扎，將它全部覆蓋硫狞。編程打印出所有覆蓋方法。如：Ｎ＝４

??? ┌─┬──┬─┐??????????? ┌──┬──┐

│? │??? │? │１２２４?? │??? │??? │? １１２２

??? │? ├──┤? │??????????? ├──┼──┤

│? │??? │? │１３３４?? │??? │??? │? ３３４４

??? ├─┼──┼─┤??????????? ├──┼──┤

│? │??? │? │５６６８?? │??? │??? │? ５５６６

??? │? ├──┤? │??????????? ├──┼──┤

│? │??? │? │５７７８?? │??? │??? │? ７７８８

??? └─┴──┴─┘??????????? └──┴──┘

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

向東要走Ｍ塊倘核，向北要走Ｎ塊泣侮，（見圖）。請設計一個程序紧唱，由計算機尋找并

打印出所有的上班的路徑活尊。

單位

?????????? ┬?? ┌─┬─┬─┬─┬─┬─┬─┐

?????????? │?? │? │? │? │? │? │? │? │

?????????? │?? ├─┼─┼─┼─┼─┼─┼─┤

?????????? ↓?? │? │? │? │? │? │? │? │

Ｎ?? ├─┼─┼─┼─┼─┼─┼─┤

?????????? ↑?? │? │? │? │? │? │? │? │

?????????? │?? ├─┼─┼─┼─┼─┼─┼─┤

?????????? │?? │? │? │? │? │? │? │? │

?????????? ┴?? └─┴─┴─┴─┴─┴─┴─┘

家?? ├─────→Ｍ←─────┤

25. (量水) 用存水為Ｍ，Ｎ升的兩個罐子漏益，量出Ａ升水蛹锰。

26. (八數(shù)碼問題) ８個編有數(shù)碼１￣８的滑牌，能在３＊３的井字格中滑動绰疤。

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

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

???????? ┎─┬─┬─┒??????????????????????? ┏━┯━┯━┓

???????? ┃2 │8 │3 ┃??????????????????????? ┃1 │2 │3 ┃

???????? ┠─┼─┼─┨??????????????????????? ┠─┼─┼─┨

┃1 │6 │4 ┃－－－－＞???????? ┃8 │0 │4 ┃

???????? ┠─┼─┼─┨??????????????????????? ┠─┼─┼─┨

???????? ┃7 │0 │5 ┃??????????????????????? ┃7 │6 │5 ┃

???????? ┗━┷━┷━┛??????????????????????? ┗━┷━┷━┛

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

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

序列敛劝，具體要求：

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

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

例：Enter the initial state:2 8 3 1 6 4 7 0 5

???????????? Enter the final state:1 2 3 8 0 4 7 6 5

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

（２）實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)換（如不能實現(xiàn)像捶，程序應輸出不能實現(xiàn)

的提示信息）上陕；

（３）輸出結(jié)果，每移動一步都必須在屏幕上顯示:

ａ作岖、移動每一步時的序號唆垃，最后一步的序號即為移動總步數(shù)；

ｂ痘儡、每一步移動后以３＊３表格形式顯示狀態(tài)。

（４）要求能使移動步數(shù)盡可能少枢步；

27.給出一個有８個格子的表格沉删，除３個格子外，每個格子中可放入一個數(shù)字醉途，這

些數(shù)字取自自然數(shù) 1 到 5矾瑰，放入格子中的數(shù)字不得相同，剩余的３個格子是空格

（用Ｏ表示）隘擎。圖１是一個放數(shù)字與空格的特例∨寡ǎ現(xiàn)要求編程實現(xiàn)從初始表格狀態(tài)

變化到目標表格狀態(tài)。初始狀態(tài)和目標狀態(tài)都是可變的（圖１货葬，圖２所示的狀態(tài)僅

是一個特例）采幌，由鍵盤輸入格子中的數(shù)字（０￣５）。

移動規(guī)則：

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

格，而不能上移進入上面空格蹲姐。

(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ù)達到目標。

????????????? ┎─┰─┰─┒????????????????????????? ┎─┰─┰─┒

┃３┃４┃０┃????????????????????????? ┃０┃０┃０┃

????????? ┎─╂─╂? ╂─╂─┒????????????????? ┎─╂─╂? ╂─╂─┒

┃０? １? ０? ２? ５┃????????????????? ┃１? ２? ３? ４? ５┃

????????? ┖─┸─┸─┸─┸─┚????????????????? ┖─┸─┸─┸─┸─┚

圖 １０－１???????????????????????????? 圖 １０－２

初始狀態(tài)Ａ????????????????????????????? 目標狀態(tài)Ｂ

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

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

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

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

成孟害，是長度小于２０個字符的串∨材猓空格符是分隔單詞的唯一字符挨务，在輸入時連續(xù)的空格

符在處理時應先化簡為單個空格符。在排版前應先輸入玉组，排版后每行的字符數(shù)為Ｎ谎柄，排

版后將整理好的文章按行輸出。輸出時不能將一個完整的單詞截斷惯雳，并要求輸出的總行

數(shù)最小朝巫。將每個不足Ｎ個字符的行用空格補足，填充空格符的方式有以下三種石景。

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

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

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

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

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

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

母表示粟矿，將每個人的磁卡的特征編號打印出來凰棉，要求輸出的電子鎖的總特征數(shù)最少。

設 3<=M<=7, 1<=N<=4, Ｍ與Ｎ由鍵盤輸入陌粹，工作人員編號用 1#,2#,...表示.

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

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

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

所有棋子都取走映凳。

（２）討論棋子總數(shù)Ｎ（一定是偶數(shù)）從６到３０的各種情況胆筒。討論內(nèi)容包括：

對各個Ｎ，是否存在一個小于Ｎ的枚數(shù)Ｍ诈豌，甲第一次绕途取Ｍ枚后就能保證甲如果策略

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

32. (走棋 ) 一個４＊４的方陣如圖矫渔。有一個小卒從上往下走彤蔽。走至格子１后就

不能走動，走至０后庙洼，若下方為１顿痪，則向左或向右走，下方為０油够，則向下走员魏。求所

有走法。

????????????? ┌─┬─┬─┬─┐

????????????? │1 │0 │0 │0 │

????????????? ├─┼─┼─┼─┤

????????????? │0 │0 │1 │0 │

????????????? ├─┼─┼─┼─┤

????????????? │0 │1 │0 │0 │

????????????? ├─┼─┼─┼─┤

????????????? │1 │0 │0 │0 │

????????????? └─┴─┴─┴─┘

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

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

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

河去呢袜啃？

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

多确⑶恰Ｋ顆熟妓，最少绕鹩１顆 (Ｋ值不能超過總數(shù)的一半抬虽，也不能小于１)。試編寫一程

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

屏幕輸入提示:

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

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

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

(3)一次最多取幾顆疑故？

(4)誰先茸菔啤钦铁？

(5)每個回合都應顯示: A. 你取幾顆才漆？

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

(6)競賽過程中發(fā)生違例時鸳玩，打印出:? 競賽無法進行下去不跟！

(7)競賽結(jié)束后打游迅铩：

I win!（我勝Ａ拇场）或? You win!（你勝Ａ馐摺）。

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時，給定 K1+K2=6,當 K1=3,K2=3 時雷恃，K1*K2=9 為最大

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

元素值均小于total)把跨，求滿足條件的所有子集着逐，子集中各元素之和應等于total耸别。

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

(1)１是集合的元素；

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

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

【铩③ 對ＡＢＣ作全排列而得的六個三位數(shù)之和為 2886代乃。

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

每一個數(shù)字放在一個一維數(shù)組的一個元素中通贞。使用這方法昌罩，打酉棵浴：

①Ｎ绘搞！的值夯辖；

②Ｎ！－ＭＷ乃ā（Ｍ＞Ｎ）昙楚；

③Ｎ？熬伞＋Ｍ淳梦！

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

為一個鏈表 CN={a1,b1,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ù)最大不超過３０）。

上例第一式的輸入為：??? 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+1.

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) 輸入字符串磅甩，并能判斷輸入是否有錯渣聚；

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

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

例如：輸入的字符為:ABCBAAADDEF

其對應的編碼表為：

???????? A:?? 2??????????????? B:? 10

???????? C:? 11??????????????? D:? 12

???????? E:? 00??????????????? F:? O1

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

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

47.某些密碼由 N 個英文字母組成(N〈26), 每個字母的平均使用率為:W1,W2,...

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

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

②鍵入Ｎ個英文字母的使用頻率课梳；

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

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

⑤鍵入二進制編碼短文泉哈，輸出譯文奕纫。

48.將４個紅球，３個白球與３個黃球排成一排升筏，共有多少種排法？

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

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

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

過程的總數(shù).

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

設整型數(shù)組 C 具有 N 個分量: C=(C1,C2,...,CN), 兩相連分量(C[I],C[I+1])

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

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

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

編程要求如下:

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

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

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

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

??????????????????? (1)???????????????????????? (2)

??????? A1? 3? 7? 2?????????????????????? 3? 7? 2

??????? A2????????????? -5? 7? -4????????????????? -5? 7? -4

??????? A3? 3? 7? 2? 0? -5? 7? -4???????? 3? 7? 2? -5? 7? -4

??????????????????? (3)???????????????????????? (9)

??????? A1? 3? 7? 2???????????????????????????????????? 3? 7? 2

??????? A2?????? -5? 7 -4?????? ......???? -5? 7? -4

??????? A3? 3? 7 -3? 7 -4????????????????? -5? 7? -4? 0 3? 7? 2

53. (工作安排問題) 現(xiàn)有 N (N≤8) 件工作, 分別由 N 個人完成, 每人都完成一

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

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

原始數(shù)據(jù)由文本文件 EXAM1.TXT 給出, 其格式如下:

第 1 行:??????? 工作任務數(shù)(N)

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

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

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

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

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

???????? 4

???????? 2? 15? 13? 4

???????? 10? 4? 14? 15

???????? 9? 14? 16? 13

???????? 7? 8? 11? 9

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

???????? 1-4, 2-2, 3-1, 4-3

???????? TOTAL=28

54.求Ｎ個字符串的最長公共子串，Ｎ＜＝２０邓尤，字符串長度不超過２５５拍鲤。

例如：Ｎ＝３贴谎，由鍵盤依次輸入三個字符串為

????? What is local bus ?

????? Name some local buses.

????? local bus is a high speed I/O bus close to the processer.

則最長公共子串為"local bus"季稳。

(參看程序 9 )

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

個短劃都稱為一筆，即７有３筆景鼠，８有７筆等仲翎。請把這十個數(shù)字重新排列，要做到

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

７→３是允許的，７→２不允許浓恶。編程打印出所有可能的排列逐哈。

如：４１０７３９５６８２。

56. (Ｎ階梵塔) 有Ｋ根棒问顷，第一根上放Ｎ片大小不等的圓盤，并保持上小下大的

順序≠魇幔現(xiàn)將Ｎ片圓盤從第１根移至第Ｋ根杜窄，移動中均保持上小下大的順序，問最少

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

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

位：天）

任務? │Ｊ1? Ｊ2? Ｊ3? Ｊ4? Ｊ5? Ｊ6

??????? ─────┼───────────────

印刷車間│ ３? １２? ５?? ２?? ９? １１

裝訂車間│ ８? １０? ９?? ６?? ３? １

如何安排加工順序嘴瓤，使加工時間最少扫外。

58.將７萬元投資到Ａ，Ｂ廓脆，Ｃ三項目上筛谚，其利潤見下表：

投資額(萬元)│ １??? ２??? ３??? ４??? ５??? ６??? ７

??????? ──────┼────────────────────

項? Ａ? │0.11? 0.13? 0.15? 0.24? 0.24? 0.30? 0.35

Ｂ? │0.12? 0.16? 0.21? 0.25? 0.25? 0.29? 0.34

目? Ｃ? │0.08? 0.12? 0.20? 0.26? 0.26? 0.30? 0.35

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

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

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

的Ａ為根節(jié)點得到圖二所示的有根樹谓晌，以Ｂ為根節(jié)點得到圖三所示的有根樹，但從

無根樹的角度看癞揉，圖一纸肉、二溺欧、三是結(jié)構(gòu)相同的無根樹，同時無根樹的結(jié)構(gòu)與節(jié)點的

名稱無關毁靶。

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

根節(jié)點（子樹１??? 子樹２??? 子樹３...）

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

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

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

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

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

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

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

關緊要返吻，所有節(jié)點都以Ｐ表示，以后的各種輸出也采用這種形式乎婿。例如：輸入無根

樹的字符串形式：Ａ（Ｂ（ＣＤ（ＥＦ）））测僵，指定根節(jié)點為Ｄ，程序應能輸出

Ｐ（Ｐ（ＰＰ）ＰＰ）谢翎，Ｐ（ＰＰ（ＰＰ）Ｐ）捍靠，Ｐ（ＰＰＰ（ＰＰ））中的任意

一種即可。

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

無關，只考慮結(jié)構(gòu)褒侧。

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

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

根樹。

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

60.用Ｎ＊Ｎ（１＜＝Ｎ＜＝８）的格點陣代表海吊档，其中＊號代表島。給你一組編

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

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

“１２”，表示該行第一“島組”由一個島組成葡秒，第二“島組”由兩個島組成姻乓，而

第四列下面的“２３”則表示本列由兩個“島組”組成鞠抑，第一個“島組”由兩個島

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

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

為止学少，步驟如下：

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

每個信息塊組成為：

格點陣大小 (N)版确，以后是行的約束條件（Ｎ行的）扣囊，列的約束條件（Ｎ列的）,

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

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

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

（３）將重構(gòu)的地圖以ＡＳＣＩＩ文件形式輸出士修。每島以＊后加一個空格表示；

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

開；若一組已知條件畫不出地圖矩桂，用“ＮＯ? ＭＡＰ（占一行）表示沸移。由不同的信

息組求得的解用“ＮＥＸＴ? ＰＲＯＢＬＥＭ”（占一行表示）１＜＝Ｎ＜＝８.

61.一個餐廳在相繼的Ｎ天里，第 i 天需要 Ri 塊餐巾(i=1侄榴，2雹锣，...，N)癞蚕。餐廳

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

(1)購買新的餐巾蕊爵，每塊需Ｐ分；

(2)把用過的餐巾送到快洗部桦山，洗一塊需Ｍ天攒射，費用需Ｆ分(Ｆ＜Ｐ)醋旦；

(3)把餐巾送到慢洗部，洗一塊需Ｎ天(Ｎ＞Ｍ)会放，費用需Ｓ分(Ｓ＜Ｆ)饲齐。

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

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

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

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

Ｆ脓诡，Ｓ，和所需天數(shù)Ｍ媒役，Ｎ祝谚，輸出每天開始時需購新餐巾數(shù)，結(jié)束時送快酣衷，慢洗部

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

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

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

次只锻，最后返回城市Ａ，求一條距離最短的路線紫谷。

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

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

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

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

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

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

???? ┏━┯━┯━┓???????? ┏━┯━┯━┓???????? ┏━┯━┯━┓

┃? │? │? ┃???????? ┃? │? │? ┃???????? ┃? │Ｏ│? ┃

???? ┠─┼─┼─┨???????? ┠─┼─┼─┨???????? ┠─┼─┼─┨

┃? │? │? ┃???????? ┃? │Ｘ│? ┃???????? ┃? │Ｘ│? ┃

???? ┠─┼─┼─┨???????? ┠─┼─┼─┨???????? ┠─┼─┼─┨

???? ┃? │? │? ┃???????? ┃? │? │? ┃???????? ┃? │? │? ┃

???? ┗━┷━┷━┛???????? ┗━┷━┷━┛???????? ┗━┷━┷━┛

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

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

示的商和余數(shù)榛丢。

(參看程序 8 )

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

韧ε印Ｍ個字母的所有排列及排列總數(shù)晰赞。

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

超過２４０位掖鱼。

(參看程序 5 )

67. ( NOI'94.1_3 )一個實數(shù)數(shù)列共有Ｎ項，已知a(i)=(a(i-1)-a(i+1))/2+d援制，

（１〈i〈Ｎ）(N<60) , 鍵盤輸入Ｎ戏挡，d，a(1)晨仑，a(n)褐墅，m，輸出 a(m)洪己。

68. ( NOI'94.1_4 )鍵盤輸入一個高精度的正整數(shù)Ｎ妥凳，去掉其中任意Ｓ個數(shù)字后

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

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

的正整數(shù)澄耍。（Ｎ不超過２４０位）

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

分別稱之為表１和表２，要求編程將表１和表２下述規(guī)則合并成表３：

規(guī)則：表１在表２之上齐莲，表１和表２的左邊框?qū)R痢站，將表１的最低行與表２的

最頂行合并。例：在你的Ｃ盤根目錄下有兩個文件 t0.1 和 t0.2选酗，分別存放上述

的表１和表２阵难，經(jīng)上述規(guī)則合并后得到表３，放在文件中芒填。三張表見下圖：

? ┎─┰─┰─┰─┒??????????????????????????????? ┎─┰─┰─┰─┒

? ┃? ┃? ┃? ┃? ┃??????? ┎┰─┰─┒??????????? ┃? ┃? ┃? ┃? ┃

? ┠─╂─╂─╂─┨??????? ┃┃? ┃? ┃??????????? ┠─╂─╂─╂─┨

? ┃? ┃? ┃? ┃? ┃??????? ┖┸─┸─┚??????????? ┃? ┃? ┃? ┃? ┃

? ┖─┸─┸─┸─┚??????????????????????????????? ┠┰┸┰┸┰┸─┚

??????????????????????????????????????????????????? ┃┃? ┃? ┃

??????????????????????????????????????????????????? ┖┸─┸─┚

表１??????????????????? 表２???????????????????? 表３

編程要求：

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

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

(3)將表１和表２規(guī)則合并成表３朱庆，并顯示之盛泡。

(4)所有制表符的ＡＳＣＩＩ碼應由選手自己從給出的示例文件中截取。

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

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

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

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

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

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

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

例:??????????????????????????????? ┃????? ┃????? ┃????? ┃

鍵盤輸入:????????????????????????? ┃????? ┃????? ┃????? ┃

???????? 3??????????????????????? d?? ━╋━??? ┃????? ┃????? ┃

???????? acb????????????????????? c?? ━╋━??? ┃????? ┃????? ┃

則一個正確的輸出文件???????? b?? ━╋━??? ┃????? ┃????? ┃

可以是:???????????????????????? a?? ━╋━??? ┃????? ┃????? ┃

????? c? A? B?????????????????????? ━━┻━━━┻━━━┻━━━┻━

????? b? A? C?????????????????????????? A?????? B?????? C?????? D

????? a? A? D

????? b? C? D

????? c? B? D

71. (最長連線) 設有一個 N×N 的方格圖形娱颊，且 N 為 3 的倍數(shù)傲诵。要求在圖形中

存放 0 或 1，相鄰的 1 可以連成一條連線箱硕，連接的方法可以是行拴竹，也可以是列；

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

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

１? ２? ３? ４? ５? ６

?????????????? ┌─┬─┬─┬─┬─┬─┐

１? │１│１│１│０│０│１│

?????????????? ├─┼─┼─┼─┼─┼─┤

２? │１│１│０│１│１│１│

?????????????? ├─┼─┼─┼─┼─┼─┤

３? │０│０│０│１│０│１│

?????????????? ├─┼─┼─┼─┼─┼─┤

４? │１│１│０│１│１│１│

?????????????? ├─┼─┼─┼─┼─┼─┤

５? │０│１│０│０│０│０│

?????????????? ├─┼─┼─┼─┼─┼─┤

６? │１│１│１│１│０│０│

?????????????? └─┴─┴─┴─┴─┴─┘

在該圖中斑响，包含有如下的一些連線：

１←１←１??????? １←１???????????????????? １

???? ↓??????????????? ↓???????????????????????? ↓

１→１??????????? １???????????????? １→１? １

?????????????????????? ↓???????????????? ↑????? ↓

１→１→１???????? １????? １

????????????????????????????????????????? ↑????? ↓

１←１←１

在以上的連線中菱属，最長的連線為：??? 表示方法：

１?????????????????????? 最長連線長度：LMAX=9

↓連線：(1,6)→(2,6)→

１→１? １???????????????????????????? (3,6)→(4,6)→

???? ↑????? ↓???????????????????????????? (4,5)→(4,4)→

１????? １???????????????????????????? (3,4)→(2,4)→

???? ↑????? ↓???????????????????????????? (2,5)

１←１←１????????????????? 連線的表示不是唯一的，僅給出一種即可舰罚。

72. (NOI'95.1_2)　在一個園形操場的四周擺放 N 堆石子(N≤100)纽门， 現(xiàn)要將石子

有次序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并成新的一堆营罢，并將新的一堆

的石子數(shù)赏陵，記為該次合并的得分。

　　編一程序饲漾，由文件讀入堆數(shù)N及每堆的石子數(shù)(≤20)蝙搔，

　　①選擇一種合并石子的方案, 使得做N-1次合并, 得分的總和最小;

②選擇一種合并石子的方案, 使得做N-1次合并, 得分的總和最大.

例如, 圖 2-1 所示的4堆石子,每堆的石子數(shù)(從最上面的一堆數(shù)起, 順時針數(shù))

依次為4? 5? 9? 4.則 3 次合并得分總和最小的方案為圖2-2,得分總和最大的方案

為圖2-3.

(加圖)

　　輸入數(shù)據(jù):

文件名由鍵盤輸入考传，該文件內(nèi)容為;

第一行為石子堆數(shù) N;

第二行為每堆的石子數(shù), 每兩個數(shù)之間用一個空格符分隔

輸出數(shù)據(jù):

輸出文件名為 OUTPUT.TXT

　　第1至 N-1 行為得分最小的合并過程. 每行包含兩個數(shù), 表示應該合并的兩

堆石子的數(shù)目, 小數(shù)在前, 大數(shù)在后, 第 N 行為合并成一堆后的最小得分總和;

第 N+1 行為空行, 第 N+2 至 2N+1 行為得分最大合并過程(格式同前). 第 2N+2

行為最大得分總和.

73. (NOI'95.1_4) N位由 0 和 1 組成的字符串 A吃型、B 可分別表示為

　　A＝ａNａN-1…ａi…ａ2ａ1

　　B＝ｂNｂN-1…ｂi…ｂ2ｂ1

其中, ａi＝0或1, ｂi＝0或1,?? 1≤i≤N, N≤15.

如果存在某一位j(j∈1…N), 在該位上兩串不同, 即ａj≠ｂj, 而其余N-1位

上的兩串相同, 即ａi＝ｂi(i∈1…N，i≠j), 則稱 A僚楞、B 兩串“互鄰”勤晚。

　　比如，在N＝4時, A＝1100, B＝1000, A泉褐、B 兩串“互鄰”, 而 C＝1100, D＝

1010, C赐写、D 兩串不“互鄰”。

編程要求：

尋找一個含有 2N 個上述01串的序列, 該序列滿足以下要求:

①組成該序列的每一個01串都與其它串不同;

②第k個串與第k-1個串有“互鄰”關系膜赃，2≤k≤2N;

③該序列首項由輸入指定.

例如 N=2, 指定首項為01, 則一個滿足上述要求的序列為

??? 01? 11? 10? 00

　　輸入數(shù)據(jù)┏━━━━━━┓? ┏━━━━━┓

文件名由鍵盤輸入???????????????? ┃EXAMPLE4.TXT┃? ┃MODEL4.TXT┃

該文件共有兩行?????????????????? ┠──────┨? ┠─────┨

第一行為? N????????????????????? ┃2?????????? ┃? ┃2???????? ┃

第二行為指定的序列首項?????????? ┃01????????? ┃? ┃01??????? ┃

???????????????????????????????????? ┃??????????? ┃? ┃11??????? ┃

　　輸出數(shù)據(jù)┗━━━━━━┛? ┃10??????? ┃

輸出文件為 OUTPUT.TXT????????????????????????????? ┃00??????? ┃

第一行為? N??????????????????????????????????????? ┃????????? ┃

第二行至第2N+1行依次輸出序列的每一個串.??????????? ┗━━━━━┛

　　輸入輸出舉例

參考輸入文件: EXAMPLE4.TXT

參考輸出文件: MODEL4.TXT

74. (NOI'95.1_5) m挺邀、n為整數(shù)，且滿足下列兩個條件：

　　① m端铛、n∈｛1, 2, …, k｝, (1≤k≤109)

② (n^2－m*n－m^2)^2＝1

編一程序, 由鍵盤輸入k, 求一組滿足上述兩個條件的 m泣矛、n, 并且使m^2＋n^2

的值最大.

例如, 若 k＝1995, 則 m＝987, n＝1597 時, 則 m、n 滿足條件, 且可使

m^2＋n^2的值最大.

75. (錢幣系統(tǒng)問題) 某錢幣系統(tǒng)由 k (k≤20) 種硬幣組成, 幣值依次為 a[1],

a[2],...,a[k],其中 a[i] (i=1,2,...,k) 為互不相同的正整數(shù), 且依降序排列,

a[1]≤200.給定某整數(shù)幣值 n(n≤3000), 要求用最少枚數(shù)的硬幣表示這個幣值.

輸入: 用文件輸入已知數(shù)據(jù), 格式為:

第 1 行: k (硬幣種數(shù))

第 2 行: a[1] a[2] ... a[k] (各幣值用空格隔開,已按降序排列好)

第 3 行: n (給定的幣值)

輸出: 直接在屏幕上輸出結(jié)果. 如果該錢幣系統(tǒng)無法表示幣值 n,應輸出'No',

否則按以下格式輸出:

第 1 行: 最少錢幣枚數(shù) r.

第 2 行: 輸出若干形如 m*n 的表達式, m 為幣值, n為使用該幣值的枚數(shù).

各式第 2 個因子之和應等于 r, 各式乘積之和應等于 n.

例: 設 (a[1],a[2],a[3])=(5,2,1),? n=12,? 則應輸出

?????? 3

?????? 5*2? 2*1.

76. (省刻度尺問題)給定長度為 L 的直尺, L 為整數(shù), 且L≤40. 為了能一次直接

量出? 1,2,...,L 的各種長度, 該尺內(nèi)部至少要有多少條刻度 ?? 請輸出最少刻度

數(shù)( 不含兩端點)及每個刻度的位置. 測量長度時可利用兩端點, 其位置分別為 0,

?L.

輸入: 由鍵盤輸入 L.

輸出: 用文本文件按以下格式輸出結(jié)果(文件名: ANS2.TXT):

第 1 行: S ( 最少刻度數(shù) )

第 2 行: 尺內(nèi) S 個刻度的位置

第 3 行至第 L+2 行: 每行輸出 3 個用空格隔開的整數(shù) t m n, 其中

1≤t≤L為要測量的各長度, m,n 依次為該長度的起止刻度 (m<n).

例: 如果 L=6, 則一個正確的輸出是:

?????? 2

1 4提示:? (1) 最少刻度數(shù) S 應滿足:

?????? 1 0 1???????????????????? C[S+2,2]=(S+2)*(S+1)/2≥L.

2 4 6???????????????????????? (2)除兩端點外, 第一個刻度可取為

3 1 4???????????????????? A[1]=1,第二個刻度可在 1, L-2, L-1 這

4 0 4三個數(shù)中選取.

?????? 5 1 6

?????? 6 0 6

————————————————