2023年3月电子学会C语言编程等级考试四级真题试卷

青少年软件编程（C语言）等级考试试卷（四级） 分数：100 题数：4 一、编程题(共4题，共100分) 1. 最佳路径 如下所示的由正整数数字构成的三角形: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。 注意：路径上的每一步只能从一个数走到下一层上和它最近的下边（正下方）的数或者右边（右下方）的数。 时间限制：1000 内存限制：65536 输入 第一行为三角形高度100>=h>=1，同时也是最底层边的数字的数目。 从第二行开始，每行为三角形相应行的数字，中间用空格分隔。 输出 最佳路径的长度数值。 样例输入 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 样例输出 30 提示 如何采用动态规划的思想，对问题进行分解。 试题编号：20230318-4-01 试题类型：编程题 标准答案： 试题难度：一般 试题解析： 展示地址：点击浏览 考生答案：（此题已作答） 考生得分：25 是否评分：已评分 评价描述： 考生答案： #include<bits/stdc++.h> using namespace std; const int maxn = 1e2 + 10; int dp[maxn][maxn], a[maxn][maxn]; int main(){ int n; cin>>n; for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++) cin>>a[i][j]; } memset(dp,0,sizeof(dp)); dp[1][1] = a[1][1]; for(int i = 2;i <= n;i++){ for(int j = 1;j <= i;j++){ dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+a[i][j]; } } int m = dp[n][1]; for(int i = 2;i < n; i++){ m = max(m,dp[n][i]); } cout<<m<<endl; } 2. 邮票收集 小A是个邮票收集爱好家，他有n种面值的邮票，每种邮票都有无数张。一天小B想要寄信，需要一共面值和为k的邮票组合。小A想要知道拼出面值为k的邮票最少需要多少张。 时间限制：1000 内存限制：131072 输入 输入是多组数据。(不超过10组) 每组数据的第一行正整数n，k，表示邮票的种类数目和目标要拼出的钱。(0 < n ≤ 100, 0 < k ≤ 1000 ) 接下来的一行有n个正整数a i (0 < a i  ≤ 1000)。 若n=k=0表示输入结束。 输出 每组数据输出一行一个数，分别表示拼出k需要的最少的邮票数量。 如果不存在能够拼出k的方案，输出-1。 样例输入 4 10 1 2 3 4 5 16 1 2 3 4 5 2 7 4 5 0 0 样例输出 3 4 -1 提示 第一组数据: 10 = 4+4+2 第二组数据：16 = 5+5+5+1 第三组数据： 不存在。 试题编号：20230318-4-02 试题类型：编程题 标准答案