BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（初中组） 第 22 题

完善程序（共 2 大题 10 小题，每小题 3 分，共计 30 分，每题有且仅有一个正确选项）

第 1 题

（$2$ 的幂表示法）

任何一个正整数都可以用 $2$ 的幂次方表示。例如 $137=2^7+2^3+2^0 $。同时约定次方用括号来表示，即 $a^b$ 可表示为 $a(b)$。由此可知，$137$ 可表示为 $2(7)+2(3)+2(0)$。进一步：$7= 2^2+2+2^0$ ( $2^1$ 用 $2$ 表示)，并且 $3=2+2^0$。所以最后 $137$ 可表示为 $2(2(2)+2+2(0))+2(2+2(0))+2(0)$。又如 $1315=2^{10} +2^8 +2^5 +2+1$，所以 $1315$ 最后可表示为 $2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$。

请补全程序：

#include <bits/stdc++.h>
using namespace std;

int a[16] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768};

void dfs(int n) {
    int k, temp;
    for (int i = 15; i >= 0; i--) {
        if (___①___) {
            k = i;
            break;
        }
    }
    if (k == 0) ___②___;
    else if (k == 1) ___③___;
    else {
        cout << 2 << "(";
        dfs(___④___);
        cout << ")";
    }
    temp = n - a[k];
    if (temp > 0) {
        cout << "+";
       

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是把整数拆成 2 的幂之和，再用特定格式输出。拿到题先别急着填空，先跑一遍逻辑：找不超过 n 的最大 2 的幂，递归处理剩下的部分；特别留意 k=0 和 k=1 是递归的出口，填错直接死循环或格式全乱。

最容易栽跟头的是把出口条件想反，比如以为 k=0 要输出 0 或 2，其实 2^0 就是 2(0)；还有递归时参数传错，把剩余量 temp 传成 n 或 a[k]，导致无限递归或算出负数。另外，判断最大幂时若写成 a[i]==n 会漏掉 n 不是 2 的幂的情况，必须用 a[i]<=n 才能找到最大的那个。

这道题考查的是‘2 的幂表示法’的递归构造，核心是贪心策略：从大到小找不超过 n 的最大 2 的幂，把 n 拆成这一项加上剩余部分，再递归处理剩余部分。题目给出的数组 a[15..0] 存好了 2^0 到 2^15 的值，正好覆盖正整数范围。

先看第①空。循环从 i=15 向下枚举，目的是找到‘不超过 n 的最大 2 的幂’。如果写 a[i]==n，只有当 n 恰好等于某个 2 的幂时才进入，否则循环会一直走到 i=0，k 变成 0，后面逻辑就崩了。所以必须用 a[i]<=n，这样才能保证找到最大的那个 k。选 B。

有了 k，接下来看递归出口。当 k=0 时，对应的是 2^0，按题意要输出 2(0)。注意不要输出 0 或 2，格式必须严格匹配。所以第②空填 cout<<"2(0)";，选 A。

当 k=1 时，对应 2^1，题目约定直接输出 2 即可，不需要括号。所以第③空填 cout<<2;，选 A。

当 k>=2 时，就要输出 2(k) 并递归处理 k 本身。这里有个细节：递归的参数应该是 k 这个指数，而不是 n 或 temp。因为我们要把 k 再拆成 2 的幂之和。所以第④空填 k，选 D。

最后处理剩余部分 temp = n - a[k]。如果 temp>0，说明还有数没表示完，需要输出 + 然后递归处理 temp。所以第⑤空填 temp，选 B。

整个推导过程其实就是模拟题目给的例子：137 先拆出 2^7，剩下 137-128=9；9 再拆出 2^3，剩下 1；1 拆出 2^0，剩下 0。递归下去，最后得到那个长长的表达式。这种贪心 + 递归的思路在信息学竞赛里非常常见，尤其是涉及进制转换、质因数分解等场景。

避坑方面，除了刚才说的出口条件，还要注意题目里的特殊约定：2^1 用 2 表示，不要写成 2(1)。另外，递归参数一定要传指数 k，如果误传 n 或 temp，会导致无限递归或错误输出。最后，输出格式要严格匹配，括号和加号的位置都不能错。

从考频趋势来看，这类‘自定义进制’或‘特殊表示法’的题目在 CSP-J/S 中属于中等偏难，通常出现在第 2-3 题，考察学生对递归和贪心的综合理解。近年真题中类似变形（如三进制、自定义字符集）也时有出现，说明命题人喜欢用‘换皮’的方式考基础算法。预测未来可能会继续考这种需要严格遵循格式输出的递归题，也可能结合 DP 或搜索，难度略有提升，但核心思想不变。