CSP-J 2024 阅读程序一二三
答案版
一、阅读程序题
点击“显示答案”查看答案和解析。
（一）素数统计（1～5题）
C++ 程序代码
#include <iostream>using namespace std;bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true;}int countPrimes(int n) { int count = 0; for (int i = 2; i <= n; i++) { if (isPrime(i)) count++; } return count;}int sumPrimes(int n) { int sum = 0; for (int i = 2; i <= n; i++) { if (isPrime(i)) sum += i; } return sum;}int main() { int x; cin >> x; cout << countPrimes(x) << " " << sumPrimes(x) << endl; return 0;}
程序功能
程序判断 2 到 n 之间的素数，并输出素数的个数和素数之和。
执行过程
isPrime通过试除判断素数。countPrimes统计素数个数，sumPrimes累加素数之和。
关键语句
i * i <= n 只检查到平方根，可以减少试除次数。
（二）费用动态规划（6～11题）
C++ 程序代码
#include <iostream>#include <vector>using namespace std;int compute(vector<int>& cost) { int n = cost.size(); vector<int> dp(n+1, 0); dp[1] = cost[0]; for (int i = 2; i <= n; i++) { dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]; } return min(dp[n], dp[n-1]);}int main() { int n; cin >> n; vector<int> cost(n); for (int i = 0; i < n; i++) cin >> cost[i]; cout << compute(cost) << endl; return 0;}
程序功能
程序用动态规划计算到达终点的最小累计费用。
执行过程
dp[i]表示到达第 i 个位置的最小费用。- 状态转移为
dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]。 - 最后比较
dp[n]和dp[n-1]。
关键语句
dp[0]=0 是动态规划的边界条件。
（三）递归计算（12～17题）
C++ 程序代码
#include <iostream>#include <cmath>using namespace std;int customFunction(int a, int b) { if (b == 0) return a; return a + customFunction(a, b-1);}int main() { int x, y; cin >> x >> y; int result = customFunction(x, y); cout << pow(result, 2) << endl; return 0;}
程序功能
customFunction(a,b) 通过递归完成 a 的 b+1 次累加，主函数再求平方。
执行过程
b==0时返回 a，递归结束。- 否则保留一个 a，并递归计算
customFunction(a,b-1)。
关键语句
b 每次减 1；若 b 为负数，则无法到达终止条件。
二、完善程序
（一）判断平方数（18～22题）
C++ 程序代码
#include<iostream>#include<vector>using namespace std;bool isSquare(int num) { int i = ***①***; int bound = ***②***; for (; i <= bound; ++i) { if (***③***) { return ***④***; } } return ___⑤___;}int main() { int n; cin >> n; if (isSquare(n)) { cout << n << " is a square number" << endl; } else { cout << n << " is not a square number" << endl; } return 0;}
程序功能
程序判断 num 是否为完全平方数。
执行过程
- 从 1 枚举到
floor(sqrt(num))。 - 若发现
num == i * i，返回 true。 - 遍历结束仍未找到时返回 false。
关键语句
判断必须使用 ==，不能写成赋值符号 =。
（二）汉诺塔问题（23～27题）
C++ 程序代码
#include <iostream>#include <vector>using namespace std;void move(char src, char tgt) { cout << "从柱子" << src << "挪到柱子" << tgt << endl;}void dfs(int i, char src, char tmp, char tgt) { if (i == ***①***) { move(***②***); return; } dfs(i - 1, ***③***); move(src, tgt); dfs(***⑤***, ***④***);}int main() { int n; cin >> n; dfs(n, 'A', 'B', 'C');}
程序功能
程序用递归解决汉诺塔问题，把圆盘从 A 柱移动到 C 柱。
执行过程
- 先把 i-1 个盘从 src 借助 tgt 移到 tmp。
- 把最大盘从 src 移到 tgt。
- 再把 i-1 个盘从 tmp 借助 src 移到 tgt。
关键语句
i==0 是递归终止条件。
答案汇总：1A，2B，3A，4B，5B；6A，7B，8B，9A，10B，11A；12B，13A，14A，15B，16B，17D；18A，19B，20D，21C，22D；23A，24B，25B，26B，27C。