遞歸-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)

分析：

對于137可先将其分解為2(7)+2(3)+2(0),再用同樣的方法将7分解為2(2)+2+2(0)，将3分解為2+2(0)，最終137表示為2(2(2)+2+2(0))+2(2+2(0))+2(0)。很明顯，這道題需要用遞歸來做。

函數fun接受一個參數，為要分解的值。觀察示例可知，當參數為1或2時可退出遞歸并輸出2(0)或2。先設定一個power表示指數，curr表示2的power次方值，當curr小于參數時curr乘2，power加1。curr大于參數時此時的curr / 2 為最接近參數的2的n次方，指數為power 減1。

源碼：

#include <iostream>
using namespace std;
 
void fun(int num){
    //結束條件，分解結束
    if(num == 1){
    	cout << "2(0)";
		return; 
	} 
	else if(num == 2){
		cout << "2";
		return ;
	}
	
	//curr 臨時變量，power 指數 
	int curr = 1;
	int power = 0;
	 
	while(curr <= num){
		curr *= 2;
		power++;
	}
	power--;
	
	if(num == curr / 2){
		cout << "2(";
		fun(power);
		cout << ")";
	}
	else{
		if(curr / 2 == 2){
			cout << "2";
			cout << "+";
			fun(num - curr / 2);
		}
		else{
			cout << "2(";
			fun(power);
			cout << ")+";
			fun(num - curr / 2);
		}
	}
}

int main(){
    int num;
    cin >> num;
    fun(num);
    return 0;
}