中國電子學會考評中心歷屆真題（含解析答案）

C語言軟件編程等級考試三級 2020年06月

編程題五道							總分:100分

一、最接近的分數（20分）
分母不超過N且小于A/B的最大最簡分數是多少?
時間限制: 1000ms
內存限制: 65536kb
輸入
三個正整數N，A，B，相鄰兩個數之間用單個空格隔開。1<=A<B<N <= 1000。
輸出
兩個正整數，分別是所求分數的分子和分母，中間用單個空格隔開。
樣例輸入

100 7 13

樣例輸出

50 93

#include <stdio.h>	// 引入C標準輸入輸出庫，用于scanf和printf函數// 定義common函數，用于計算兩個浮點數的最大公約數
double common(double x, double y) {double m = x, n = y, r;// 使用do-while循環計算最大公約數do {r = (int)m % (int)n; // 求m除以n的余數m = n; // 更新m為nn = r; // 更新n為余數r} while (r != 0); // 當余數為0時，循環結束，n中存放的就是最大公約數return m; // 返回最大公約數
}int main() {double sum, a, b, n, i, A, B, max = 0, p, q;// 從標準輸入讀取n, a, b三個值scanf("%lf %lf %lf", &n, &a, &b);// 外層循環，B從n遞減到1for (B = n; B >= 1; B--) {// 內層循環，A從1開始遞增for (A = 1; ; A++) {// 如果A/B大于a/b，則跳出內層循環if (A / B > a / b)break;// 如果A/B在max和a/b之間，則更新max，并計算p和qif (A / B > max && A / B < a / b) {max = A / B;p = A / common(A, B); // 計算A與B的最大公約數，并求A除以最大公約數的結果q = B / common(A, B); // 計算A與B的最大公約數，并求B除以最大公約數的結果}}}// 輸出p和q的值printf("%g %g", p, q);return 0;
}/*代碼的功能是尋找一對分數（A/B）和（p/q），其中A和B是整數，且滿足以下條件：1. <= B <= n，其中n是用戶輸入的一個整數。2. A/B在0和a/b之間，其中a和b也是用戶輸入的兩個整數，且b不為0。3. A/B盡可能地接近a/b，但不能超過它。4. p和q分別是A和B除以它們的最大公約數（GCD）的結果。common函數使用輾轉相除法（歐幾里得算法）來計算兩個浮點數的最大公約數。main函數讀取用戶輸入的n, a, b，然后通過兩個嵌套的for循環來找到滿足條件的A和B。內層循環從A=1開始遞增，并檢查A/B是否滿足條件。如果滿足，則更新max、p和q的值。當A/B超過a/b時，內層循環結束。外層循環負責遞減B的值，直到B=1。最后，程序輸出找到的p和q的值。注意：代碼中的sum和i變量未被使用，可以刪除。由于使用了double類型來表示分數，可能會引入精度問題。在實際應用中，可能需要使用其他方法來精確表示分數。common函數中的類型轉換(int)m和(int)n可能會導致精度損失。在C語言中，double轉int會進行向下取整。如果m和n非常大或非常小，這可能會導致問題。但在本例中，由于m和n都是整數或整數的倒數，所以這種轉換應該是安全的。
*/

二、和數（20分）
給定一個正整數序列，判斷其中有多少個數，等于數列中其他兩個數的和。比如，對于數列1234,這個問題的答案就是2，因為3 =2 +1，4 = 1 +3。
時間限制: 1000ms
內存限制: 65536kb
輸入
共兩行，第一行是數列中數的個數n ( 1 <= n <= 100)，第二行是由n個不大于10000的正整數組成的數列，相鄰兩個整數之間用單個空格隔開。
輸出
一個整數，即數列中等于其他兩個數之和的數的個數。
樣例輸入

4
1 2 3 4

樣例輸出

2

