关于 幂次方 一题的思路+代码（递归）

题目来源：洛谷 P1010 [NOIP1998 普及组] 幂次方

题目描述

任何一个正整数都可以用2的幂次方表示。例如
137=2⁷+2³+2⁰
由此可知，137可表示为：
2(7)+2(3)+2(0)
而7又可以表示为：2(2)+2+2(0)
3可以表示为：2+2(0)
因此137最终表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)

输入描述

一个正整数n(n≤20000)。

输出描述

符合约定的n的0,2表示(在表示中不能有空格)

输入样例1

1315

输出样例1

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

输入样例2

137

输出样例2

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

OP

\

思路

这道题要用递归来处理：

对于每一个大于2的数，都需要通过二进制将其拆为二的幂次和，对于每一个幂次再进行递归处理；

通过构建 tr[i] 来存储 i 的表达式；

通过处理二进制数和构建幂次栈来按顺序存储该数内含有2的哪些幂次，方便接下来的递归与构建字符串。

（对于(13)D,(1101)B，其幂次栈即为$\{3,2,0\}$，代表$13=2^3+2^2+2^1$ ）

还有一部分内容写在注释里了，方便理解。

代码

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

string tr[20004];//tr[i]存储i的表达式

string getst(int n)
{
    if(tr[n][0])return tr[n];//如果构建过串，直接输出
    stack<int>stk;//构建幂次栈
    int c=0,z=n;//z为n的一个拷贝，用于二进制处理；c记录处理到的二进制位数
    while(z)//构建幂次栈
    {
        if(z&1)stk.push(c);
        c++;
        z>>=1;
    }
    while(!stk.empty())
    {
        int z=stk.top();
        stk.pop();
        if(z!=1)//对于一般位，进行递归处理
        {
            tr[n]+="2(";
            tr[n]+=getst(z);//递归
            tr[n]+=')';
        }
        else tr[n]+='2';//如果n的二进制第1位为1，此时z=1，对字符串的贡献仅为‘2’
        if(!stk.empty())tr[n]+='+';//如果不是最右位，就添一个‘+’
    }
    return tr[n];
}

int main()
{
    tr[0]='0',tr[1]="1",tr[2]="2",tr[4]="2(2)";//初始化
    int n;
    cin>>n;
    cout<<getst(n);
    return 0;
}

初始化在函数外会RTE！

ED

\