P1010 [NOIP1998 普及组] 幂次方
题目描述
任何一个正整数都可以用 22 的幂次方表示。例如 137=27+23+20137=27+23+20。
同时约定方次用括号来表示，即 ��ab 可表示为 �(�)a(b)。
由此可知，137137 可表示为 2(7)+2(3)+2(0)2(7)+2(3)+2(0)
进一步：
7=22+2+207=22+2+20 ( 2121 用 22 表示)，并且 3=2+203=2+20。
所以最后 137137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)2(2(2)+2+2(0))+2(2+2(0))+2(0)。
又如 1315=210+28+25+2+11315=210+28+25+2+1
所以 13151315 最后可表示为 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。
输入格式
一行一个正整数 �n。
输出格式
符合约定的 �n 的 0,20,2 表示（在表示中不能有空格）。
输入输出样例
输入 #1复制
1315
输出 #1复制
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
说明/提示
【数据范围】
对于 100%100% 的数据，1≤�≤2×1041≤n≤2×104。
这里给大家提供两种解法
—— 一种很朴实 一种很高级 ——
++其实是高级的那种解法很少人写++
----括号及加号的添加我放在后面写了----
模拟递归
这个算法很多人都会写了，思路如下：
- 算出2的多少次幂最接近给出的n；
- 用原来n的数减去2的幂，如果这个数大于2，继续对新的n进行搜索；
- 如果幂大于2，对幂进行上述搜索；
- 一旦输入函数的数为0（2的0次幂）或1（2的1次幂）或2（2的二次幂），输出；
至此，思路就很清晰了，那么我就上代码吧（很多人都会了不详解了）
//认真看，杜绝抄袭
#include<cstdio>
using namespace std;
int n;
void search(int x)
{
if(n!=0)
{
int p=1,q=0;
printf("2");
//每一次搜索都要输出2
//如果是1次幂就没必要写2(1)，后面会说;
while(x>=p)
{
++q;
p*=2;
}
//计算幂，由于这里会多算一次，所以计数器q-1;
--q;
if(q==0 || q==2)printf("(%d)",q);
//各种括号的判断
if(q>=3)
{
printf("(");
search(q);
printf(")");
}
x-=p/2;
//上面计数器就是多算了一次，因此p也多乘了一个2;
if(x)//输入的数x为真（最后分解完就成0了，变成假），输出"+";
{
printf("+");search(x);
}
}
}
int main()
{
scanf("%d",&n);
search(n);
return 0;//别忘了写;
}
下面讲一种高级的：
二进制数
我们知道，二进制数表示的其实就是一个正整数分解成为2的幂次方和！
如3用二进制表示为 11 ,从右到左分别是第0位，第1位……
则3=2^1+2^0(只要二进制那位是一，就是2^（这一位）)
再比如10 二进制是1010，则10=2^3+2^1;
大家自己体会一下
下面更高级的：位运算（其实也不高级，就是没人做）
不会位运算的就用上面那种吧，个人觉得位运算更快（普通14ms，位运算11ms）
位运算具体问度娘吧
思路如下：
- 遍历n的二进制（从地位到高位），用数组储存该位为1的位数；如1010（即10），先记录第1位是1，最后记录到第3位是1；
- 遍历完成后，对高位先进行处理（即原来为i++，现在变为i--）
- 该位(就是幂的次数)大于2,，递归再次处理
- 一旦处理到该位小于3，输出；
这里着重点一下括号的添加：
- 在每一次递归搜索前，肯定是搜到2的几次幂，输出"2(";
- 搜索结束后，也有括号")"，但这里也肯定有个"+";
- 最后一个不能输出加号，要进行判断，具体看下面程序；
- 是最后一个不要"+"，不是就写个"+";
- 输入函数的幂小于3时，只要该次幂不等于1，输出（该次幂）
- 由于2的一次幂不会有括号，因此2的加号也不见了，特判幂=1；
- 同第3、4，只要2不是最后一个，输出"2+"，是最后一个输出"2";
二进制代码实现如下：
//认真看，杜绝抄袭
#include<cstdio>
using namespace std;
void ASCII(int m)
{
int i=0,k=m,u=0,h[50];
while(k)//位运算实现；
{
if(k&1)h[++u]=i;
//h[++u]相当于++u，h[u]……
k>>=1;
i++;
}
//据上面写的，u从1开始，无论如何一定会有输出；
while(u)//u为真
{
if(h[u]<3)//具体括号判断；
{
if(h[u]==1 && u-1!=0) printf("2+");
else if(h[u]==1) printf("2");
if((h[u]==0||h[u]==2)&&(u-1!=0)) printf("2(%d)+",h[u]);
else if(h[u]==0||h[u]==2) printf("2(%d)",h[u]);
--u;//搜索下一个；
}
else
{
printf("2(");
ASCII(h[u--]);
//相当于h[u],--u;
//这里千万不能写成 h[--u],否则你会3个WA两个MLE；
if(u!=0)printf(")+");
//由于u进行了自减，此时的u已经是下一个数了；
else printf(")");
//判断括号；
}
}
}
int main()
{
int n;
scanf("%d",&n);
ASCII(n);
return 0;//别忘了写；
}