#include <stdio.h>  // 引入標準輸入輸出庫，用于scanf和printf函數int main() {  // 主函數入口int n;  // 定義一個整數n，用于存儲數組的長度int a[100],count=0;  // 定義一個最大長度為100的整數數組a和一個計數器count，并初始化count為0// 輸入數據scanf("%d",&n);  // 從標準輸入讀取一個整數，并存儲到n中for(int i=0; i<n; i++){  // 遍歷數組a，用于輸入n個整數scanf("%d",&a[i]);  // 從標準輸入讀取一個整數，并存儲到數組a的第i個位置}// 枚舉所有數for(int i=0; i<n; i++){  // 遍歷數組aint f=0;  // 定義一個標志變量f，用于表示當前數是否可以表示為其他兩數之和，初始化為0（表示不可以）for(int c=0; c<n; c++){  // 遍歷數組a，用于尋找可能的加數cif(c==i)  // 如果c和i相等（即不和自己判斷）continue;  // 則跳過當前循環，繼續下一次循環for(int d=0; d<n; d++){  // 遍歷數組a，用于尋找可能的加數dif(d==i || d==c)  // 如果d和i或d和c相等continue;  // 則跳過當前循環，繼續下一次循環if(a[i]==a[c]+a[d])  // 如果a[i]等于a[c]和a[d]的和f=1;  // 則將標志變量f設置為1（表示可以表示為其他兩數之和）}}// 統計個數if(f)  // 如果f為1count++;  // 則計數器count加1}printf("%d",count);  // 輸出計數器count的值，即可以表示為其他兩數之和的數的個數return 0;  // 主函數返回0，表示程序正常結束
}/*需要注意的是，這段代碼的時間復雜度是O(n^3)，在n較大時可能會非常慢。此外，由于它使用了三重循環，對于每個數都檢查了其他所有數對，因此效率不高。在實際應用中，可能需要考慮更高效的算法來解決這個問題。
*/

三、吃糖果（20分）
名名的媽媽從外地出差回來，帶了一盒好吃又精美的巧克力給名名（盒內共有N塊巧克力，20>N>0)。媽媽告訴名名每天可以吃一塊或者兩塊巧克力。假設名名每天都吃巧克力，問名名共有多少種不同的吃完巧克力的方案。
例如:如果N=1，則名名第1天就吃掉它，共有1種方案;
如果N=2，則名名可以第1天吃1塊，第2天吃1塊，也可以第1天吃2塊，共有2種方案;
如果N=3，則名名第1天可以吃1塊，剩2塊，也可以第1天吃2塊剩1塊，所以名名共有2+1=3種方案;
如果N=4，則名名可以第1天吃1塊，剩3塊，也可以第1天吃2塊，剩2塊，共有3+2=5種方案。
現在給定N，請你寫程序求出名名吃巧克力的方案數目。
時間限制: 1000ms
內存限制: 65536kB
輸入
輸入只有1行，即整數N。
輸出
輸出只有1行，即名名吃巧克力的方案數。
樣例輸入

4

樣例輸出

5

#include <stdio.h>  // 引入C標準輸入輸出庫，用于scanf和printf函數int main() {  // 主函數入口int n;  // 定義一個整數變量n，用于存儲用戶要查詢的斐波那契數列的項數int a[20];  // 定義一個整數數組a，大小為20，用于存儲斐波那契數列的前20項// 輸入數據scanf("%d",&n);  // 從標準輸入讀取一個整數，并存儲在變量n中// 初始化斐波那契數列的前兩項a[0]=1;  // 斐波那契數列的第0項是1a[1]=2;  // 斐波那契數列的第1項是2// 計算斐波那契數列的剩余項for(int i=2; i<n; i++){  // 從第2項開始，計算到第n-1項a[i]=a[i-1]+a[i-2];  // 每一項都是前兩項的和}// 輸出斐波那契數列的第n項printf("%d",a[n-1]);  // 注意，數組是從0開始索引的，所以第n項實際上是a[n-1]return 0;  // 主函數返回0，表示程序正常結束
}
/*注意：雖然代碼邏輯是正確的，但是有一個小問題。如果用戶輸入的n大于20，那么代碼將會訪問數組a的越界索引，這會導致未定義的行為。在實際應用中，應該添加對n的合法性檢查，或者動態分配數組的大小以適應更大的n值。
*/

