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;
}