原题链接

题目描述

用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。

如果只有 5 个砝码，重量分别是 1，3，9，27，81。则它们可以组合称出 1 到 121 之间任意整数重量（砝码允许放在左右两个盘中）。

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

 解：

观察到1,3,9,27,81均为3的倍数，故考虑利用进制来做：

每个砝码可以放左盘或者右盘或者不放，刚好有三种状态，例如：5 = 12₍₃₎

"1"可以表示取用该砝码,由于一个砝码只能取用一次,那如何"2"呢,进一步考虑,可以采取进位的方式:

1 2 = 2 -1 = 1 -1 -1

 

让"-1"表示该砝码放在右盘即可。

import java.util.*;
public class Main {
    static List<Integer> res = new ArrayList();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int carry;
        int num;
        while(N > 0){
          carry = (N % 3 == 2)? 1:0;
          num = (N % 3 == 2)?-1:(N + carry)%3;
          res.add(num);
          N = N / 3 + carry;
        }
         System.out.print((int)Math.pow(3,res.size() - 1));
          for(int i = res.size() - 2; i >= 0; i--){
            if(res.get(i) == -1)
                System.out.print("-"+(int)Math.pow(3,i));
            else if(res.get(i) == 1)
                System.out.print("+"+(int)Math.pow(3,i));
           }
    }
}