四、漢諾塔問題（20分）
有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。
要求按下列規則將所有圓盤移至C桿:每次只能移動一個圓盤;大盤不能疊在小盤上面。提示:可將圓盤臨時置于B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須遵循上述兩條規則。
如何移?最少要移動多少次?
時間限制: 1000ms
內存限制: 65536kb
輸入
輸入為一個整數后面跟三個單字符字符串。
整數為盤子的數目，后三個字符表示三個桿子的編號。
輸出
輸出每一步移動盤子的記錄。一次移動一行。
每次移動的記錄為例如3:a->b的形式，即把編號為3的盤子從a桿移至b桿。
我們約定圓盤從小到大編號為1，2,…n。即最上面那個最小的圓盤編號為1，最下面最大的圓盤編號為n。
樣例輸入

3 a b c

樣例輸出

1:a->c
2:a->b
1:c->b
3:a->c
1:b->a
2:b->c
1:a->c

#include <stdio.h>	// 引入C標準輸入輸出庫，用于scanf和printf函數// 定義find函數，用于將n個盤子從a柱移動到c柱，以b柱作為輔助
void find(int n, char a, char b, char c) {if(n == 1) { // 如果只有一個盤子printf("%d:%c->%c\n", n, a, c); // 直接從a柱移動到c柱return; // 返回}find(n - 1, a, c, b); // 先將n-1個盤子從a柱移動到b柱，以c柱作為輔助printf("%d:%c->%c\n", n, a, c); // 然后將最后一個盤子從a柱移動到c柱find(n - 1, b, a, c); // 最后將n-1個盤子從b柱移動到c柱，以a柱作為輔助
}int main() {int n; // 定義盤子數量char a, b, c; // 定義三個柱子的名稱scanf("%d %c %c %c", &n, &a, &b, &c); // 從用戶處獲取輸入：盤子數量和三個柱子的名稱find(n, a, b, c); // 調用find函數開始漢諾塔問題的求解return 0; // 程序結束
}/*這段代碼使用了遞歸的方式來解決漢諾塔問題。對于n個盤子，它首先將n-1個盤子從起始柱子移動到過渡柱子，然后將最大的盤子從起始柱子移動到目標柱子，最后再將n-1個盤子從過渡柱子移動到目標柱子。這個過程重復進行，直到所有的盤子都被移動到目標柱子。
*/

五、文件結構“圖“（20分）
在計算機上看到文件系統的結構通常很有用。Microsoft Windows上面的"explorer"程序就是這樣的一個例子。但是在有圖形界面之前，沒有圖形化的表示方法的，那時候最好的方式是把目錄和文件的結構顯示成一個"圖"的樣子，而且使用縮排的形式來表示目錄的結構。比如:

ROOT
| dir1
| file1
| file2
| file3
| dir2
| dir3
| file1
file1
file2

這個圖說明:ROOT目錄包括三個子目錄和兩個文件。第一個子目錄包含3個文件，第二個子目錄是空的，第三個子目錄包含一個文件。
時間限制: 1000ms
內存限制: 65536kb
輸入
你的任務是寫一個程序讀取一些測試數據。每組測試數據表示一個計算機的文件結構。每組測試數據以’*‘結尾，而所有合理的輸入數據以’#‘結尾。一組測試數據包括一些文件和目錄的名字（雖然在輸入中我們沒有給出，但是我們總假設ROOT目錄是最外層的目錄)。在輸入中,以’]‘表示一個目錄的內容的結束。目錄名字的第一個字母是’d’，文件名字的第一個字母是’f’。文件名可能有擴展名也可能沒有(比如fmyfile.dat和fmyfile)。文件和目錄的名字中都不包括空格,長度都不超過30。一個目錄下的子目錄個數和文件個數之和不超過30。
輸出
在顯示一個目錄中內容的時候，先顯示其中的子目錄(如果有的話)，然后再顯示文件(如果有的話)。文件要求按照名字的字母表的順序顯示（目錄不用按照名字的字母表順序顯示，只需要按照目錄出現的先后顯示)。對每一組測試數據，我們要先輸出"DATA SET x:" ,這里x是測試數據的編號（(從1開始)。在兩組測試數據之間要輸出一個空行來隔開。
你需要注意的是，我們使用一個’|'和5個空格來表示出縮排的層次。

