蓝桥杯算法训练VIP-幂方分解 （C++代码）

解题思路:

主要在于递归分治函数

运用位运算查找当前需要进行分解数的1的最高位,然后先打印一个2,再对得到的幂进行判断,是1直接不用处理,是2或0就按代码中进行打印.不是0,1,2就对幂进行递归分解.最后判断剩余的减去2^i的数是否还需要进行分解,需要分解就先打印一个"+".

注意事项:运用位运算比较方便

参考代码:

#include <bits/stdc++.h> //蓝桥 幂方运算:在洛谷那里练过一模一样的题目,但那个时候不是我自己写的... 

using namespace std;

void fenzhi(int n)

{

int i;

for(i=20;i>=0;i--) //找到当前正在幂方分解的最高位1 

{

if(n&(1<<i))

break;

}

printf("2"); //先打印个2 

if(i==2 || i==0) //i==1时不做处理

printf("(%d)",i);

if(i!=2 && i!=0 && i!=1) //如果得到i也需要进行分解. 

{

printf("(");

fenzhi(i);

printf(")");

}

if(n-pow(2,i)!=0) //如果当前n没有被分解完

{

int temp=n-pow(2,i);

printf("+");

fenzhi(temp);

}

return ;

}

int main()

{

int N;

scanf("%d",&N);

fenzhi(N);

return 0;

}