2011年選拔賽C大學

考試時間為4小時。

所填寫的代碼不超過一條語句（即不能出現分号）。

考生的程式隻有能運作出正确結果的時候才有機會得分。

選手的程式必須是通用的，不能隻對試卷中給定的資料有效。

不能使用c++特性

1. 代碼填空 （滿分3分）

　　神秘的三位數

　　有這樣一個3位數，組成它的3個數字階乘之和正好等于它本身。即：abc = a! + b! + c!下面的程式用于搜尋這樣的3位數。請補全缺失的代碼。

2. 代碼填空 （滿分4分）

　　歌賽新規則

　　 歌手大賽的評分規則一般是去掉一個最高分，去掉一個最低分，剩下的分數求平均。當評委較少的時候，如果我們隻允許去掉一個分數，該如何設計規則呢？ 有人提出：應該去掉與其餘的分數(還是他自己的分數不是其他選手，從下面的代碼可以看出double t = x[i] - sum / (n-1)，而且題目是針對某一個選手說的，原來了解錯了)平均值相差最遠的那個分數。即“最離群”的分數。 以下的程式用于實作這個功能。其中x存放所有評分，n表示數組中元素的個數。函數傳回最“離群”的那個分數值。

3. 代碼填空 （滿分4分）

　　反轉串

　　我們把“cba”稱為“abc”的反轉串。 下面的代碼可以把buf中的字元反轉。其中n表示buf中待反轉的串的長度。請補充缺少的代碼。

4. 代碼填空 （滿分5分）

　　n進制小數

　　将任意十進制正小數分别轉換成2,3,4,5,6,7,8,9進制正小數，小數點後保留8位，并輸出。例如：若十進制小數為0.795，則輸出：  十進制正小數 0.795000 轉換成 2 進制數為: 0.11001011  十進制正小數 0.795000 轉換成 3 進制數為: 0.21011011  十進制正小數 0.795000 轉換成 4 進制數為: 0.30232011  十進制正小數 0.795000 轉換成 5 進制數為: 0.34414141  十進制正小數 0.795000 轉換成 6 進制數為: 0.44341530  十進制正小數 0.795000 轉換成 7 進制數為: 0.53645364  十進制正小數 0.795000 轉換成 8 進制數為: 0.62702436  十進制正小數 0.795000 轉換成 9 進制數為: 0.71348853 以下代碼提供了這個功能。其中，dTestNo表示待轉的十進制小數。iBase表示進制數。

5. 代碼填空 （滿分6分）

　　輪換

　　串“abcd”每個字元都向右移位，最右的移動到第一個字元的位置，就變為“dabc”。這稱為對串進行位移=1的輪換。同理，“abcd”變為：“cdab”則稱為位移=2的輪換。 下面的代碼實作了對串s進行位移為n的輪換。請補全缺失的代碼。

6. 代碼填空 （滿分9分）

　　中獎計算

　　某抽獎活動的規則是：每位參與者在紙上寫下一個8位數的号碼。最後通過搖獎的辦法随機産生一個8位數字。參與者寫下的數字中最多有多少個連續位與開獎号碼中的相同，則稱為中了幾個号。 例如：小張寫的數字是：12345678，而開獎号碼是：42347856。則稱小張中了3個号，因為其中最長的相同連續位是：“234”（不僅要相同，而且要位置相同）。如果小張寫的是：87654321，則他隻中了一個号。 下面的代碼根據傳入的參數，傳回中了幾個号。其中：a表示被評價的号碼，b表示搖号産生的數字。

7. 代碼填空 （滿分10分）

　　機率問題

　　某個袋子中有紅球m個，白球n個。現在要從中取出x個球。那麼紅球數目多于白球的機率是多少呢？ 下面的代碼解決了這個問題。其中的y表示紅球至少出現的次數。 這與前文的問題是等價的。因為如果取30個球，要求紅球數大于白球數，則等價于至少取出16（(30+1)/2,不管奇偶這個 都是較大者）個紅球。請根據僅存的線索，判斷程式邏輯，并補全缺少的代碼。

下面的題目都是程式設計題，沒有标準答案，隻有測試用例。

