C++入門必做題 題目 共76道題
以下是C++入門必做題所有題目，共76道題
關(guān)于字體顯示的說明：
由于字體格式限制，部分題目的英文部分有偏移現(xiàn)象。
解決辦法：將題目拷貝到記事本，字體設(shè)置為‘Fixedsys’即可。
1.給定等式? A B C D E???? 其中每個字母代表一個數(shù)字，且不同數(shù)字對應(yīng)不
D F G同字母。編程求出這些數(shù)字并且打出這個數(shù)字的
+????? D F G算術(shù)計算豎式。
???????????? ───────
??????????????? X Y Z D E
2.Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名學(xué)生有可能參加計算機(jī)競賽，根據(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.輸入一個十進(jìn)數(shù)，將其轉(zhuǎn)換成 N 進(jìn)制數(shù)（0<N<=16)。
6.矩陣中填數(shù). 當(dāng)給出 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ù)Ｘ，Ｙ，將Ｘ，Ｙ化為二進(jìn)制數(shù)，然后將這兩個二進(jìn)制數(shù)作二進(jìn)
制加法運(yùn)算，再將結(jié)果化為十進(jìn)制數(shù)輸出。
9.四人玩火柴棍游戲，每一次都是三個人贏，一個人輸。輸?shù)娜艘蹿A者手中的火柴
數(shù)進(jìn)行賠償，即贏者手中有多少根火柴棍，輸者就賠償多少根?，F(xiàn)知道玩過四次后，
每人恰好輸過一次， 而且每人手中都正好有１６根火柴。問此四人做游戲前手中各有
多少根火柴? 編程解決此問題。
10.如圖１所示，編寫程序計算?????????????? ┎┰┰┰┰┰┰┰┰┰┒
大大小小正方形共有多少？當(dāng)最小????????? ┠╂╂╂╂╂╂╂╂╂┨
正方行邊長為１時，它們的總面積????????? ┠╂╂╂╂╂╂╂╂╂┨
共為多少？????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨
??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨
??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨
??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨
??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨
??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨
??????????????????????????????????????????? ┠╂╂╂╂╂╂╂╂╂┨
??????????????????????????????????????????? ┖┸┸┸┸┸┸┸┸┸┚
11.巧排數(shù)字。將１、２、．．．、２０這２０個數(shù)排成一排，使得相鄰的兩個數(shù)之
和為一個素數(shù)，且首尾兩數(shù)字之和也為一個素數(shù)。編程打印出所有的排法。
12.下圖是一個集裝箱倉庫，陰影部分表示有集裝箱存放不能通過，無陰影處為臨時通
道。當(dāng)有人要從入口處到達(dá)出口處時，必須尋找可通過路線，請你找出可完成這個過程
的最方便（即用最短路線）到達(dá)出口處的路徑。
┎┰┰┰入口┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┰┒
????????? ┠╂╂╂──╂╂╂╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂╂┸┸╂╂╂┨
????????? ┠╂╂╂──╂┸┸╂──╂┰┰╂┰┰╂──╂╂╂╂──╂╂╂┨
????????? ┠╂╂╂──╂┰┰╂┰┰╂╂╂╂╂╂╂──╂┸┸╂──╂╂╂┨
????????? ┠╂╂╂──╂╂╂╂╂╂╂╂╂╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂┨
????????? ┠╂╂╂──╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂┸┸╂╂╂┨
????????? ┠╂╂╂──╂┰┰╂┰┰╂┰┰╂──╂┰┰╂──╂┰┰╂╂╂┨
????????? ┠╂╂╂──╂╂╂╂╂╂╂╂╂╂──╂╂╂╂──╂╂╂╂╂╂┨
????????? ┠╂╂╂──╂╂╂╂┸┸╂┸┸╂──╂╂╂╂──╂┸┸╂╂╂┨
????????? ┠╂╂╂──╂╂╂╂┰┰╂┰┰╂┰┰╂╂╂╂┰┰╂──╂╂╂┨
┖┸┸┸──┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸┸出口┸┸┸┚
13.有N個硬幣（N為偶數(shù)）正面朝上排成一排，每次將 N-1 個硬幣翻過來放在原位
置， 不斷地重復(fù)上述過程，直到最后全部硬幣翻成反面朝上為止。編程讓計算機(jī)把
翻幣的最簡過程及翻幣次數(shù)打印出來（用＊代表正面，O 代表反面）。
14.有黑白棋子各有Ｎ個（分別用＊和Ｏ代替），按下圖方式排列
＊＊＊．．．＊＊＊ＯＯＯ．．．ＯＯＯ
Ｎ個黑棋??????????? Ｎ個白棋
允許將相鄰兩個棋子互換位置，最后使隊形成黑白交替排列，試編程實現(xiàn)該操作。
15.已知６個城市，用ｃ[i,j]表示從ｉ城市到城市ｊ是否有單向的直達(dá)汽車
（１=<ｉ〈＝６，１〈＝ｊ〈＝６）, c[i,j]=1 表示城市ｉ到城市ｊ有單向直達(dá)汽
車； 否則 ｃ[i,j]＝0.? 試編制程序，對于給出的城市代號ｉ，打印出從該城市出
發(fā)乘車（包括轉(zhuǎn)車）可以到達(dá)的所有城市。
16.設(shè)有８枚硬幣ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，其中有一枚硬幣是偽造的。
真?zhèn)斡矌诺膮^(qū)別僅是重量不同，可能重，可能輕。今要求以天平為工具，用最少的
比較次數(shù)挑出偽造硬幣，并鑒定它是重還是輕。
17.編寫一個程序，當(dāng)輸入不超過６０個字符組成的英文文字時，計算機(jī)將這個句子
中的字母按英文字典字母順序重新排列，排列后的單詞的長度要與原始句子中的長度
相同。例如：
輸入：
ＴＨＥ ＰＲＩＣＥ ＯＦＢＲＥＡＤ ＩＳ ￥１ ２５ ＰＥＲ ＰＯＵＮＤ
輸出：
ＡＢＣ ＤＤＥＥＥ ＥＦＨＩＩＮＯ ＯＰ ￥１ ２５ ＰＰＲ ＲＲＳＴＵ
并且要求只對Ａ到Ｚ的字母重新排列，其它字符保持原來的狀態(tài)。
18.在一線性七個格位置的圖上有兩種不同顏色的棋子Ａ，Ｂ. 排列如下圖所示，中間
格的位置為空。
????????? ┎─┰─┰─┰─┰─┰─┰─┒
┃Ａ┃Ａ┃Ａ┃? ┃Ｂ┃Ｂ┃Ｂ┃
????????? ┖─┸─┸─┸─┸─┸─┸─┚
要求將Ａ，Ｂ的現(xiàn)行位置交換,形成下圖中的排列：
????????? ┎─┰─┰─┰─┰─┰─┰─┒
┃Ｂ┃Ｂ┃Ｂ┃? ┃Ａ┃Ａ┃Ａ┃
????????? ┖─┸─┸─┸─┸─┸─┸─┚
移動棋子的條件：
(1)每個格中只準(zhǔn)放一個棋子。
(2)任意一個棋子均可移動一格放入空格內(nèi)。
(3)一方的棋子均可跳過另一方的一個棋子進(jìn)入空格。
(4)任何棋子不得跳躍兩個或兩個以上棋子（無論顏色同異）
(5)任何一個顏色棋子只能向前跳，不準(zhǔn)向后跳。
編程完成有關(guān)的移動，并且完成具有２Ｎ＋１個格子的情形. 其中兩種顏色各有
Ｎ個棋子,且中間為空格.
19. (背包問題) 有 N 件物品 d1，......dN，每件物品重量為 W1，..., WN
(Wi > 0)， 每件物品價值為 V1，......VN (Vi>0)。用這N件物品的某個子集
填空背包，使得所取物品的總重量<=TOTAL，并設(shè)法使得背包中物品的價值盡可
能高。
20. (Ｎ皇后) 在國際象棋的棋盤上放置Ｎ個皇后，使其不能互相攻擊，即任意
兩個皇后不能處在棋盤的同一行，同一列，同一斜線上，試問共有多少種擺法？
21.請設(shè)計一個程序，由計算機(jī)把１..￣.８的八個自然數(shù)填入圖中，使得橫、
豎、對角任何兩個相鄰的小方格中的兩個數(shù)是不連續(xù)的。(下圖右側(cè)的 4 個圖
為禁止的情形).
??????????? ┌─┐????????? ┌─┐?????????????? ┌─┐
│? │????????? │４│?????????????? │８│
??????? ┌─┼─┼─┐????? └─┼─┐?????? ┌─┼─┘
│? │? │? │????????? │５│?????? │７│
??????? ├─┼─┼─┤????????? └─┘?????? └─┘
??????? │? │? │? │????? ┌─┐
└─┼─┼─┘????? │６│?????????? ┌─┬─┐
│? │????????? ├─┤?????????? │１│２│
└─┘????????? │７│?????????? └─┴─┘
??????????????????????????? └─┘
22.在一個４＊４的小方格（如圖所示）中放置８個＊號，使得每行每列放且
僅放兩個＊號。
????????? ┌─┬─┬─┬─┐
│＊│＊│? │? │
????????? ├─┼─┼─┼─┤
│＊│? │＊│? │
????????? ├─┼─┼─┼─┤
│? │＊│? │＊│
????????? ├─┼─┼─┼─┤
│? │? │＊│＊│
????????? └─┴─┴─┴─┘
求出所有的基本解。
23. (覆蓋問題) 有邊長為Ｎ（Ｎ為偶數(shù)）的正方形，請你用Ｎ＾２／２個長為２,
寬為１的長方形，將它全部覆蓋。編程打印出所有覆蓋方法。如：Ｎ＝４
??? ┌─┬──┬─┐??????????? ┌──┬──┐
│? │??? │? │１２２４?? │??? │??? │? １１２２
??? │? ├──┤? │??????????? ├──┼──┤
│? │??? │? │１３３４?? │??? │??? │? ３３４４
??? ├─┼──┼─┤??????????? ├──┼──┤
│? │??? │? │５６６８?? │??? │??? │? ５５６６
??? │? ├──┤? │??????????? ├──┼──┤
│? │??? │? │５７７８?? │??? │??? │? ７７８８
??? └─┴──┴─┘??????????? └──┴──┘
24.某地街道把城市分割成矩形方格，每一方格叫作塊，某人從家中出發(fā)上班，
向東要走Ｍ塊，向北要走Ｎ塊，（見圖）。請設(shè)計一個程序，由計算機(jī)尋找并
打印出所有的上班的路徑。
單位
?????????? ┬?? ┌─┬─┬─┬─┬─┬─┬─┐
?????????? │?? │? │? │? │? │? │? │? │
?????????? │?? ├─┼─┼─┼─┼─┼─┼─┤
?????????? ↓?? │? │? │? │? │? │? │? │
Ｎ?? ├─┼─┼─┼─┼─┼─┼─┤
?????????? ↑?? │? │? │? │? │? │? │? │
?????????? │?? ├─┼─┼─┼─┼─┼─┼─┤
?????????? │?? │? │? │? │? │? │? │? │
?????????? ┴?? └─┴─┴─┴─┴─┴─┴─┘
家?? ├─────→Ｍ←─────┤
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)????????????????????????????? 目標(biāo)狀態(tài)
以左圖為初始狀態(tài)，右圖為目標(biāo)狀態(tài)，請找出從初始狀態(tài)到目標(biāo)狀態(tài)的滑牌移步
序列，具體要求：
（１）輸入初始狀態(tài)和目標(biāo)狀態(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ù)應(yīng)有查錯和示錯功能；
（２）實現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)換（如不能實現(xiàn)，程序應(yīng)輸出不能實現(xiàn)
的提示信息）；
（３）輸出結(jié)果，每移動一步都必須在屏幕上顯示:
ａ、移動每一步時的序號，最后一步的序號即為移動總步數(shù)；
ｂ、每一步移動后以３＊３表格形式顯示狀態(tài)。
（４）要求能使移動步數(shù)盡可能少；
27.給出一個有８個格子的表格，除３個格子外，每個格子中可放入一個數(shù)字，這
些數(shù)字取自自然數(shù) 1 到 5，放入格子中的數(shù)字不得相同，剩余的３個格子是空格
（用Ｏ表示）。圖１是一個放數(shù)字與空格的特例?，F(xiàn)要求編程實現(xiàn)從初始表格狀態(tài)
變化到目標(biāo)表格狀態(tài)。初始狀態(tài)和目標(biāo)狀態(tài)都是可變的（圖１，圖２所示的狀態(tài)僅
是一個特例），由鍵盤輸入格子中的數(shù)字（０￣５）。
移動規(guī)則：
(1)每一個數(shù)字只可以通過虛線移入相鄰空格。如圖１中，允許“２”左移入空
格，而不能上移進(jìn)入上面空格。
(2)只允許水平移動或垂直移動，不允許斜移。
(3)移動后，該數(shù)字原先所在的格子變成空格。
實現(xiàn)目標(biāo)：
(1)輸入初始表格狀態(tài)和目標(biāo)表格狀態(tài)的數(shù)據(jù)。
①分別在一行內(nèi)輸入上述兩項數(shù)據(jù)；
②對輸入的數(shù)據(jù)應(yīng)有查錯和報錯功能；
(2)實現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)換（如不能實現(xiàn)也應(yīng)給出必要的說明）。
(3)顯示結(jié)果：每移動一步都應(yīng)在屏幕上有如下信息：
①顯示每一步移動的序號。所以最后一步的序號就是移動的總步數(shù)。
②顯示每一步移動前后的表格狀態(tài)。
(4)以最少的移動步數(shù)達(dá)到目標(biāo)。
????????????? ┎─┰─┰─┒????????????????????????? ┎─┰─┰─┒
┃３┃４┃０┃????????????????????????? ┃０┃０┃０┃
????????? ┎─╂─╂? ╂─╂─┒????????????????? ┎─╂─╂? ╂─╂─┒
┃０? １? ０? ２? ５┃????????????????? ┃１? ２? ３? ４? ５┃
????????? ┖─┸─┸─┸─┸─┚????????????????? ┖─┸─┸─┸─┸─┚
圖 １０－１???????????????????????????? 圖 １０－２
初始狀態(tài)Ａ????????????????????????????? 目標(biāo)狀態(tài)Ｂ
28.ｎ枚銀幣 C1,C2,...,Cn, 其中有一塊不合格,不合格的銀幣比正常的要重。現(xiàn)用
一天平找出不合格的一塊，要求在最壞的情況下，用的天平次數(shù)最少。
29.把一段文章按要求排版。文章的輸入方式為：由鍵盤輸入一段以回車符結(jié)束的文章
（最大長度 2000 個字符）。排版時以單詞為基本單位。單詞由不含空格的任意字符組
成，是長度小于２０個字符的串?？崭穹欠指魡卧~的唯一字符，在輸入時連續(xù)的空格
符在處理時應(yīng)先化簡為單個空格符。在排版前應(yīng)先輸入，排版后每行的字符數(shù)為Ｎ，排
版后將整理好的文章按行輸出。輸出時不能將一個完整的單詞截斷，并要求輸出的總行
數(shù)最小。將每個不足Ｎ個字符的行用空格補(bǔ)足，填充空格符的方式有以下三種。
１）將填充的空格符置于每行的末尾，并要求每行的起始為單詞。
２）將填充的空格符置于每行的開始，并要求每行的末尾為單詞。
３）將填充的空格符平均分配在每行中，并保證行的起始和末尾均為單詞。
30.某機(jī)要部門安裝了電子鎖。Ｍ個工作人員每人發(fā)一張磁卡，卡上有開鎖的密碼特征。
為了確保安全，規(guī)定至少要有Ｎ個人同時使用各自的磁卡才能將鎖打開。問電子鎖上至
少要有多少種特征? 每個人的磁卡上至少要有多少特征? 如果特征的編號以小寫英文字
母表示，將每個人的磁卡的特征編號打印出來，要求輸出的電子鎖的總特征數(shù)最少。
設(shè) 3<=M<=7, 1<=N<=4, Ｍ與Ｎ由鍵盤輸入，工作人員編號用 1#,2#,...表示.
31.甲乙兩人從２４枚棋子中輪流取子，甲先取，規(guī)定每次所取的枚數(shù)不能多于上
一個人所取的枚數(shù)，也不可不取。
（１）甲第一次取多少枚才能保證甲取得最后一枚，當(dāng)然，他也不能第一次就把
所有棋子都取走。
（２）討論棋子總數(shù)Ｎ（一定是偶數(shù)）從６到３０的各種情況。討論內(nèi)容包括：
對各個Ｎ，是否存在一個小于Ｎ的枚數(shù)Ｍ，甲第一次?。兔逗缶湍鼙ＷC甲如果策略
正確,一定能取到最后一枚棋子。
32. (走棋 ) 一個４＊４的方陣如圖。有一個小卒從上往下走。走至格子１后就
不能走動，走至０后，若下方為１，則向左或向右走，下方為０，則向下走。求所
有走法。
????????????? ┌─┬─┬─┬─┐
????????????? │1 │0 │0 │0 │
????????????? ├─┼─┼─┼─┤
????????????? │0 │0 │1 │0 │
????????????? ├─┼─┼─┼─┤
????????????? │0 │1 │0 │0 │
????????????? ├─┼─┼─┼─┤
????????????? │1 │0 │0 │0 │
????????????? └─┴─┴─┴─┘
33. (野人與傳教士 ) 設(shè)有三個傳教士和三個野人來到河邊，打算乘一只船從右
岸渡到左岸去。該船最大負(fù)載能力為兩人，在任何時候，如果野人人數(shù)超過傳教士
人數(shù)，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡過
河去呢？
34. (取棋子 ) 設(shè)有Ｎ顆棋子，由人和計算機(jī)輪流從中取走若干顆。每方每次最
多?。祟w，最少取１顆 (Ｋ值不能超過總數(shù)的一半，也不能小于１)。試編寫一程
序使計算機(jī)有較多的獲勝機(jī)會。
屏幕輸入提示:
(1)輸入競賽規(guī)則：A. 取最后一顆棋子的那一方為敗.
B.取最后一顆棋子的那一方為勝.
(2)總共有多少顆棋子？
(3)一次最多取幾顆？
(4)誰先?。?/p>
(5)每個回合都應(yīng)顯示: A. 你取幾顆？
B.我取走......顆，還剩......顆.
(6)競賽過程中發(fā)生違例時，打印出:? 競賽無法進(jìn)行下去！
(7)競賽結(jié)束后打?。?/p>
I win!（我勝?。┗? You win!（你勝?。?。
35. ( Grundy博弈 ) 在兩位選手面前放著一堆銅幣。第一位選手把原堆分成不相
等的兩堆。然后每個選手輪流地這樣做，即當(dāng)輪到某一方分時, 他把已被分開的任
一堆再分成不相等的兩堆。博弈這樣一直進(jìn)行下去，直到每一堆都只剩下一個或兩
個銅幣為止，這時博弈結(jié)束。規(guī)定首先遇到這種情況的選手為輸。
36.猴子選大王：
① N只猴子站成一行，每隔 M 只從頭到尾報數(shù)，反復(fù)進(jìn)行,報過數(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,當(dāng) K1=3,K2=3 時，K1*K2=9 為最大
38.有一集合中有 N 個元素，每個元素均為自然數(shù)。給定一個 total （假設(shè)每個
元素值均小于total)，求滿足條件的所有子集，子集中各元素之和應(yīng)等于total。
39.一個集合滿足如下條件：
(1)１是集合的元素；
(2)若 P 是集合的元素，則 2*P+1，4*P+5 也是集合的元素。
求：此集合中最小的 K 個元素。
?、?對ＡＢＣ作全排列而得的六個三位數(shù)之和為 2886。
40.一個整型變量只能用來存貯較小的 N！的值，當(dāng) N 較大時，可將階乘值中的
每一個數(shù)字放在一個一維數(shù)組的一個元素中。使用這方法，打?。?/p>
①Ｎ！的值；
②Ｎ?。停。ǎ停荆危?/p>
③Ｎ?。?！
41. (合并鏈表) 已知兩個鏈表 AN={a1,a2,...an}, BN={b1,b2,...bm}, 將其合并
為一個鏈表 CN={a1,b1,a2,b2,...}
42. (算術(shù)表達(dá)式求值) 輸入一個由數(shù)字、+，-，*，/ 及括號組成的算術(shù)表達(dá)式，
求其值。
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, 運(yùn)算結(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é)果應(yīng)為：5*x^6-7*x^4+4*x^3+50*x^2+4*x+1.
45. (數(shù)列的最小代價) 給定一個正整數(shù)序列，例如：4,1,2,3, 不改變數(shù)的位置把
它們相加， 并且由括號來標(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ù)列的一個代價。對于另一種算法:
(4+((1+2)+3))=(4+((3+3))=(4+(6))=10,得到數(shù)列的另一個代價為：3+6+10=19.
若給出 N 個數(shù)的數(shù)列，求出此數(shù)列的最小代價。
46.設(shè)有一個字符串，長度小于 100，且全部以英文字母組成。對字串中的每個字
母可用 0,1,2 三個數(shù)字進(jìn)行編碼，且數(shù)字可以重復(fù)使用。
程序要求：(1) 輸入字符串，并能判斷輸入是否有錯；
(2)輸出對應(yīng)的編碼表及碼長，要求字串的編碼總長度為最短；
(3)根據(jù)上述編碼表，給出一些編碼，然后求出其原字符串。
例如：輸入的字符為:ABCBAAADDEF
其對應(yīng)的編碼表為：
???????? A:?? 2??????????????? B:? 10
???????? C:? 11??????????????? D:? 12
???????? E:? 00??????????????? F:? O1
對應(yīng)的編碼為：210111022212120001?????? 總碼長為：18
根據(jù)該編碼，給出編碼:010001121110222?? 則輸出字串:FEFDCBAAAA.
47.某些密碼由 N 個英文字母組成(N〈26), 每個字母的平均使用率為:W1,W2,...
,Wn,要求編程完成下列任務(wù)：
①鍵入英文字母及個數(shù)；
②鍵入Ｎ個英文字母的使用頻率；
③用二進(jìn)制數(shù)對該Ｎ個英文字母進(jìn)行編碼（最短，無二義性）；
④鍵入字母短文（單詞用空格區(qū)分），輸出相應(yīng)編碼；
⑤鍵入二進(jìn)制編碼短文，輸出譯文。
48.將４個紅球，３個白球與３個黃球排成一排，共有多少種排法？
49.有面值為 M..N 的郵票各一枚，共能拼出多少不同的面額。
50.有一個四階方陣，隨機(jī)產(chǎn)生 1..16 這 16 個自然數(shù)（不重復(fù)），依次填入每
個方格中。要求用最少的對調(diào)次數(shù)，使每一行、每一列以及對角線上的四個數(shù)之和
均相等。打印每一次對調(diào)的過程。
51.微型藍(lán)球賽. 甲,乙兩隊進(jìn)行藍(lán)球比賽,結(jié)果甲隊以S:T 獲勝.(T<S<=10, S,T
由鍵盤輸入). 比賽中, 甲隊得分始終領(lǐng)先(嚴(yán)格大于乙隊). 規(guī)定以任何方式進(jìn)一
球都只得一分. 編程序打印該比賽的每一種可能的不同的得分過程, 以及所有不同
過程的總數(shù).
52.求兩整型數(shù)組錯位相加的最大面積.
設(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 的面積最大.
例: 設(shè) N=3, A1=(3,7,2), A2=(-5,7,-4), 則應(yīng)考慮 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 個人完成, 每人都完成一
件,且只完成一件, 每人完成不同工作的時間不同. 試設(shè)計一種分配工作方案, 使
完成 N 件工作所需的總時間最少.
原始數(shù)據(jù)由文本文件 EXAM1.TXT 給出, 其格式如下:
第 1 行:??????? 工作任務(wù)數(shù)(N)
第 2 -- N+1 行: 第 i+1 行為第 i 個人完成各件工作所需的時間. 以上各數(shù)
均為不超過 1000 的正整數(shù).
計算結(jié)果可直接在屏幕上輸出: 第一行為工作分配方案, 共 N 組, 每組數(shù)據(jù)的
形式為 a-b, 其中 a 為工作人員編號, b 為他應(yīng)完成的工作序號.
例: 設(shè) 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. (Ｎ階梵塔) 有Ｋ根棒，第一根上放Ｎ片大小不等的圓盤，并保持上小下大的
順序?，F(xiàn)將Ｎ片圓盤從第１根移至第Ｋ根，移動中均保持上小下大的順序，問最少
移幾次方得結(jié)果，求出移動方案。
57.某一印刷廠有六項加工任務(wù)，對印刷車間和裝訂車間所需時間見下表（時間單
位：天）
任務(wù)? │Ｊ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é)點之間只有相鄰關(guān)系。如圖一所示，是一棵有七個節(jié)點的無根樹，以圖一
的Ａ為根節(jié)點得到圖二所示的有根樹，以Ｂ為根節(jié)點得到圖三所示的有根樹，但從
無根樹的角度看，圖一、二、三是結(jié)構(gòu)相同的無根樹，同時無根樹的結(jié)構(gòu)與節(jié)點的
名稱無關(guān)。
有根樹可以用字符串的形式表示，其遞歸表示方法是：
根節(jié)點（子樹１??? 子樹２??? 子樹３...）
圖一，圖二的有根樹可表示為 A(B(CF(EGD))) 和 B(ACF(EGD))。由于子樹的表示
順序可以不同，所以一棵有根樹可以有多種表示方法，如圖三又可表示成
B(F(EGD)CA)或 B(ACF(DE(G)) 等。表示無根樹時，可以以它任一節(jié)點為根節(jié)點，
將其看作有根樹，從而可以利用有根樹的字符串表示形式來表示無根樹。
任務(wù)一：由鍵盤讀入一個字符串表示的無根樹，無根樹的各節(jié)點的名稱用互不
相同的大寫英文字母表示。由用戶輸入一個節(jié)點的名稱，程序應(yīng)能夠輸出一種以該
節(jié)點為根節(jié)點的字符串形式。程序輸出無根樹的字符串形式時，各個節(jié)點的名稱無
關(guān)緊要，所有節(jié)點都以Ｐ表示，以后的各種輸出也采用這種形式。例如：輸入無根
樹的字符串形式：Ａ（Ｂ（ＣＤ（ＥＦ））），指定根節(jié)點為Ｄ，程序應(yīng)能輸出
Ｐ（Ｐ（ＰＰ）ＰＰ），Ｐ（ＰＰ（ＰＰ）Ｐ），Ｐ（ＰＰＰ（ＰＰ））中的任意
一種即可。
任務(wù)二：輸入兩個串表示的無根樹，判斷其結(jié)構(gòu)是否一樣。注意它與節(jié)點名稱
無關(guān)，只考慮結(jié)構(gòu)。
任務(wù)三：輸入無根樹的總枝數(shù)Ｎ（1<=N<=11），輸出所有枝數(shù)為Ｎ的互不相同
的無根樹，并記錄總數(shù)。以字符串形式輸出，例如：N=5 時共有６種不同結(jié)構(gòu)的無
根樹。
注意：各種樹結(jié)構(gòu)的字符串表達(dá)形式不唯一。
60.用Ｎ＊Ｎ（１＜＝Ｎ＜＝８）的格點陣代表海，其中＊號代表島。給你一組編
碼信息，讓你重構(gòu)一張地圖。這組信息是按垂直方向，水平方向島的情況摘取的。
下例中，每行右邊的數(shù)字按順序表示該行中“島組”的大小，如第一行數(shù)字為
“１２”，表示該行第一“島組”由一個島組成，第二“島組”由兩個島組成，而
第四列下面的“２３”則表示本列由兩個“島組”組成，第一個“島組”由兩個島
組成，第二個“島組”由三個島組成。
任務(wù)：編程執(zhí)行以下步驟，直到給定的輸入 (ASCII) 文件中的信息組全部讀完
為止，步驟如下：
（１）從輸入文件 (ASCII 文件）中讀入下一個信息塊，并將它顯示在屏幕上。
每個信息塊組成為：
格點陣大小 (N)，以后是行的約束條件（Ｎ行的），列的約束條件（Ｎ列的）,
每行（或每列）的約束條件是
一行數(shù)字，數(shù)字間有空格，最后用０結(jié)束。上面的例子如圖所示。
（２）重構(gòu)這張地圖（若有多個解，要逐個構(gòu)成地圖），并顯示。
（３）將重構(gòu)的地圖以ＡＳＣＩＩ文件形式輸出。每島以＊后加一個空格表示；
空白處用連續(xù)的兩個空格表示。若同一已知條件可畫出多張地圖，相互間用空行隔
開；若一組已知條件畫不出地圖，用“ＮＯ? ＭＡＰ（占一行）表示。由不同的信
息組求得的解用“ＮＥＸＴ? ＰＲＯＢＬＥＭ”（占一行表示）１＜＝Ｎ＜＝８.
61.一個餐廳在相繼的Ｎ天里，第 i 天需要 Ri 塊餐巾(i=1，2，...，N)。餐廳
可以從三種途徑得到餐巾:
(1)購買新的餐巾，每塊需Ｐ分；
(2)把用過的餐巾送到快洗部，洗一塊需Ｍ天，費(fèi)用需Ｆ分(Ｆ＜Ｐ)；
(3)把餐巾送到慢洗部，洗一塊需Ｎ天(Ｎ＞Ｍ)，費(fèi)用需Ｓ分(Ｓ＜Ｆ)。
在每天結(jié)束時，餐廳必須決定將多少塊用過的餐巾送到快洗部，多少塊送慢洗部，
多少塊保存起來延期送洗。在每天開始時，餐廳必須決定是否購買新餐巾及購買多
少，使洗好的和新購的餐巾之和滿足當(dāng)天的需求量Ri，并使Ｎ天總的費(fèi)用最小。請
編程輸入總天數(shù)，每天所需的餐巾塊數(shù)以及每塊餐巾的新購費(fèi)用Ｐ，快，慢洗費(fèi)用
Ｆ，Ｓ，和所需天數(shù)Ｍ，Ｎ，輸出每天開始時需購新餐巾數(shù)，結(jié)束時送快，慢洗部
和延期送洗的餐巾數(shù)。
62. (旅行商 ) 一個推銷員計劃做一次旅行，他必須訪問如圖所示每個城市。每
兩個城市的路徑旁標(biāo)有路徑。要求從城市Ａ出發(fā)，訪問每個城市一次，且只訪問一
次，最后返回城市Ａ，求一條距離最短的路線。
63. (tic__tac__toe游戲) tic__tac__toe 游戲的規(guī)則是：從一個空的 (N*N) 的
棋盤（例如Ｎ＝３）開始，甲乙二人輪流將棋子放置在棋盤上未被占據(jù)的方格中，
例如甲第一個放，他把棋子放在中央的方格里， 然后輪到乙放，他把棋子放在第
一行中間的方格里。于是又輪到甲放，......如此進(jìn)行下去。判定勝負(fù)的方法是：
若某一游戲者有Ｎ枚棋子占據(jù)了一橫行，或一豎列，或一對角線，則此人獲勝；若
直至整個棋盤被占滿還沒有一方獲勝，則為平局。
???? ┏━┯━┯━┓???????? ┏━┯━┯━┓???????? ┏━┯━┯━┓
┃? │? │? ┃???????? ┃? │? │? ┃???????? ┃? │Ｏ│? ┃
???? ┠─┼─┼─┨???????? ┠─┼─┼─┨???????? ┠─┼─┼─┨
┃? │? │? ┃???????? ┃? │Ｘ│? ┃???????? ┃? │Ｘ│? ┃
???? ┠─┼─┼─┨???????? ┠─┼─┼─┨???????? ┠─┼─┼─┨
???? ┃? │? │? ┃???????? ┃? │? │? ┃???????? ┃? │? │? ┃
???? ┗━┷━┷━┛???????? ┗━┷━┷━┛???????? ┗━┷━┷━┛
64.以字符串形式由鍵盤輸入兩個高精度的８進(jìn)制正整數(shù)，串長小于２５５，以
第一個數(shù)為被除數(shù)，第二個數(shù)為除數(shù)，進(jìn)行高精度除法運(yùn)算，并顯示按 8 進(jìn)制表
示的商和余數(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ù)最小。輸出應(yīng)包括所去掉的數(shù)字的位置和組成的新
的正整數(shù)。（Ｎ不超過２４０位）
69.在兩個文本文件中各存有一個以西文制表符制成的未填入任何表項的表結(jié)構(gòu)，
分別稱之為表１和表２，要求編程將表１和表２下述規(guī)則合并成表３：
規(guī)則：表１在表２之上，表１和表２的左邊框?qū)R，將表１的最低行與表２的
最頂行合并。例：在你的Ｃ盤根目錄下有兩個文件 t0.1 和 t0.2，分別存放上述
的表１和表２，經(jīng)上述規(guī)則合并后得到表３，放在文件中。三張表見下圖：
? ┎─┰─┰─┰─┒??????????????????????????????? ┎─┰─┰─┰─┒
? ┃? ┃? ┃? ┃? ┃??????? ┎┰─┰─┒??????????? ┃? ┃? ┃? ┃? ┃
? ┠─╂─╂─╂─┨??????? ┃┃? ┃? ┃??????????? ┠─╂─╂─╂─┨
? ┃? ┃? ┃? ┃? ┃??????? ┖┸─┸─┚??????????? ┃? ┃? ┃? ┃? ┃
? ┖─┸─┸─┸─┚??????????????????????????????? ┠┰┸┰┸┰┸─┚
??????????????????????????????????????????????????? ┃┃? ┃? ┃
??????????????????????????????????????????????????? ┖┸─┸─┚
表１??????????????????? 表２???????????????????? 表３
編程要求：
(1)程序應(yīng)能自給定的文件中讀入兩個源表并顯示。
(2)若源表有錯，應(yīng)能指出其錯。
(3)將表１和表２規(guī)則合并成表３，并顯示之。
(4)所有制表符的ＡＳＣＩＩ碼應(yīng)由選手自己從給出的示例文件中截取。
70. (圓盤問題) 從左向右依次安放 4 根細(xì)柱 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. (最長連線) 設(shè)有一個 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)，
?、龠x擇一種合并石子的方案, 使得做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ù), 表示應(yīng)該合并的兩
堆石子的數(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個串有“互鄰”關(guān)系，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,應(yīng)輸出'No',
否則按以下格式輸出:
第 1 行: 最少錢幣枚數(shù) r.
第 2 行: 輸出若干形如 m*n 的表達(dá)式, m 為幣值, n為使用該幣值的枚數(shù).
各式第 2 個因子之和應(yīng)等于 r, 各式乘積之和應(yīng)等于 n.
例: 設(shè) (a[1],a[2],a[3])=(5,2,1),? n=12,? 則應(yīng)輸出
?????? 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 應(yīng)滿足:
?????? 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
————————————————
