问题描述
任何一个正整数都可以用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表示(在表示中不能有空格)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
package algo12; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); in.close(); div(n); } private static void div(int n) { if (n == 0) { System.out.print(0); return; } char[] cs = Integer.toBinaryString(n).toCharArray(); boolean isOutputFirst = false; for (int i = 0; i < cs.length; i++) { if (cs[i] == '1') { if (isOutputFirst) { if (cs.length - i - 1 == 1) { System.out.print("+2"); } else { System.out.print("+2("); div(cs.length - 1 - i); System.out.print(")"); } } else { if (cs.length - i - 1 == 1) { System.out.print(2); } else { System.out.print("2("); div(cs.length - 1 - i); System.out.print(")"); } isOutputFirst = true; } } } } } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