8. 程式設計（滿分15分）

方陣的主對角線之上稱為“上三角”。 請你設計一個用于填充n階方陣的上三角區域的程式。填充的規則是：使用1，2，3….的自然數列，從左上角開始，按照順時針方向螺旋填充。

例如：當n=3時，

輸出：

1 2 3

6 4

5

當n=4時，

1  2 3 4

9 10 5

8  6

7 當n=5時，輸出：   1  2  3  4  5  12 13 14  6  11 15  7  10  8   9 程式運作時，要求使用者輸入整數n（3~20） 程式輸出：方陣的上三角部分。 要求格式：每個資料寬度為4，右對齊

　　

9. 程式設計（滿分16分）

公司發了某商店的購物券1000元，限定隻能購買店中的m種商品。每種商品的價格分别為m1,m2,…，要求程式列出所有的正好能消費完該購物券的不同購物方法。 程式輸入： 第一行是一個整數m，代表可購買的商品的種類數。 接下來是m個整數，每個1行，分别代表這m種商品的單價。 程式輸出：  第一行是一個整數，表示共有多少種方案  第二行開始，每種方案占1行，表示對每種商品購買的數量，中間用空格分隔。 例如： 輸入： 2 200 300 則應輸出： 2 2  2 5  0  輸入： 2 500 800 則應輸出： 1 2  0 。

　

10. 程式設計（滿分28分）

一種Playfair密碼變種加密方法如下：首先選擇一個密鑰單詞（稱為pair）（字母不重複

，且都為小寫字母），然後與字母表中其他字母一起填入至一個5x5的方陣中，填入方法如

下： 1.首先按行填入密鑰串。 2.緊接其後，按字母序按行填入不在密鑰串中的字母。 3.由于方陣中隻有25個位置，最後剩下的那個字母則不需變換。 如果密鑰為youandme，則該方陣如下：  y o u a n d m e b c f g h i j k l p q r s t v w x 在加密一對字母時，如am，在方陣中找到以這兩個字母為頂點的矩形（紅色字型）： y o u a n d m e b c f g h i j k l p q r s t v w x

這對字母的加密字母為該矩形的另一對頂點，如本例中為ob。 請設計程式，使用上述方法對輸入串進行加密，并輸出加密後的串。 另外有如下規定： 1、一對一對取字母，如果最後隻剩下一個字母，則不變換，直接放入加密串中； 2、如果一對字母中的兩個字母相同，則不變換，直接放入加密串中； 3、如果一對字母中有一個字母不在正方形中，則不變換，直接放入加密串中； 4、如果字母對出現在方陣中的同一行或同一列，如df或hi，則隻需簡單對調這兩個字母，

即變換為fd或ih； 5、如果在正方形中能夠找到以字母對為頂點的矩形，假如字母對為am，則該矩形的另一對

頂點字母中，與a同行的字母應在前面，在上例中應是ob；同樣若待變換的字母對為ta，則

變換後的字母對應為wo； 6、本程式中輸入串均為小寫字母，并不含标點、空格或其它字元。 解密方法與加密相同，即對加密後的字元串再加密，将得到原始串。 要求輸入形式如下： 從控制台輸入兩行字元串，第一行為密鑰單詞（長度小于等于25），第二行為待加密字元

串（長度小于等于50），兩行字元串末尾都有一個回車換行符，并且兩行字元串均為小寫

字母，不含其它字元。 在标準輸出上輸出加密後的字元串。 例如，若輸入： youandme welcometohangzhou 則表示輸入的密鑰單詞為youandme，形成的正方形如上所示；待加密字元串為

welcometohangzhou。在正方形中可以找到以第一對字母we為頂點的矩形，對應另一對頂點

字母為vb，是以加密後為vb，同理可找到與字母對lc,et,oh,ho對應的頂點字母對。而字母

對om位于上述正方形中的同一列，是以直接以颠倒這兩個字母來加密，即為mo，字母對an

同理。字母對gz中的z不在上述正方形中，是以原樣放到加密串中。最後剩一個字母u也原

樣輸出。 是以輸出的結果為： vbrmmomvugnagzguu