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

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

編程題四道							總分:100分

一、最長上升子序列（25分）
一個數的序列bi，當b1 < b2< … <bs的時候，我們稱這個序列是上升的。對于給定的一個序列(a1, a2… aN)，我們可以得到一些上升的子序列(ai1, ai2,…, aik)，這里1<=i1<i2<… <ik <=N。
比如，對于序列(1，7，3，5，9，4，8)，有它的一些上升子序列，如(1，7)，(3，4，8)等等。這些子序列中最長的長度是4，比如子序列(1，3，5，8)。
你的任務，就是對于給定的序列，求出最長上升子序列的長度。
時間限制: 2000ms
內存限制: 65536kb
輸入
輸入的第一行是序列的長度N (1 <=N<= 1000)。
第二行給出序列中的N個整數，這些整數的取值范圍都在0到10000。輸出
最長上升子序列的長度。
樣例輸入

7
1 7 3 5 9 4 8

樣例輸出

4

#include <iostream>  // 引入輸入輸出流庫
using namespace std;  // 使用標準命名空間int main() {  // 程序主入口int N;  // 定義一個整型變量N，用于存儲用戶輸入的序列長度scanf("%d",&N);  // 從標準輸入讀取一個整數到變量Nint a[1010];  // 定義一個整型數組a，大小為1010，用于存儲用戶輸入的序列for(int i = 0; i < N; i++){  // 循環N次，讀取序列中的每個元素scanf("%d", &a[i]);  // 從標準輸入讀取一個整數到數組a的第i個位置}// 定義dp數組，dp[i]表示以a[i]結尾的最長上升子序列的長度int dp[1010];  dp[0] = 1;  // 初始化dp數組的第一個元素為1，因為任何單個元素都可以視為一個長度為1的上升子序列int max_len = 0;  // 定義一個變量max_len，用于存儲最長上升子序列的長度for(int i = 1; i < N; i++){  // 從序列的第二個元素開始遍歷for(int j = i - 1; j >= 0; j--){  // 對每個元素，向前遍歷它之前的所有元素if(a[i] > a[j]){  // 如果當前元素大于之前的某個元素dp[i] = dp[j] + 1;  // 更新dp[i]為dp[j]+1，表示以a[i]結尾的最長上升子序列長度增加了1break;  // 找到后，跳出內層循環}}max_len = max(max_len, dp[i]);  // 更新最長上升子序列的長度}printf("%d", max_len);  // 輸出最長上升子序列的長度return 0;  // 程序結束，返回0
}/*代碼使用動態規劃的思想解決了LIS問題。對于每個位置i，它都嘗試找到在它之前的位置j，使得a[i] > a[j]，并更新dp[i]為dp[j] + 1。這樣，dp[i]就存儲了以a[i]結尾的最長上升子序列的長度。然后，通過遍歷所有的dp[i]，可以找到整個序列的最長上升子序列的長度。
*/

二、核電站（25分）
一個核電站有N個放核物質的坑，坑排列在一條直線上。如果連續3個坑中放入核物質，則會發生爆炸，于是，在某些坑中可能不放核物質。
現在，請你計算:對于給定的N，求不發生爆炸的放置核物質的方案總數。
時間限制: 1000ms
內存限制: 131072kb
輸入
輸入文件只有多行，每行對應一個正整數N<= 40;輸出
輸出文件有多行，每行只有一個正整數，表示方案總數。
樣例輸入

1
2
3
4
10

樣例輸出

2
4
7
13
504

