寒光博客

[LanQiao]天平称重:变种三进制(巧用进制)
题目_数学问题 分析 1, 3, 9, 27, 81,…… 3^0,3^1,3^2,3^3,3^4,…… 题目中...
扫描右侧二维码阅读全文
21
2019/07

[LanQiao]天平称重:变种三进制(巧用进制)

题目_数学问题

变种三进制

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

如果有无限个砝码,重量分别是1,3,9,27,81,……等3的指数幂
神奇之处在于用它们可以称出任意整数重量(砝码允许放在左右两个盘中)。

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

用户输入:

5

程序输出:

9-3-1

用户输入:

19

程序输出:

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

分析

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 即可

总结就是 二进制的 01 代表取和不取

那么换三进制来说

三进制类转换 每位(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)
所以 现在转换到了

我们只要 0 -1 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
理解 上的的障碍 就是 那个进制转换 顺便复习了一下 进制运算 哈哈不亏
看完之后思路就很清晰了。 然后 一个字 妙啊~~

想成为dalao的第二天 以上都是个人总结 如有问题 欢迎指教!!

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

参考文献

本文作者:Author:     文章标题:[LanQiao]天平称重:变种三进制(巧用进制)
本文地址:https://dxoca.cn/Algorithm/178.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:July 31st, 2019 at 12:16 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment