问题描述 任何一个正整数都可以用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); }}新闻热点
疑难解答
