詳細解析藍橋杯練習系統經典試題：幂方分解

問題描述
　　任何一個正整數都可以用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);
		}
		
	}
}