蓝桥杯算法训练VIP-幂方分解（java代码）

解题思路:
        将需要转化的数转化成二进制数即可，题中的137可以转化为10001001，根据进制转化的规则，很容易得到137 = 2^7+2^3+2^0，7,3,0分别为10001001从末尾从零开始数那三个1的下标。然后在递归的进行7,3,0的相关操作。直到不能分解为止，也就是分解到2、1、0时候，2可以直接输出2,1可以直接输出2（0），0不需要输出。详情参考代码注释

注意事项:
        注意事项已在代码注释中给出。
参考代码:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();//输入的数
		Recursion(n);//递归
	}
	
	public static void Recursion(int n) {
		ArrayList<Integer> binary = convertBinary(n);//存储得到的n转化成的二级制集合
		for (int i = binary.size()-1; i >= 0; i--) {//因为题设是按指数递减输出的，故从集合末端开始遍历
			if (binary.get(i) != 0) {//如果遍历到的元素值不为0.就代表有值为2（i）的家数
				if(i >= 2) {//如果i大于等于2，就说明还可以继续分解，按if语句里的输出
					System.out.print("2(");//
					Recursion(i);//继续分解i；
					Boolean ishave = false;//记录后面是否还有输出
					for(int j = i-1; j >= 0; j-- ) {//从i开始遍历，如果未遍历的二进制集合值全是0，就代表后面已经没有了
						if(binary.get(j) != 0) {//如果出现了非零数就代表后面还有输出，跳出循环
							ishave = true;
							break;
						}
					}
					if(ishave) {//如果后面还有输出就需要补上+号，如果没有则直接输出）即可
						System.out.print(")+");
					}else {
						System.out.print(")");
					}
				}else if (i == 1) {//如果i=1，就代表为2（1），直接输出2即可
					if(binary.get(i-1) == 0) {//因为i=1就代表后面只可能出现2（0），如果集合里下标为0的值为0就代表没有2（0）无须补上+号
						System.out.print("2");
					}else {
						System.out.print("2+");
					}
				}else if (i == 0) {//如果i = 0，直接输出2（0）即可，后面一定没有输出了
					System.out.print("2(0)");
				}
			}
		}
	}
	
	//除基取余法将n转化为二进制集合，4的转化的二进制集合为001，代表4可以转化为0个2（0），0个2（1），1个2（2）相加
	public static ArrayList<Integer> convertBinary(int n) {
		ArrayList<Integer> binary = new ArrayList<Integer>();
		while (n > 0) {
			binary.add(n % 2);
			n = n/2;
		}
		return binary;
	}
}