[洛谷]P1010 幂次方 | CloudingYu的博客

题目描述

任何一个正整数都可以用 $2$ 的幂次方表示。例如 $\displaystyle 137=2^7+2^3+2^0$ 。

同时约定次方用括号来表示，即 $\displaystyle a^b$ 可表示为 $a(b)$ （ $\displaystyle a^b$ 为a的b次方）。

由此可知， $137$ 可表示为 $2(7)+2(3)+2(0)$ 。

进一步：

$\displaystyle 7=2^2+2+2^0$ ( $\displaystyle 2^1$ 用 $2$ 表示)，并且 $\displaystyle 3=2+2^0$ ，

所以最后 $137$ 可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)。

又如 $\displaystyle 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)$ 。

整体思路

看到这道题，相信很多人都第一时间想到了递归。虽然很多大佬用二进制也能完成这道题，但是递归无疑是最容易理解的一种方式。我们不妨定义一个函数 void print(int k){}，用这个函数来打印出 $k$ 的 $2$ 的幂次方表示。

具体实现

我们从 $1$ 开始尝试：当 $k=1$ 时，应输出 ” $2(0)$ ”；

当 $k=2$ 时，应输出 ” $2$ ”；

当 $k=3$ 时，应输出 ” $2+2(0)$ ”；

当 $k=4$ 时，应输出 ” $2(2)$ ”；

当 $k=5$ 时，应输出 ” $2(2)+2(0)$ ”；

$\cdots$

首先，我们发现输出的结果都是由“ $2(0)$ ”和“ $2$ ”组成的，所以递归的终止条件就是 $k=1$ 或 $2$ 。

其次， $k>3$ 后，结果都是由多部分组成的（除了 $2$ 的整数幂），所以不妨先利用循环枚举，将 $k$ 分解为多个 $2$ 的整数幂形式，存在数组中，以便输出。

最后，在输出前几项时，应紧跟着输出 ' $+$ ' ，而最后一项不需要输出 ' $+$ '。

代码实现

#include <iostream>
#include <cstring>
using namespace std;
int pow[17]; // 存储2的所有整数幂的值，数据最大范围是2×10^4，而2^15约等于32768
void print(int k)
{
    int t = 15;
    int a[17];   // 存储k分解后的2的整数幂
    int len = 0; // 计录数组a的长度
    memset(a, 0, sizeof(a));
    while (k > 0) // 循环将k分解为2的整数幂，并存入数组a中
    {
        if (k >= pow[t])
        {
            a[++len] = t; // 存入指数
            k -= pow[t];
        }
        t--;
    }
    for (int i = 1; i <= len; i++) // 循环递归（最后一项不需要‘+’）
    {
        if (a[i] == 0) // 如果这一项指数为0，输出”2（0）“
            cout << "2(0)";
        else if (a[i] == 1) // 如果这一项指数为0，输出”2“
            cout << "2";
        else
        {
            cout << "2(";
            print(a[i]); // 其他情况，输出"2（a[i])"
            cout << ")";
        }
        if (i != len) // 最后一项不需要输出'+'
            cout << '+';
    }
    return;
}
int main()
{
    pow[0] = 1;
    for (int i = 1; i <= 15; i++)
        pow[i] = 2 * pow[i - 1]; // 提前计算2的整数幂，减少计算量
    int n;
    cin >> n;
    print(n);
    cout << endl;
    return 0;
}