首页 › 试卷 › C/C++编程考级 › C/C++编程三级 › 青少年软件编程(C/C++)3级等级考试真题试卷(2024年12月)

青少年软件编程(C/C++)3级等级考试真题试卷(2024年12月) VIP

C/C++编程三级 共 5 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

最近的斐波那契数

斐波那契数列 Fn 的定义为:对 n ≥ 0 有 Fn+2 = Fn+1 + Fn,初始值为 F0 = 0 和 F1 = 1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。

本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。

时间限制:1000

内存限制:65536

输入

输入在一行中给出一个正整数 N(≤ 108)。

输出

在一行输出与 N 最近的斐波那契数。如果解不唯一,输出最小的那个数。

样例输入

305

样例输出

233

提示

样例解释 部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... }。可见 233 和 377 到 305 的距离都是最小值 72,则应输出较小的那个解。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;bits/stdc++.h&gt; #include&lt;math.h&gt; using namespace std; int main(){ int n[101]; n[0]=0,n[1]=1; for(int i=2;i&lt;43;i++){ n[i]=n[i-1]+n[i-2]; } int N; cin&gt;&gt;N; int min_diff=9999999; int temp[101]={0},j=0; for(int i=0;i&lt;43;i++){ if(abs(n[i]-N)&lt;min_diff){ min_diff=abs(n[i]-N); temp[j++]=n[i]; } } cout&lt;&lt;temp[j-1]; return 0; }</pre>
这道题暂未补解析。
2. 简答题

构造性证明

关于数学定理证明,也有高下之分。最暴力的证明方法是“构造性证明”,即当需要证明某种解存在时,直接把解构造出来,而不是仅通过推理证明解之存在。

下面有一个定理:

设 ai(i=1, … , 5)均为正实数。则一定存在 4 个互不相同的下标 i、j、k、l,使得 |ai / aj - ak / al| < 1/2。

作为程序员,就请你编写程序构造出正确的下标,验证这个结论。

时间限制:1000

内存限制:65536

输入

输入在一行中顺序给出 5 个正实数。为保证计算中不产生浮点溢出,我们令输入的数字在 [10-10, 1010] 区间内,且小数点后不超过 10 位小数。

输出

在一行中首先输出使得定理结论成立的下标有多少套,随后输出最小的一套下标。数字间以 1 个空格分隔,行首尾不得有多余空格。 注:所谓下标集 {i1, …, i4} 小于下标集 {j1, …, j4},是指存在 1 ≤ k ≤ 4 使得 il=jl 对所有 l < k 成立,且 ik < jk。

样例输入

3.12 5.27 0.0007 9825.4413 10

样例输出

18 1 4 3 2

提示

样例解释: 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个,例如 5、4、3、2 就是另一套解。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;iomanip&gt; using namespace std; const double EPS = 1e-9; // 比较两个双精度浮点数是否相等(考虑精度误差) bool doubleEqual(double a, double b) {     return fabs(a - b) &lt; EPS; } int main() {     vector&lt;double&gt; nums(5);     for (int i = 0; i &lt; 5; ++i) {         cin &gt;&gt; nums[i];     }     int count = 0;     vector&lt;int&gt; result(4);     // 四重循环遍历所有可能的四个下标组合     for (int i = 0; i &lt; 5; ++i) {         for (int j = 0; j &lt; 5; ++j) {             if (i == j) continue;             for (int k = 0; k &lt; 5; ++k) {                 if (k == i || k == j) continue;                 for (int l = 0; l &lt; 5; ++l) {                     if (l == i || l == j || l == k) continue;                     double val = fabs(nums[i] / nums[j] - nums[k] / nums[l]);                     if (val &lt; 0.5) {                         count++;                         if (count == 1) {                             result = {i + 1, j + 1, k + 1, l + 1};                         }                     }                 }             }         }     }     cout &lt;&lt; count &lt;&lt; " ";     for (int idx : result) {         cout &lt;&lt; idx &lt;&lt; " ";     }     return 0; }</pre>
这道题暂未补解析。
3. 简答题

环形公路出口

一条环形高速路上有 N 个出口。给定任意一对出口,请你算出这两个出口之间的最短距离。

时间限制:1000

内存限制:65536

输入

输入第一行给出区间 [3,105] 内的整数 N,以及 N 个整数距离 D1 D2 … DN,其中 Di 是第 i 和第 i+1 个出口之间的距离,DN 是第 N 和第 1 个出口之间的距离。同行数字间以空格分隔。 第二行给出正整数 M (≤ 104)。随后 M 行,每行给出一对出口的编号(出口从 1 到 N 顺序编号)。题目保证公路全长不超过 107。

输出

输出 M 行,每行给出对应输入的一对出口之间的最短距离。

样例输入

5 1 2 4 14 9
3
1 3
2 5
4 1

样例输出

