算法很美：天平称重

算法很美：天平称重

题目描述

• 用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。如果有无限个砝码，重量分别是1，3，9，27，81，……等3的指数幂，神奇之处在于用它们可以称出任意整数重量（砝码允许放在左右两个盘中）。

• 本题目要求编程实现：对用户给定的重量，给出砝码组合方案。
  用户输入：5
  程序输出：9-3-1
  用户输入：19
  程序输出：27-9+1

• 要求程序输出的组合总是大数在前小数在后。
  可以假设用户的输入的数字符合范围1~121。

算法思想

• 采用二进制中一一对应的思想，eg：5的三进制为，12，但是我们不能同时加两个1，所以我们将2-3，及将该位变成-1（选取一个负的对应的值3的0次方），并进行进位操作，及对下一位1+1.

代码

public static void main(String[] args) {Scanner sc=new Scanner(System.in);int input&#Int();//转换成三进制数String input_s&#String(input,3);char[] charArray = new StringBuilder(input_s).reverse().toString().toCharArray();//加一为了最后一位进位做准备ArrayList<Integer> resArrayList=new ArrayList<>();for(int i=0;i<charArray.length;i++) {if(charArray[i]=='2') {//将三进制数颠倒放入数组，所以结果每次插在头部resArrayList.add(0,-1);//是最后一个字符if(i==charArray.length-1) {resArrayList.add(0,1);}else {charArray[i+1]+=1;}}else if(charArray[i]=='3'){resArrayList.add(0,0);//是最后一个字符if(i==charArray.length-1) {resArrayList.add(0,1);}else {charArray[i+1]+=1;}}else {resArrayList.add(0,charArray[i]-'0');}}StringBuilder sBuilder=new StringBuilder();for(int i=0;i<resArrayList.size();i++) {(i)==1) {sBuilder.append("+").append((int)Math.pow(3, resArrayList.size()-i-1));}else if ((i)==-1) {sBuilder.append("-").append((int)Math.pow(3, resArrayList.size()-i-1));}}System.out.println(sBuilder.substring(1).toString());}