2的幂次方表示（递归）

2的幂次方表示

任何一个正整数都可以用2的幂次方表示。例如：

137=27+23+20
           

同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：

2(7)+2(3)+2(0)
           

进一步：7=22+2+20（21用2表示）

3=2+20
           

所以最后137可表示为：

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

又如：

1315=210+28+25+2+1
           

所以1315最后可表示为：

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

输入

一个正整数n（n≤20000）。

输出

一行，符合约定的n的0，2表示（在表示中不能有空格）。

样例输入

137

样例输出

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

个人思路： 递归

去找规律，以及边界条件。2的幂次方表示，离不开除以2，以及除了多少个2，所以函数convert(m,n)，m表示现在正处理的数，n表示上一个处理的数可以用几个二次幂表示，相当于存储了上一个数。如果m为奇数，就需要将m分解为1+(m-1)。再对m-1（此时是偶数）和1分别处理。

当除尽且n大于三时，像2的7次方，7还需要分解，这时就需要写套娃代码了，将7再去处理,

if(m==1&&n>=3) 
	{
		cout<<"2(";
		convert(n,0);
		cout<<")";
	}
           

最后找边界，因为输出时只有2和0两个数，可知正整数都可以分解为1,2的和，即2的0次方，2的1次方，当然2的2次方需要单独列出来。

convert(1,2) 输出2（2）

convert(1,1)输出2

convert(1,0)输出2（0）

（欢迎小伙伴们在评论区留下自己的意见~）

心得： 第一次独立写了一道递归，终于觉得有所进步了！！o(╥﹏╥)o！！一开始没思路，去搜答案，但是大部分用的位运算，因为我没看懂，所以抽了两小时写了个菜鸡水平的递归。

最后祝各位元旦快乐，bug越写越少，头发浓密。= ~ =

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
void convert(int m,int n)
{
	int i;
	int flag_odd=0;//判断当前处理数字的奇偶，因为奇数需要分出一个处理 
	if(m%2==1) flag_odd=1;
	//m==1表示当前处理数字除尽了，必须打印了 
	if(m==1&&n==0) cout<<"2(0)";//2的0次方 
	else if(m==1&&n==1) cout<<"2";//2的1次方 
	else if(m==1&&n==2) cout<<"2(2)";//2的2次方 
	else if(m>1) //如果当前数未除尽 
		{
			if(flag_odd)//奇数 
			{
				convert(m/2,n+1);
				cout<<"+";
				convert(1,n);//分数一个1处理，n不变 
			}
			else //偶数 
			 	convert(m/2,n+1);
		}
	else if(m==1&&n>=3)//需要套娃的情况，次方还能分解 
	{
		cout<<"2(";
		convert(n,0);
		cout<<")";
	}
} 
int main()
{
	int i,k,m;
	cin>>m;
	convert(m,0);
	cout<<endl;
}