洛谷题解 P1010 【幂次方】
程序员文章站
2022-05-08 22:52:32
...
在我的博客食用效果更佳!https://www.cbw2007.tk/articles/luogu-P1010-sol/,文章最初发表于201975月12日。更多见在不同的网站浏览本站内容
分析
看各位大佬都用二进制等高端算法,蒟蒻都不会啊!QAQ只好用了最朴素的递归与模拟。
这里要理清这两点:
- 在分解一个数时,不能出现重复的,因为。
- 分解出来的幂的指数要尽可能的大。
然后,程序的具体思路是:
- 先找一个尽可能大的幂。
- 特判,将指数为0和1的单独挑出来输出。
- 递归指数。
- 减去已经找到的幂次方数,返回第一步。
这样说可能有点迷,上代码更简单!
核心代码
void dfs(int k)//传入一个数
{
while (k!=0)//如果这个数还没有处理完
{
int t=2,i;//指数为1
for (i=1;t<=k;i++)//指数不断增加,直到当前幂次方已经大于k
t*=2;
i--; t/=2;//因为这时候t已经比k大了,所以指数减一
if (i==0)//如果指数为零
{
cout<<"2(0)";
k-=1;//同k-=t
goto last;
}
if (i==1)//如果指数为一
{
cout<<"2";
k-=2;//同k-=t
goto last;
}
cout<<"2(";
dfs(i);//递归指数
// cout<<i;//可以把这一步取消注释,把上一步进行注释,观察指数未分解时是否正确
cout<<")";
k-=t;//减去已经找到的幂次方数
last:
if (k!=0)
cout<<"+";//如果k没处理完,输出加号
}
}