樣例輸入

file1
file2
dir3
dir2
file1
file2
]
]
file4
dir1
]
file3
*
file2
file1
*
#

樣例輸出

DATA SET 1:
ROOT
| dir3
|| dir2
|| file1
|| file2
| dir1
file1
file2
file3
file4DATA SET 2:
ROOT
file1
file2

提示
一個目錄和它的子目錄處于不同的層次
一個目錄和它的里面的文件處于同一層次

#include<iostream>  // 引入輸入輸出流庫
#include<set>       // 引入集合庫
#include<string>    // 引入字符串庫using namespace std;  // 使用標準命名空間int flag;  // 定義一個全局變量flag，用于標記是否已經打印了ROOT// 定義一個函數printkg，用于打印指定長度的豎線和空格
void printkg(int l){for(int i = 0; i < l; ++i)printf("| ");
}// 定義一個函數pf，用于處理用戶的輸入
void pf(int l){string str;  // 定義一個字符串變量str，用于存儲用戶的輸入set<string> dir;  // 定義一個字符串集合dir，用于存儲目錄結構if(!flag){  // 如果flag為0（即未打印ROOT）printf("ROOT\n");  // 打印ROOTflag = 1;  // 將flag設置為1，表示已經打印了ROOT}while(cin >> str){  // 循環讀取用戶的輸入switch(str[0]){  // 根據輸入的第一個字符進行不同的操作case 'f':  // 如果輸入的第一個字符是'f'dir.insert(str);  // 將整個輸入字符串添加到目錄集合中break;  // 結束switch語句case 'd':  // 如果輸入的第一個字符是'd'printkg(l);  // 打印指定長度的豎線和空格cout << str << endl;  // 打印輸入的字符串（表示一個新的目錄）pf(l + 1);  // 遞歸調用pf函數，增加層級break;  // 結束switch語句case ']':  // 如果輸入的第一個字符是']'for(set<string>::iterator i = dir.begin(); i != dir.end(); ++i){  // 遍歷目錄集合printkg(l - 1);  // 打印指定長度的豎線和空格（比當前層級少一級）cout << *i << endl;  // 打印目錄集合中的每個字符串（表示返回上一級目錄）}return;  // 結束函數case '*':  // 如果輸入的第一個字符是'*'for(set<string>::iterator i = dir.begin(); i != dir.end(); ++i)cout << *i << endl;  // 打印目錄集合中的所有字符串（表示列出當前目錄的所有文件和子目錄）cin.get();  // 讀取一個字符（可能是為了消耗輸入流中的換行符或其他字符）return;  // 結束函數}}
}int main(){int n = 1;  // 定義一個變量n，用于表示數據集的編號while(cin.peek() != '#'){  // 循環讀取輸入，直到遇到'#'字符為止printf("DATA SET %d:\n", n);  // 打印數據集的編號flag = 0;  // 將flag重置為0，表示未打印ROOTpf(1);  // 從第一層級開始處理用戶的輸入++n;  // 增加數據集的編號printf("\n");  // 打印一個空行，用于分隔不同的數據集}return 0;  // 程序結束
}/*這個程序通過用戶輸入的不同字符來模擬目錄樹的操作，如創建新目錄、返回上一級目錄、列出當前目錄的內容等。程序使用了一個字符串集合來存儲目錄結構，并使用遞歸函數來處理不同層級的目錄操作。
*/