NOIP 2的幂次方表达式

样例输入

137

样例输出

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

• 思路1:

• code1:

#include <iostream>
using namespace std;
int Pow[16] = {1};

void Divide(int n){
	bool flag = true;
	while(n > 0){
		if(!flag) printf("+");
		else flag = false;
		if(n == 1){
			printf("2(0)");	
			return;
		} 
		if(n == 2){
			printf("2");
			return;	
		} 	
		if(n == 3){
			printf("2+2(0)");
			return;	
		} 	
		for(int j = 15; j >= 2; --j){
			if(Pow[j] <= n){
				//分解n的第一个（最大的）因子的二次幂的幂次(Pow[i]=2^i)即Divide(i) 
				//因为4 = 2(2),第一次分解n的时候,已经相当于把4等价于2(2)，真正要分解的是()里面的2 
				printf("2(");
				Divide(j);
				printf(")"); 
				n -= Pow[j];
				break;				
			}

		}	
	}
}

int main(){
	int x;
	scanf("%d", &x);
	for(int i = 0; i < 16; ++i){
		Pow[i+1] = Pow[i] * 2;
	}
	Divide(x);
}