AcWing每日一題 3483.2的幂次方（遞歸）

2的幂次方

原題連結

每個正數都可以用指數形式表示。

例如，137=27+23+20。

讓我們用 a(b) 來表示 ab。

那麼 137 可以表示為 2(7)+2(3)+2(0)。

因為 7=22+2+20，3=2+20，是以 137 最終可以表示為 2(2(2)+2+2(0))+2(2+2(0))+2(0)。

給定一個正數 n，請你将 n 表示為隻包含 0 和 2 的指數形式。

資料範圍

1≤n≤20000,

每個輸入最多包含 100 組資料。

輸入格式

輸入包含多組資料。

每組資料占一行，一個正數 n。

輸出格式

每組資料輸出一行，一個指數形式表示。

輸入樣例：

1315

輸出樣例：

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

1998年NOIP普及組題目，一個比較簡單的遞歸，特判輸入為1的情況即可

AC代碼：

//手機輕按兩下代碼可以全屏看代碼哦
#include<bits/stdc++.h>
using namespace std;
void f(int x){
	if(x==2){//如果x為2,無法繼續細分，輸出2後return 
		printf("2");
		return ;	
	}
	if(x==1){//x為1的情況對應前面2^1,是以輸出2 
		printf("2");
		return ;
	}
	if(x==0){ 
		printf("0");
		return ;
	}
	bool flag=0;
	for(int i=14;i>=0;--i){
		if((1<<i)&x){
			if(flag)printf("+");//如果不是第一個輸出則輸出加号 
			flag=1;
			if(i!=1)printf("2(");//特判i是否等于1，如果等于1即2的1次方 
			f(i);//遞歸          //不需要輸出2(1),輸出2即可 
			if(i!=1)printf(")");
		}
	}
}
int main(){
	int n;
	while(cin>>n){
		if(n!=1)f(n);
		else printf("2(0)");
		printf("\n");
	}
	return 0;//保持好習慣，和點贊一樣
}