天平称重：变种3进制

题目：用天平称重时，我们希望用尽可能少的砝码祝贺称出尽可能多的重量。

如果有无限个砝码，但他们的重量分别是1，3，9，27，81....等3的指数幂神奇之处在于用他们的组合可以称出任意整数重量（砝码允许放在左右两个盘中）。

本题目要求编程实现：对用户给定的重量，给出砝码组合方案，重量<1000000。

例如：

用户输入：

5

程序输出：

9-3-1

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int weight = input.nextInt();String res = scheme(weight);System.out.println(res);}public static String scheme(int weight){String str = new StringBuilder(Integer.toString(weight,3)).reverse().toString();char[] cArr = str.toCharArray();List<Integer> list = new ArrayList<>();for(int i =0;i<cArr.length;i++){if(cArr[i] == '2'){list.add(-1);if(i == cArr.length-1){list.add(1);}else{cArr[i+1]++;}}else if(cArr[i] == '3'){list.add(0);if(i == cArr.length-1){list.add(1);}else{cArr[i+1]++;}}else{list.add(cArr[i]-'0');}}//System.out.println(list);StringBuilder sb = new StringBuilder();for(int i =list.size()-1;i>=0;i--){int res = pow(3,i)*list.get(i);if(res == 0)continue;if(res>0 && i!=list.size()-1){sb.append("+");}sb.append(res);}return sb.toString();}public static int pow(int a,int n){if(n == 0)return 1;if(n == 1) return a;int res = a;int nn = 1;while(nn*2<n){nn*=2;res *= res;}return res*pow(a,n-nn);}
}