详细解析蓝桥杯练习系统经典试题：幂方分解

问题描述
　　任何一个正整数都可以用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表示（在表示中不能有空格）
           

这道题是一道经典的模拟递归问题，在很多oj平台上都有这道题的出现。这道题是可以用二进制算的。但作为一道经典的模拟递归题目我们还是老老实实做吧。

首先，这题的终止条件是0或者2，但也可以把1写作2(1)作为终止条件。一个递归问题除了需要终止条件，还需要状态的变化，就是规模要不断缩小，这样递归才有意义。这里要有两部分要进行递归。一个数可能分成多个数，每个数可能都要递归，另外，每个数它的幂可能大于2，这里也需要进行递归。

算法思路：

1.找到最接近n这个数的2的幂次方

2.对这个幂的进行判断，如果大于2就要把这个幂次方当作一个函数新的n进行递归

3.用n减去这个最接近n的2的幂次方，如果剩下的数不等于0则进行递归，同时要添置＋号

4.如果n小于等于2了，直接用if终止递归

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		f(n);
	}
	public static void f(int n) {
		if(n==0) {           //这3个if都是终止条件
			System.out.print("0");
			return;
		}
		if(n==1) {
			System.out.print("2(0)");
			return;
		}
		if(n==2) {
			System.out.print("2");
			return;
		}
		System.out.print(2);    //如果在上面if没有被终止，那么肯定n>2的，那么肯定要进行递归，所以这里先写个2
		int sum=1,pow=0;//sum最接近n的2的幂次方数，pow代表的幂方
		while(sum<=n) {
			pow++;
			sum*=2;
		}
		sum/=2;   //这里肯定是多算了一次，因为sum要大于n才停止循环
		pow--;
		if(pow==0||pow==2) {      //如果这个幂是0或者2可以直接出答案，如果是1则不用处理
			System.out.print("("+pow+")");
		}
		if(pow>=3) {  //如果大于3的话，肯定还要分解
			System.out.print("(");
			f(pow);
			System.out.print(")");
		}
		n-=sum;   //把n减掉最接近n的2的幂次方这个数
		if(n!=0) { //如果剩下的数不为0就要继续递归，并添置＋号
			System.out.print("+");
			f(n);
		}
		
	}
}