Programming Clip】06、07年清華計算機考研上機試題解答（個别測試用例無法通過）

1.清華計算機系研究所學生考試上機07年試題解答（自己今天上午做的，有一個不能完成所有測試用例～）

清華大學計算機科學與技術系

2007 年碩士研究所學生招生複試

2007 年 3 月 24 日

注意事項：

1. 試題共三題，總計 100 分，考試時間為一個半小時。

2. 不得使用自帶的電子裝置，包括筆記本、 U 盤、手機等；不得使用參考書籍和資料。

3. 程式設計環境為 Windows 2000 Professional + Visual Studio 6.0 ，隻能使用 C/C++ 語言。

4. 每一題的輸入資料都從檔案 input.txt 中讀取，将結果輸出至檔案 output.txt ，請嚴格按照每一題的輸入輸出格式 。在考試過程中，我們恕不提供除試題中樣例以外的測試資料，請自行生成輸入資料以對程式進行自測。

5. 在考試結束之前自行設定編譯環境和配置編譯參數，将所寫的程式編譯成可執行檔案，檔案名在每一題中都有規定。生成的可執行檔案将作為最終測試的唯一依據，若無法運作您的可執行檔案，最終成績将記為零分。

6. 程式對每個測試資料的可用運作時間上限 1 秒，若逾時或結果錯誤，則該測試用例不能得分。

7. 在考試過程中，若計算機出現故障，請及時通知從業人員，以免耽誤您的考試時間。

8. 上機考試結束後，請勿馬上離開，從業人員将會直接進行現場測試，需要您的合作。

第一題（可執行檔案名 program1.exe ）

求正整數 N(N>1) 的質因數的個數。注意： 1 不是 N 的質因數：若 N 為質數， N 是 N 的質因數。相同的質因數需要重複計算。

如 120=2*2*2*3*5 ，共有 5 個質因數。

輸入：

正整數N ，1<N<109

輸出：

N 的質因數的個數

樣例輸入：

120

樣例輸出

5

第二題（可執行檔案名：program2.exe ）

對于一個十進制數A ，将A 轉換為二進制數，然後按位逆序排列，再轉換為十進制數B ，我們乘B 為A 的二進制逆序數 。

例如對于十進制數173 ，它的二進制形式為101011101 ，逆序排列得到10110101 ，其十進制數為181 ，181 即為173 的二進制逆序數

一個1000 位( 即2999 ) 以内的十進制數。

輸入的十進制數的二進制逆序數。

173

樣例輸出：

181

（下列程式隻能忍受部分測試用例）

第三題（可執行檔案名program3.exe ）

有若幹張郵票，要求從中選取最少的郵票張數湊成一個給定的總值。

如，有1 分，3 分，3 分，3 分，4 分五張郵票，要求湊成10 分，則使用3 張郵票：3 分、3 分、4 分即可。

首先是要求湊成的郵票總值M ，M<100

然後是一個數N ，N 〈20 ，表示有N 張郵票。接下來是N 個正整數，分别表示這N 張郵票的面值，且以升序排列。

能夠湊成總值M 的最少郵票張數。若無解，輸出0 。

10 5 1 3 3 3 4

3

分析：這是最簡單的背包問題，動态規劃的方法，寫得不是很規範，不過結果很不錯，線形複雜度 ~~

2.清華計算機系研究所學生考試上機06年試題解答（自己今天下午做的，郁悶之中。。。做的時間太長）

一、輸入：兩行

第一行：M和N

第二行：X

M和N是一個十進制數，M和N都在[2-36]之間，X是一個M進制數，X在[1-2*10^19]

輸出：一行

第一行：現在要求你将M進制數X轉換成N進制數輸出

輸入一：

16 10

F

輸出一：

15

二、按照手機鍵盤輸入字母的方式，計劃所花費的時間

如：a,b,c都在“1”鍵上，輸入a隻需要按一次，輸入c需要連續按三次。

如果連續兩個字元不在同一個按鍵上，則可直接按，如：ad需要按兩下，kz需要按6下

如果連續兩字元在同一個按鍵上，則兩個按鍵之間需要等一段時間，如ac，在按了a之後，需要等一會兒才能按 C。

現在假設每按一次需要花費一個時間段，等待時間需要花費兩個時間段。

現在給出一串字元，需要計劃出它所需要花費的時間。

輸入一：bob

輸出一：7

輸入二：www