#include <iostream>  // 包含C++標準輸入輸出流庫
#include <cstring>   // 包含C++字符串操作庫，用于memset函數
using namespace std; // 使用標準命名空間long long dp[55][7]; // 定義一個二維數組dp，用于存儲動態規劃的狀態。dp[i][j]表示前i個坑中連續埋了j個雷的方案數。int main() {int n; // 定義一個整數n，表示坑的數量for(int c = 0; c<40; c++){ // 循環40次，處理多組數據cin >> n; // 從標準輸入讀取一個整數nif(n <= 0) // 如果n小于等于0，則結束當前循環break;memset(dp,0, sizeof(dp)); // 將dp數組中的所有元素初始化為0dp[1][1] = 1; // 第一個坑放一個核物質的方案數為1dp[1][0] = 1; // 第一個坑不放核物質的方案數為1for(int i = 2; i <= n; i++){ // 從第二個坑開始遍歷到第n個坑for(int j = 0; j < 3; j++){ // 遍歷連續放核物質的數量，從0到2if(j == 0){ // 如果當前連續放核物質的數量為0for(int k = 0; k < 3;k++) // 遍歷前一個坑連續放核物質的數量，從0到2dp[i][j]+= dp[i - 1][k]; // 更新dp[i][j]，累加前一個坑所有可能的方案數}else // 如果當前連續放核物質的數量不為0dp[i][j] += dp[i - 1][j - 1]; // 更新dp[i][j]，累加前一個坑連續埋了j-1個核物質的方案數}}long long ans = 0; // 定義一個變量ans，用于存儲所有可能的方案數for(int i = 0; i < 3; i++) // 遍歷最后一個坑連續放核物質的數量，從0到2ans += dp[n][i]; // 累加最后一個坑所有可能的方案數到anscout <<ans; // 輸出所有可能的方案數到標準輸出}return 0; // 程序結束，返回0
}/*代碼使用動態規劃的方法解決了放置物體的問題。首先，它初始化了一個二維數組dp來存儲中間結果。然后，它讀取一系列的輸入值n，對于每個n，它都使用動態規劃來計算在n個位置中放置物體的方案數，并將結果輸出到標準輸出。
*/

三、山區建小學（25分）
政府在某山區修建了一條道路，恰好穿越總共m個村莊的每個村莊一次，沒有回路或交叉，任意兩個村莊只能通過這條路來往。
已知任意兩個相鄰的村莊之間的距離為di(為正整數)，其中，0 < i < m。為了提高山區的文化素質，政府又決定從m個村中選擇n個村建小學(設0 < n <= m < 500 )。
請根據給定的m、n以及所有相鄰村莊的距離，選擇在哪些村莊建小學，才使得所有村到最近小學的距離總和最小，計算最小值。
時間限制: 24000ms
內存限制: 65536kb
輸入
第1行為m和n，其間用空格間隔;
第2行為(m-1)個整數，依次表示從一端到另一端的相鄰村莊的距離，整數之間以空格間隔。
例如: 10 3 2 4 6 5 2 4 3 1 3，表示在10個村莊建3所學校。第1個村莊與第2個村莊距離為2，第2個村莊與第3個村莊距離為4，第3個村莊與第4個村莊距離為6，…，第9個村莊到第10個村莊的距離為3。
輸出
各村莊到最近學校的距離之和的最小值。
樣例輸入

10 2
3 1 3 1 1 1 1 1 3

樣例輸出

18

