题目_数学问题

分析

1， 3， 9， 27， 81，……
3^0，3^1，3^2，3^3，3^4，……
题目中描述 三的指数幂 提示并联想到用3进制解决问题。

我们先假设为二进制：

二进制转换： 每位(0\1)乘以2的0、1、2..次方
例如：5
其二进制是 101 >> 12^2+02^1+1*2^0=4+0+1
砝码一遍 放 4 1 即可
如果是 19 其二进制为(10011)(16+2+1)
| 16 | 8 | 4 | 2 | 1 |
| --- | --- | --- | --- | --- |
|1|0|0|1|1|
一边放 16 2 1 即可

那么换三进制来说

三进制类转换 每位(0\1\2)乘以3的0、1、2..次方
进制从右边开始算 27 9 3 1
19 就是 201 >> 23^2+13^0
5 就是 12 >> 1*3^1+2^3^0
但是 1代表要取一个重量为3的砝码，2代表要取两个重量为1的砝码，但是题目说明是 分别 所以不能重用
同时也说做砝码数最少 重量最大 且为左右砝码盘 可以相互抵消
再以5为例 我们放砝码 组合方式是（9 -3 -1）
所以 我们再把 5的三进制变一下
(1,2) +1 =(2,3)
因为三进制逢3进1 所以=(3,0) 我们再减一个1 = (2,-1) 但是2 还是没法表示2(选两个不允许)
把其中的2转换 左盘和右盘 (1,-1,-1) 从两个放一个盘 到 更大的放到一个盘 减去小的
手算一下 结果还是一样是5 怎么理解2 的这一步呢 类比 2进制 左移 倍数扩大 然后 再减去一半
想明白了 就感觉很妙
手算想一下也就明白啦 或者看代码哈
再举例 7 =(2,1) 把2向前进一位 =(1,-1,1) 即 (9,-3,1)
所以 现在转换到了

代码

package BlueCup.Six_MathQuestion;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Case1_天平称重 {
    //
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        convert(N);//转特殊三进制
    }

    private static void convert(int N) {
        //转换三进制
        final String x = Integer.toString(N, 3);
        //翻转 字符数组 到着算可能越界 所有翻转从左到右
        char[] arr = new StringBuilder(x).reverse().toString().toCharArray();//翻转
        //容器处理之后的 0 -1 1
        List<Integer> list=new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]=='2') {
                list.add(0, -1);//-1 插到开头
                if (i == arr.length - 1) {//到尽头
                    list.add(0, 1);//最后一个字符  插入1 因为是尽头 没进位了
                } else {
                    ++arr[i + 1];//否则下一位+1
                }
            }else if(arr[i]=='3'){
                list.add(0,0);
                //更高位进1
                if(i==arr.length-1){
                    list.add(0,1);
                }else{
                    ++arr[i+1];
                }
            }else{
                list.add(0,arr[i]-'0');//不是0、就是1
            }

        }
        StringBuilder sb = new StringBuilder();//注意是逆序 进制
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == 1) sb.append("+").append((int) Math.pow(3, list.size() - i - 1));
            if (list.get(i) == -1) sb.append("-").append((int) Math.pow(3, list.size() - i - 1));
            //0直接pass咯
        }
        //因为结果的第一位一定是 正的 所以我能把它符号丢掉
        System.out.println(sb.substring(1));
    }
}

感觉

这道题消化及整理 撸代码 共耗时1h30min qaq
理解 上的的障碍 就是 那个进制转换 顺便复习了一下 进制运算 哈哈不亏
看完之后思路就很清晰了。 然后 一个字 妙啊~~

https://github.com/Dxoca/Algorithms/blob/master/src/BlueCup/Six_MathQuestion/Case1_%E5%A4%A9%E5%B9%B3%E7%A7%B0%E9%87%8D.java

参考文献