問題描述 任何一個正整數都可以用2進制表示，例如：137的2進制表示為10001001。 將這種2進制表示寫成2的次冪的和的形式，令次冪高的排在前面，可得到如下表達式：137=2^7+2^3+2^0 現在約定冪次用括號來表示，即a^b表示為a（b） 此時，137可表示為：2（7）+2（3）+2（0） 進一步：7=2^2+2+2^0 （2^1用2表示） 3=2+2^0 所以最后137可表示為：2（2（2）+2+2（0））+2（2+2（0））+2（0） 又如：1315=2^10+2^8+2^5+2+1 所以1315最后可表示為： 2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0） 輸入格式 正整數（1<=n<=20000） 輸出格式 符合約定的n的0，2表示（在表示中不能有空格） 樣例輸入 137 樣例輸出 2(2(2)+2+2(0))+2(2+2(0))+2(0) 樣例輸入 1315 樣例輸出 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0) 提示 用遞歸實現會比較簡單，可以一邊遞歸一邊輸出
思路： 觀察樣例：1315=2^10+2^8+2^5+2+1 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0) 先找出整數n的最大2次冪k，然后令n=n-2^k，繼續計算n的最大2次冪，直到n=0或n=1為止，此處可以用遞歸實現。另外在遞歸的同時進行打印時需要注意2^2=2(2)，2^1=2，2^0=2(0)，括號的打印需要條件判斷。
import java.util.Scanner;public class Test { public int calculate(int n) {// 計算整數n的最大2次冪 int i = -1; while (Math.pow(2, i) <= n) { i++; } i--; return i; } public void PRint(int n) { switch (n) { case 0: System.out.print("0");//n=0時，2(0) return; case 1: System.out.print("2");//n=1時，2(1) = 2,括號的顯示與n獨立 return; case 2: System.out.print("2");//n=2時，2(2) return; default: break; } int k = calculate(n); if (k >= 2 || k == 0) {//2(2),2(1),2(0)中，2(1)直接用2替換，不需要添加2(),直接打印 System.out.print("2("); print(k); System.out.print(")"); } else { print(k); } int m = n - (int) Math.pow(2, k); while (m > 0) { int t = calculate(m); System.out.print("+"); if (t >= 2 || t == 0) {//條件判斷的理由同上 System.out.print("2("); print(t); System.out.print(")"); } else { print(t); } m = m - (int) Math.pow(2, t); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); Test t = new Test(); t.print(n); }}新聞熱點
疑難解答