#include <algorithm> // 引入算法庫，盡管在這段代碼中并沒有使用到該庫中的功能
#include <cstring>   // 引入字符串操作庫，用于memset函數
#include <iostream>  // 引入輸入輸出流庫
using namespace std; // 使用標準命名空間int dis[510], a[510][510], dp[510][510]; // 定義全局變量：dis用于存儲距離，a用于存儲某個子問題的解，dp用于存儲最終的最優解int main() { // 主函數入口int m, n; // 定義兩個整數變量m和n，分別表示問題的兩個維度memset(a,0,sizeof(a)); // 使用memset函數將二維數組a初始化為0cin >> m >> n; // 從標準輸入讀取m和n的值dis[1] = 0; // 初始化dis數組的第一個元素為0for (int i = 2; i<= m; i++){ // 從2開始遍歷到mcin >> dis[i]; // 讀取dis數組的每個元素dis[i]+= dis[i - 1]; // 更新dis數組，使其存儲的是從第一個元素到當前元素的累積和}for (int i = 1; i <= m; i++) // 遍歷所有可能的子問題的起始點for (int j = i + 1; j <= m; j++) // 遍歷所有可能的子問題的結束點a[i][j] = a[i][j - 1] + dis[j] - dis[(i + j)/ 2]; // 計算子問題的解，這里使用了一個基于累積和的公式for (int i = 1; i <= m; i++) // 初始化dp數組的第一列for(int j = 1; j <= i && j <= n; j++)dp[i][j] = 999999; // 將dp數組初始化為一個很大的數，表示初始時還沒有找到解for (int i =1; i<= m; i++) // 初始化dp數組的第一行dp[i][1] = a[1][i]; // 將dp數組的第一行設置為a數組的第一行的值for (int i = 2; i <= m; i++) // 從第二行開始遍歷dp數組for(int j = 2; j <= i && j <= n; j++) // 遍歷dp數組的每一列for(int k = j - 1; k < i; k++) // 遍歷所有可能的分割點kdp[i][j] = min(dp[i][j], dp[k][j - 1] + a[k + 1][i]); // 更新dp數組的值，尋找最優解cout << dp[m][n] << endl; // 輸出最終的最優解return 0; // 程序結束
}/*這個程序的整體邏輯是動態規劃。首先，它計算了一個累積和數組dis，然后基于這個數組計算了子問題的解a。接著，它使用動態規劃的思想，通過填充dp數組來找到最終的最優解。最后，程序輸出了這個最優解。
*/

四、公共子序列（25分）
我們稱序列Z= <z1,z2…,zk >是序列X=<x1, x2…, xm >的子序列當且僅當存在嚴格上升的序列<i1, i2,… ik >，使得對j =1,2… k,有xij = zj。比如Z= < a, b, f, c >是X=<a, b, c, f, b, c >的子序列。
現在給出兩個序列X和Y，你的任務是找到X和Y的最大公共子序列，也就是說要找到一個最長的序列Z，使得Z既是X的子序列也是Y的子序列。
時間限制: 3000ms
內存限制: 65536kb
輸入
輸入包括多組測試數據。每組數據包括一行，給出兩個長度不超過200的字符串，表示兩個序列。兩個字符串之間由若干個空格隔開。
輸出
對每組輸入數據，輸出一行，給出兩個序列的最大公共子序列的長度。
樣例輸入

abcfbc abfcab
programming contest
abcd mnp

樣例輸出

4
2
0

#include<iostream>    // 引入輸入輸出流庫
#include<cstring>     // 引入字符串操作庫（這里主要是使用memset函數）
#include<cstdio>      // 引入C標準輸入輸出庫（雖然在這段代碼中未直接使用）
using namespace std; // 使用標準命名空間string a,b;           // 定義兩個字符串變量a和b
int dp[220][220];    // 定義一個二維數組dp，用于存儲動態規劃過程中的子問題的解int lcs(){           // 定義一個函數lcs，用于計算最長公共子序列的長度memset(dp,0,sizeof(dp)); // 使用memset函數初始化dp數組，所有元素設為0int lena=a.size(),lenb=b.size(); // 獲取字符串a和b的長度for(int i=1;i<=lena;i++)         // 外層循環，遍歷字符串a的所有字符for(int j=1;j<=lenb;j++)     // 內層循環，遍歷字符串b的所有字符if(a[i-1]==b[j-1])       // 如果當前字符相等dp[i][j]=dp[i-1][j-1]+1; // 更新dp[i][j]為左上角元素加1else                     // 如果當前字符不相等dp[i][j]=max(dp[i-1][j],dp[i][j-1]); // 更新dp[i][j]為上方和左方元素中的較大值return dp[lena][lenb]; // 返回dp數組的最后一個元素，即最長公共子序列的長度
}int main() {           // 主函數while(cin>>a>>b)  // 循環讀取字符串a和bcout<<lcs()<<"\n"; // 調用lcs函數并輸出最長公共子序列的長度，然后換行return 0;          // 程序結束
}
/*這道題使用了動態規劃的方法來求解最長公共子序列問題。通過構建一個二維數組dp來存儲子問題的解，并利用遞推關系逐步填充這個數組，最終得到最長公共子序列的長度。
*/