3
10
7
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; using namespace std; int main() {     int N;     cin &gt;&gt; N;     vector&lt;int&gt; distances(N);     for (int i = 0; i &lt; N; ++i) {         cin &gt;&gt; distances[i];     }     vector&lt;int&gt; prefixSum(N + 1, 0);     for (int i = 0; i &lt; N; ++i) {         prefixSum[i + 1] = prefixSum[i] + distances[i];     }     int M;     cin &gt;&gt; M;     for (int i = 0; i &lt; M; ++i) {         int start, end;         cin &gt;&gt; start;         cin &gt;&gt; end;         if (start &gt; end) {             swap(start, end);         }         int sum = prefixSum[end - 1] - prefixSum[start - 1];         int total = prefixSum.back();         cout &lt;&lt; min(sum, total - sum) &lt;&lt; endl;     }     return 0; }</pre>
这道题暂未补解析。
4. 简答题

子串与子列

子串是一个字符串中连续的一部分,而子列是字符串中保持字符顺序的一个子集,可以连续也可以不连续。例如给定字符串 atpaaabpabtt,pabt 是一个子串,而 pat 就是一个子列。

现给定一个字符串 S 和一个子列 P,本题就请你找到 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。

时间限制:1000

内存限制:65536

输入

输入在第一行中给出字符串 S,第二行给出 P。S 非空,由不超过 104 个小写英文字母组成;P 保证是 S 的一个非空子列。

输出

在一行中输出 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。

样例输入

atpaaabpabttpcat
pat

样例输出

pabt
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;string.h&gt; int main(){     char s[10001], p[10001];     int i, j, t = 0, len, min = 10001, m, n, k = 0, flag = 0;     scanf("%s\n%s", s, p);    while(1){         for(i = 0;i &lt; strlen(p);i++){            if(!i){                for(j = t + k;j &lt; strlen(s);j++){                    if(s[j] == p[i]){                        k = 1;                        break;                    }                }                t = j;            }else{                 for(j++;j &lt; strlen(s);j++){                     if(s[j] == p[i]) break;                 }            }            if(j == strlen(s)){                flag = 1;               break;            }         }         if(flag == 1) break;         len = j - t + 1;         if(len &lt; min){             min = len;             m = t;             n = j;         }     }     for(i = m;i &lt;= n;i++) printf("%c", s[i]);     return 0; }</pre>
这道题暂未补解析。
5. 简答题

拼大数

如何随机生成一个有 n 位数的大数呢?一种方法是,找到 n 个小朋友,每人发一张卡片,卡片一面写着编号(这里假设小朋友们从 1 到 n 编号),另一面让他们随便写下一个 1 位数字。然后让小朋友们把自己的卡片在墙上钉成一排,要求一张挨着一张,按他们的编号升序排列,显示他们自己写的数字。

但是,让十万个孩子都按指令行动,可太难了。结果是卡片乱七八糟满墙都是,有些甚至显示的不是正确的面。例如第 23 号小朋友在卡片上写了 8,我们应该在墙上看到 8,但是却看到了 23…… 你的任务就是把这些卡片整理好,得到我们真想要拼成的大数。

时间限制:6000

内存限制:65536

输入

输入第一行给出一个正个整数 n (≤ 105),随后 n 行,每行按 n1 n2的格式给出一张卡片两面的数字。

输出

在一行中输出我们真想要拼成的 n 位大数。 如果卡片两面都是 1 位数,那么就很难说哪个数字是编号,哪个数字是小朋友自己写的,所以解可能是不唯一的。这时候需要输出能得到的最小的数字。

样例输入

12
7 11
8 9
3 1
2 12
4 6
10 0
5 1
2 5
6 8
1 4
7 2
9 3

样例输出

359114268072
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; using namespace std; int main() {     int n;     cin &gt;&gt; n;     vector&lt;priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, greater&lt;pair&lt;int, int&gt;&gt;&gt;&gt; pq(n + 1);     vector&lt;pair&lt;int, int&gt;&gt; cards(n);     for (int i = 0; i &lt; n; ++i) {         int a, b;         cin &gt;&gt; a &gt;&gt; b;         cards[i].first = a;         cards[i].second = b;         // Check if a is a valid id and b is a valid digit         if (a &gt;= 1 &amp;&amp; a &lt;= n &amp;&amp; b &gt;= 0 &amp;&amp; b &lt;= 9) {             pq[a].emplace(b, i);         }         // Check if b is a valid id and a is a valid digit         if (b &gt;= 1 &amp;&amp; b &lt;= n &amp;&amp; a &gt;= 0 &amp;&amp; a &lt;= 9) {             pq[b].emplace(a, i);         }     }     vector&lt;bool&gt; used(n, false);     vector&lt;int&gt; result(n + 1, -1);     for (int i = 1; i &lt;= n; ++i) {         while (!pq[i].empty()) {             auto [d, idx] = pq[i].top();             pq[i].pop();             if (!used[idx]) {                 used[idx] = true;                 result[i] = d;                 break;             }         }         if (result[i] == -1) {             cout &lt;&lt; "No solution" &lt;&lt; endl;             return 0;         }     }</pre>
这道题暂未补解析。