洛谷——P1010幂次方

原题链接
仔细读题可以看出，这道题本质上是递归。比如对于8,8=2^3，而继续对3分析3又可拆解为2的一次幂和2的零次幂。因此，我们采用递归来解决这道题。

#include<iostream>
using namespace std;
int a[15];
//这个是让数组储存2的幂次方的结果
void POW() {
	a[0] = 1;
	for (int i = 1; i < 15; i++)
		a[i] = a[i - 1] * 2;
}
void print(int n) {
//无论如何，第一个输出的总会是2
	cout << 2;
	int j = 14;
//我们从最大的2的幂次开始，逐渐减少，找到最接近n但比n小的那个	
	while (n < a[j])
		j--;
//这里是特判，如果是零次幂或是二次幂，直接就输出(j)	
//ps:一次幂什么都不输
	if (j == 0 || j == 2)
		cout << "(" << j << ")";
//否则，先输出(，对j递归，在输出）		
	if (j >= 3) {
		cout << "(";
		print(j);
		cout << ")";
	}
	n -= a[j];
//接着要考虑n剩余的部分，如果还有就要输出+，并对剩余部分递归	
	if (n) {
		cout << "+";
		print(n);
	}

}
int main()
{
	POW();
	int n;
	cin >> n;
	print(n);
	return 0;
}