luogu-P1010 幂次方

NOIP 1998 普及组真题，主要考察递归与分治算法的使用。这道题目虽然是早期真题，但对理解将数字分解并使用递归进行求解非常有帮助。GESP四、五级以上可练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。

luogu-P1010 [NOIP 1998 普及组] 幂次方

题目要求

题目描述

任何一个正整数都可以用 $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)$。

输入格式

一行一个正整数 $n$。

输出格式

符合约定的 $n$ 的 $0, 2$ 表示（在表示中不能有空格）。

输入输出样例 #1

输入 #1

1315

输出 #1

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

说明/提示

【数据范围】

对于 $100\%$ 的数据，$1 \le n \le 2 \times {10}^4$。

题目分析

这道题是一个非常经典的递归与分治思想的结合。题目的要求是将一个正整数不断拆解为 $2$ 的若干次幂之和，然后再对相应的指数继续进行拆解，直到指数变为 $0$ 或 $1$。

1. 拆分为 $2$ 的幂次方

给定的数值 $n$ 可以转换为其二进制形式。每一个等于 $1$ 的二进制位，就代表了一个 $2$ 的若干次幂组合。例如：

• $137$ 的二进制是 10001001，其第 $7$ 位、$3$ 位和 $0$ 位是 $1$。因此 $137 = 2^7 + 2^3 + 2^0$。
• 对其指数进一步分解，$7 = 2^2 + 2^1 + 2^0$，$3 = 2^1 + 2^0$。

2. 递归处理过程

我们可以设计一个递归函数 solve(int n)：

• 首先，寻找能够组合成 $n$ 的每一个最大的二进制位（从大到小）。因为 $n \le 20000$，$2^{14} = 16384$，所以最多从第 $14$ 位开始向下遍历到第 $0$ 位。
• 对于位数为 $1$ 的索引 $i$：
  • 如果 $i = 0$，表示 $2^0$，按题目要求输出 2(0)。
  • 如果 $i = 1$，表示 $2^1$，按题目要求只输出 2 而不是 2(1)。
  • 对于 $i \ge 2$，由于还需要继续拆分，因此格式为 2( 加上递归调用 solve(i) ，最后搭配 ) 。
• 拼接符号控制：在分解同一个数字 $n$ 时，各项之间要有 + 连接，所以我们需要一个标志变量（如 first）来确保第一项之前不输出加号，后面的项输出加号。

3. 总体流程

1. 读取输入的正整数 $n$。
2. 调用 solve(n) 进入递归。
3. 在 solve 内部从大到小（如 $i=14 \rightarrow 0$）遍历，通过位运算 (n >> i) & 1 判断第 $i$ 位是否为 $1$。
4. 如果为 $1$，首先判断是否为当前拆分的第一项，若不是则先输出 + 号。接着根据 $i$ 的值输出特定格式的字符串。如果是 $i \ge 2$ 的情况，继续通过递归嵌套求解。

示例代码

#include <iostream>

// 递归函数，将数字 n 表示为 2 的幂次方形式
void solve(int n) {
    bool first = true; // 标志变量，用于控制 '+' 的输出，确保第一项前没有 '+'
    // n <= 20000，2^14 = 16384 是在范围内的最大 2 的幂，因此从 14 遍历到 0
    for (int i = 14; i >= 0; i--) {
        // 利用位运算判断 n 二进制的第 i 位是否为 1
        if ((n >> i) & 1) {
            // 如果不是按位拆分出来的第一项，则需要输出分隔符 '+'
            if (!first) {
                std::cout << "+";
            }
            first = false; // 当前项处理后，将标志位置为 false

            // 按照题目要求格式处理特殊的指数 0 和 1
            if (i == 0) {
                std::cout << "2(0)"; // 2^0 的情况
            } else if (i == 1) {
                std::cout << "2";    // 2^1 的情况直接输出为 2
            } else {
                // 如果指数 i >= 2，则按规定输出 '2('，并对指数 i 继续递归求解
                std::cout << "2(";
                solve(i);
                std::cout << ")";
            }
        }
    }
}

int main() {
    int n;
    std::cin >> n; // 读取输入的正整数 n

    solve(n);      // 启动递归求解
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号